IT LAB

난이도 : Level 2 문제링크 H-Index : 논문 n편 중, h번 이상 인용된 논문이 h편 이상,나머지 논문이 h번 이하 인용시, h의 최댓값 논문의 인용 횟수를 담은 배열이 주어질 때, H-Index를 리턴하라 해설 1. H-Index 의 범위는 1 ~ 전체 논문수 입니다. 2. H가 가장 큰 숫자부터 작은수까지 조건을 만족하는지 확인합니다. public int solution(int[] citations) { int answer = 0, size = citations.length; Arrays.sort(citations); for (int i = 0; i = h) { return h; } } return..

난이도 : Level 3 문제링크 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. I 숫자 : 큐에 주어진 숫자를 삽입합니다. D 1 : 큐에서 최댓값을 삭제합니다. D -1 : 큐에서 최솟값을 삭제합니다. 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 리턴 비어있지 않으면 [최댓값, 최솟값] 리턴 해설 1. 두개의 우선순위 큐 사용하기 - 최대힙, 최소힙 PriorityQueue minPq = new PriorityQueue(); PriorityQueue maxPq = new PriorityQueue(Comparator.reverseOrder()); 최소힙 - 최솟값을 항상 루트로 두는 힙 자료구조 최대힙 - 최댓값을 항상 루트로 두는 힙 자료구조 2. 삽입 for (String ..

난이도 : Level 3 문제링크 하드디스크는 한번에 하나의 작업만 수행할 수 있습니다. 각 작업의 요청시간-소요시간을 담은 2차원 배열 jobs가 주어진다. 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리할 때의 평균값을 리턴하라 해설 출처에서 공부한 내용을 정리했습니다 1. 변수 선언하기 int cnt = 0; int idx = 0; int end = 0; cnt : 처리된 작업의 수 idx : 현재 처리한 작업의 인덱스 end : 현재 처리한 작업의 종료시간 2. 요청시간이 빠른 순으로 처리하고, 우선순위 큐로 다음 처리할 작업 정하기 Arrays.sort(jobs, (a, b) -> a[0] - b[0]); PriorityQueue pq = new PriorityQueue(..

난이도 : Level 3 문제링크 n명의 권투선수가 대회에 참가하였다 1대1 방식으로 진행되며 승패 정보가 주어진다 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다 A선수가 B선수보다 실력이 좋다면 A선수는 B선수를 항상 이깁니다 몇몇 경기가 분실되어 정확하게 순위를 매길 수 없습니다 정확하게 순위를 매길 수 있는 선수의 수를 리턴하라 해설 1. 플로이드-워셜 알고리즘을 활용한 모든 선수들의 승패 배열 생성하기 boolean[][] graph = new boolean[n][n]; for (int i = 0; i < results.length; i++) { graph[results[i][0]-1][results[i][1]-1] = true; } for (int k = 0; k < n; k++..

난이도 : Level 3 문제링크 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하라 해설 1. 인접노드 데이터 자료구조 생성 private Map init(int[][] edge, Map edges) { for (int i = 0; i < edge.length; i++) { int src = edge[i][0]-1, desc = edge[i][1]-1; makeEdges(src, desc, edges); makeEdges(desc, src, edges); } return edges; } private void makeEdges(int src, int desc, Map edges) { if (!edges.containsKey(src)) { Set set = new HashSet(); set.add(de..

난이도 : Level 4 문제링크 출발지부터 distance 만큼 떨어진 도착지점이 있고 그 사이에는 바위들이 놓여 있다. 최대 n개의 바위를 제거하였을 때, 각 바위 사이의 거리의 최솟값 중 가장 큰 값을 리턴하라. 해설 1. 바위 사이의 거리의 최솟값중 최댓값을 이분탐색 public int solution(int distance, int[] rocks, int n) { long left = 1, right = distance, mid = 0, answer = 0, prevRock = 0, rockCount = 0; Arrays.sort(rocks); while (left rock - prevRock) rockCount++; else prevRock = rock; } if (mid > distance ..

난이도 : Level 3 문제링크 입국심사를 위해 n명이 줄을 서있습니다. 가장 앞에 서있는 사람은 비어있는 심사대로 가서 심사를 받을 수 있습니다. 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 각 입국심사관이 심사하는데 걸리는 시간이 주어집니다. 입국심사관은 동시에 한명만 심사할 수 있습니다. 모든 사람이 심사를 받는데 걸리는 최소 시간을 리턴하세요. 해설 1. 심사에 걸리는 모든 시간을 대상으로 이분탐색 public long solution(int n, int[] times) { Arrays.sort(times); int count = 0; long minTime = 1, midTime = 0, maxTime = (long)times[0] * n; while ..

난이도 : Sliver 4 문제링크 N개의 정수가 주어질 때, 이 안에 X라는 정수가 존재하는 지 여부를 리턴하라 해설 전체코드 보기 1. A배열 정렬하기 static int N, M; static int[] A, B; public static void main(String[] args) throws IOException { init(); Arrays.sort(A); for (int i = 0; i < M; i++) { binarySearch(i); } } 이분탐색을 활용하기 위해 A배열을 정렬합니다. 2. 이분탐색을 통해 검색하기 private static void binarySearch(int idx) { int left = 0, right = A.length-1; while (left B[idx])..

난이도 : Gold 2 문제링크 5*5 격자판이 5개 쌓인 3차원 미로가 존재한다 (5*5*5) 주어진 5개의 격자판을 임의의 순서대로 쌓아 퍼즐을 만든다. 맨 위 격자의 좌측 상단(0, 0)에서 맨 아래 격자의 우측 하단까지(4, 4) 도착하는데 걸리는 최단 이동 횟수를 구하라 격자는 회전가능하며, 벽은 이동할 수 없음 해설 전체코드 보기 1. 퍼즐을 만들 수 있는 모든 경우 탐색하기 private static void dfs(int depth, int[][][] curMaze) { if (depth == height) { if (curMaze[0][0][0] == 1 && curMaze[4][4][4] == 1) { int turn = bfs(curMaze, new boolean[height][row..

난이도 : Level 3 문제링크 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채워야 한다 보드의 빈공간과 조각은 딱 맞아떨어져야 한다 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 리턴하라 조각을 회전시킬 수 있음 조각끼리는 서로 인접할 수 없다 해설 game_board에 있는 빈칸들과 table에 있는 퍼즐들을 각각 List에 담습니다 각각 인접한 빈칸과 퍼즐을 (0, 0)에서 시작하는 리사이징 2차원 배열을 생성하고 list에 담습니다. 빈칸과 퍼즐을 비교하기 위함입니다. 빈칸에 현재 가지고 있는 퍼즐들을 하나씩 맞춰보면서 딱 맞으면 퍼즐의 갯수만큼 누적합을 계산합니다. 퍼즐에 빈칸이 맞지 않으면 시계방향으로 90도 회전해 봅니다 회전해도 맞지 않다면 해당 퍼즐은 빈칸..