IT LAB

난이도 : Gold 5 문제 링크 1. 문제 설명 요구사항 모든 사람들의 친구관계가 주어질 때, 아래와 같은 친구관계가 존재하는지 판별하라. 친구관계 A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 2. 내 풀이 5명의 사람이 연쇄적으로 친구인 관계 존재 여부 자료구조 (친구관계) 친구관계 : 양방향, 다대다, (친구 수)가변적 무방향 그래프 Vertex: 사람, Edge: 친구 인접 리스트 (메모리 관점에서) 자신의 친구들을 효율적으로 기억할 수 있음 코드 // 선언 private static List graph = new ArrayList(); // 초기화 for (int i = 0; i < nodeCnt; i++) { graph.add(new ArrayList()); ..

난이도 : Level 2 문제링크 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶다. 이를 위해 가장 스코빌 지수가 낮은 두개의 음식을 섞어 새로운 음식을 만든다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다 섞어야 하는 최소 횟수를 리턴하라 해설 1. 최소힙을 사용하여 가장 스코빌 지수가 낮은 음식 두개를 꺼냅니다. PriorityQueue pq = new PriorityQueue(); for (int s : scoville) { pq.add(s); } while (pq.size() > 1 && pq.peek() < K) { int min = pq.poll(); ..

난이도 : 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])..