드디어 7단계 스트릭 뱃지... 다음은 256일...
분류 전체보기
문제 접근 방식 결국 문제에서 요구하는건 두 우주의 행성들의 대소관계가 같은지를 판단하는 것이기 때문에 이분 탐색으로 좌표 압축을 한 후에 좌표 압축 결과가 같은 배열 쌍이 존재할 때마다 카운트를 1씩 증가시켜주기만 하면 된다. 20 10 30 10 20 60 80 25 79 30 50 80 80 25 81 예를 들어 위와 같이 5개의 우주마다 3개의 행성이 있을 때 행성의 크기 순으로 표현하면 다음과 같다 1 0 2 0 1 2 2 0 1 0 1 2 1 0 2 가장 작은 수부터 0이라고 표현 했을 때 행성의 대소관계가 일치하면 같은 행성이라고 볼 수 있기 때문에 1 0 2로 같은 1번과 5번 행성이 균등하다 볼 수 있고 0 1 2로 같은 2번과 4번 행성도 균등하다. 풀이 public class Main..
문제 접근 방식 주어진 수들에서 중복을 허용하여 3개의 수를 더한 값이 이미 배열에 존재하는 경우 중 가장 큰 값을 찾아야 한다. 수들이 최대 1000개 주어지기 때문에 3중 반복문으로 모든 경우를 다 곱하는 경우만 해도 최대 10억 번의 계산이 필요해 값을 찾기까지 하려면 절대 불가능한 방법이다. 문제를 x + y + z가 아니라 (x + y) + z로 나누어 생각해보면 x + y를 먼저 구해둔 후에 합해서 z가 될 수 있는 경우를 찾으면 된다. x + y를 모두 구하면 최대 1,000,000개가 나올 수 있기 때문에 이걸 매번 O(N)으로 반복 순회하면 안되고 정렬하여 이분 탐색으로 찾아주면 된다. 정리하면 아래와 같다. 1. 배열을 정렬한다. nums 2. (x + y) 쌍을 구한다. pairs 3..
문제 접근 방식 문제 이름 그대로 트리의 높이와 넓이를 구해야 하는데 주의해야 할 점은 이진 트리가 주어질 때 루트 노드는 주어지지 않기 때문에 탐색을 무조건 1번 정점에서 시작하는 것이 아니라 따로 루트 노드를 찾아서 시작해줘야 한다. 트리의 높이야 탐색을 하면서 자식 노드를 방문할 때마다 부모 노드의 높이 + 1을 해주면 되니 쉽게 구할 수 있지만 문제는 트리의 넓이를 구하는 것이다. 위의 트리의 경우를 살펴보면 알 수 있는게 가로 한 줄에는 하나의 정점만 존재할 수 있고, 가장 왼쪽 가로줄의 정점부터 1번째 가장 오른쪽의 정점을 n번째로 방문한다. 즉, 처음 방문하는 정점은 8번 정점일 것이고 가장 마지막에 방문하는 정점은 7번 정점이 된다. 이진 트리가 주어지니 전위, 중위, 후위 순회 중에서 문..
문제 접근 방식 내리 칭찬이 있어서 부하는 상사가 받은 칭찬 + 상사한테 받을 칭찬을 받을 수 있다. 트리에서 상사는 부모고 부하는 자식이니 루트부터 방문을 하면서 부하에게 현재까지 본인이 받은 칭찬을 넘겨주기만 하면 된다. 조심해야할게 한 명의 부하가 여러번 칭찬을 받을 수 있어서 입력을 받을 때 부하 번호 = 부하가 직속 상사로부터 받은 칭찬 이 아니라 부하 번호 += 부하가 직속 상사로부터 받은 칭찬 이 되어야 한다. 풀이 public class Main { private static final ArrayList near = new ArrayList(); private static int[] compliments; public static void main(String[] args) throws I..
문제 접근 방식 분리 집합과 유니온 파인드에 대해서 아직 배우지 않아 기존에 풀었던 4803번 문제와 비슷하게 풀면 풀 수 있겠다 생각이 들어 무작정 시도해봤는데 어찌저찌 풀었다. 우선 이번 문제는 그래프가 주어졌을 때 간선을 지우거나 추가하여 하나의 트리로 만들기 위한 총 횟수를 구해야 한다. 간단하게 생각하면 한 정점에서 방문할 수 있는 모든 정점을 방문했을 때 사이클이 존재하지 않는다면 이미 하나의 트리니 기존의 트리와 합치기만 하면 될 것이고 그렇지 않다면 간선을 제거해주고 합쳐주면 된다. 사이클이 존재하는 경우에 몇 개의 간선을 제거해야 하는지는 트리의 규칙을 생각해보면 쉬운데 정점 N개의 트리는 N-1개의 간선을 가지고 있으니 현재까지 발견한 간선의 수 - (N - 1) = 삭제해야 할 간선의..
문제 접근 방식 이전까지의 트리 문제에서는 각 노드 간의 거리가 1이였다면 이번 문제에서는 노드 간 거리가 서로 다르게 주어진다. 그래서 인접 리스트를 만들 때 기존에는 각 각선의 양끝 정점에 대해서만 넣어줬다면 이번에는 정점 간의 거리도 넣어준 후에 탐색만 해주면 된다. 풀이 public class Main { private static int start, end, result; private static boolean[] isVisited; private static final ArrayList near = new ArrayList(); public static void main(String[] args) throws IOException { BufferedReader br = new Buffered..
문제 접근 방식 정점이 N개이고 루트가 R인 올바른 트리에 대한 간선이 주어졌을 때 정점이 U인 경우에는 몇 개의 정점을 방문할 수 있는지를 알아내면 된다. 예를 들어 위와 같은 트리가 있을 때를 생각해보면 루트인 5번 정점부터 방문하면 당연히 모든 정점인 9개의 정점을 다 방문할 수 있다. 하지만 4번 정점부터 방문한다면 위와 같이 4개의 정점만 방문할 것이고 8번 정점부터 방문한다면 8번 하나만 방문할 수 있다. 이제 특정 정점에 포함된 정점의 개수가 몇 개인지를 알아내면 되는데 이는 트리의 성질을 이용하면 쉽게 계산할 수 있다. 위의 트리를 다시 살펴보면 정점 3의 경우는 자기 자신을 포함한 자식 노드의 정점 수의 합인 3이고 정점 4의 경우도 마찬가지로 자기 자신을 포함한 자식 노드인 3번 노드의..
