Java

문제 접근 방식 한 사람이 모든 사람을 친구의 친구의 친구...의 친구 까지 걸치고 걸쳐 모두 알 수 있다고 가정 했을 때 모든 사람을 알기 위해 필요한 단계가 가장 짧은 사람을 구해야 한다. 1 2 2 3 3 4 4 5 2 4 5 3 위와 같은 관계가 주어졌을 때 2번 사람의 경우를 살펴보면 아래와 같다. 본인 2 친구 1 3 4 친구의 친구 5 2번 자기 자신과 직접적으로 친구 관계인 1, 3, 4번이 있고 5번은 3번의 친구니 친구의 친구 관계이고 2번이 모든 사람을 알기 위해 필요한 단계는 친구의 친구까지다. 즉, 본인 0단계, 친구 1단계, 친구의 친구 2단계로 2단계만 거치면 모든 사람을 알 수 있다. 이때 조심해야 할 점은 2번이 5번을 알 수 있는 방법이 두 가지인데 첫 번째는 2 >> 3..

문제 접근 방식 DFS와 BFS 방식으로 탐색하는 순서를 순서대로 출력하면 된다. 문제를 대충 보고 인접 리스트로 풀었더니 예제가 틀리길래 다시보니 작은 번호의 정점부터 방문하는 조건이 있어서 인접 행렬로 바꿔 풀었다. 양방향 그래프이기 때문에 양쪽 간선에 모두 이동할 수 있게 인접 행렬에 표시해주고 DFS와 BFS 순서대로 탐색을 진행해주면서 정점에 방문할 때마다 출력해주면 된다. 풀이 public class Main { private static int n; private static int[][] nearArr; private static boolean[] isVisited; private static StringBuilder sb = new StringBuilder(); public static ..

문제 접근 방식 끊기지 않고 연결된 묶음이 몇 개인지 찾는 문제로 BFS와 DFS 둘 중 아무거나 사용해서 풀 수도 있고, 인접 행렬이나 인접 리스트 중 아무거나 사용해도 상관없기에 BFS를 사용해서 인접 행렬과 인접 리스트 둘 다 사용해 풀어봤다. 문제에서 주어진 그래프는 무방향 그래프이기 때문에 인접 행렬이나 리스트를 만들 때 (x, y)와 (y, x) 모두 추가해줘야 한다. 인접 행렬의 경우에는 0과 1로 구분해서 간선이 존재하는 경우를 1로 표현해주면 되고 인접 리스트의 경우에는 해당 정점에서 이동할 수 있는 정점을 추가해주면 된다. 풀이 인접 행렬을 사용한 풀이 public class Main { public static void main(String[] args) throws IOExcepti..

문제 접근 방식 우선순위 큐를 활용해서 풀 수 있는 문제로 우선순위 큐를 덱처럼 사용하면 된다. 원할 때마다 언제든지 가장 작은 값을 빼거나 가장 큰 값을 뺄 수 있어야 하기 때문에 최소힙과 최대힙에 동일하게 수를 추가해 준 후에 가장 큰 값을 빼야 하는 경우에는 최대힙에서 반대의 경우는 최소힙에서 빼주면 된다. 이때 조심해야할게 반대쪽에서 뺀 수는 반대쪽에만 사라지고 다른 한쪽에는 존재하기 때문에 맵을 이용해서 수마다 등장 횟수를 카운팅 해준 후에 수들을 큐에서 꺼낼 때마다 꺼낸 수가 등장 횟수가 남아있는지 확인하여 다른 쪽의 큐와 상태를 유지해 줄 수 있다. 예를 들면 최대값을 하나 빼려고 최대힙에서 9라는 숫자를 꺼냈는데 해당 숫자의 카운트가 0이라면 최소힙에서 빼서 사라진 값이기에 해당 수를 건너..

문제 접근 방식 정말 쉬운데 하고 풀었다가 바로 틀려버린 문제다... 데드라인이 빠른 순으로 정렬하고 같다면 보상이 큰 순으로 정렬한 후에 그대로 반복문을 돌면서 더해줬더니 예제는 맞지만 제출하니 틀렸다. 예제가 하나뿐이라 생각하지 못한 케이스가 있었는데 데드라인이 나중이라도 이전 데드라인 문제를 생략하고 이후의 데드라인 문제를 푸는 것이 좋을 때가 있다. 2 30 2 20 3 60 3 50 위와 같이 데드라인이 2일 때 2개를 선택하는 것보단 둘 다 선택하지 않고 데드라인이 3일 때를 선택하는 것이 더 효율적이다. 그래서 정렬은 그대로 유지하되 최소힙을 사용해 이전에 선택한 값이 이후에 선택할 값보다 비효율적인 경우 교체해줘야 한다. 2 30 2 20 최소힙 {20, 30} 3 60 최소힙 {30, 6..

문제 접근 방식 수가 하나씩 추가될 때마다 현재까지의 수 중에서 중간값을 출력해야 하고 현재까지 부른 수가 짝수 개면 중간값은 둘 중 더 작은 수를 출력한다. 무식하게 생각하면 매번 수를 부를 때마다 정렬해서 중간 인덱스를 출력하는 방법을 떠올릴 수 있지만 문제의 제한 시간과 입력을 생각하면 불가능하다. 최소힙과 최대힙 우선순위 큐를 각각 하나씩 만들어서 특정 상황에 맞게 수를 저장하고 꺼내는 방식으로 효율적으로 풀 수 있는 문제다. 예를 들어 현재까지 주어진 수가 짝수 개일 때를 생각해 보면 현재 수가 이전까지의 중간값보다 작은 경우를 살펴보면 다음과 같다. 4 5 10 (11) 12 15 20// 중간값 11 >> 6 이 입력으로 들어옴 4 5 6 (10 11) 12 15 20 // 중간값이 두개지만..

문제 접근 방식 맨 처음에 문제를 풀 때는 잘못 이해해서 정렬을 사용해서 풀 수도 있을 줄 알았는데 문제를 제대로 이해하고 보니 중간중간 계산 결과를 다시 넣을 때마다 정렬을 한다면 매우 비효율적이기 때문에 우선순위 큐를 사용해서 풀었다. 10 // 10개의 수가 주어졌을 때 123 456 234 998 12 7 876 887 455 234 만약 위와 같은 입력이 주어졌을 때 계산 순서는 다음과 같다. 7 + 12 = 19 19 + 123 = 142 142 + 234 = 376 376 + 234 = 610 610 + 455 = 1065 1065 + 456 = 1521 1521 + 876 = 2397 2397 + 887 = 3284 3284 + 998 = 4282 위 순서대로 계산하여 결과를 모두 더하면 ..

문제 접근 방식 배열에 수를 모두 저장한 후에 정렬하고 끝에서 n번째 인덱스를 출력해도 풀리는 문제지만 우선순위 큐를 이용해서 좀 더 효율적으로 풀 수 있다. 최소 힙으로도 풀 수 있지만 최대 힙으로 푸는 것이 더 효율적이니 자바에서 제공하는 우선순위 큐 기준으로는 생성자 파라미터로 정렬 기준을 역순으로 주어 최대 힙을 사용할 수 있다. 최대 힙에 입력 받은 수들을 모두 넣어준 후에 n개를 꺼내면 n번째 큰 수가 나오게 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..