Java

문제 접근 방식 기본적인 재귀 문제로 문제에 기저 조건부터 규칙까지 그대로 나와 있기 때문에 코드로 구현만 하면된다. 우선 재귀 함수의 기저 조건은 선의 길이가 1일 때일 것이고 현재 선의 중앙을 길이의 3분의 1만큼 공백으로 바꿔준 후에 나머지 왼쪽과 오른쪽 선도 재귀를 이용해 같은 과정을 반복해주면 된다. 풀이 public class Main { private static char[] chars; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder()..

문제 접근 방식 Merge Sort를 구현하여 k번째로 정렬되는 수를 구하면 된다. 정렬 후에 k번째 수를 구하는 것이 아닌 정렬 과정에서의 k번째 수인 것에 유의해야 한다. 문제에서 요구하는 구현 방식은 바텀업이 아닌 탑다운 방식이기 때문에 주어진 의사코드대로 구현하면서 카운팅을 해주다 k번째일 때 수를 기록만 하면 된다. 바텀업 방식은 정렬 순서가 조금 다르기 때문에 정렬 결과는 같더라도 해당 문제를 풀기에는 적합하지 않다. 우선 0번째 인덱스부터 n-1번째 인덱스를 정렬하기 위해서는 왼쪽과 오른쪽 절반으로 나누어가면서 더 이상 나눌 수 없을 때까지 나눈 후에 다시 배열을 합쳐가면서 더 작은 값들을 임시 배열에 기록한 후에 임시 배열의 결과를 원본 배열에 옮겨주면 된다. 풀이 public class ..

문제 접근 방식 트리를 순회하면서 해당 노드에 자식이 없다면 해당 노드는 리프 노드라는 것을 알 수 있으니 카운트를 1씩 증가시켜주면 된다. 처음에는 루트 노드가 무조건 0번인줄 알고 풀었는데 틀려서 찾아 보니 루트 노드는 랜덤이기 때문에 이 부분만 조심해서 입력으로 -1을 받을 때 해당 부분을 루트 노드로 지정하고 탐색해주면 된다. 또한 이진 트리가 아닌 일반적인 트리이기 때문에 자식이 꼭 최대 두 개가 아니라 이상일 수도 있다. 풀이 public class Main { private static int remove, leaf = 0; private static final ArrayList near = new ArrayList(); public static void main(String[] args) ..

문제 접근 방식 각 스티커를 고른 상태 안고른 상태로 백트래킹으로 탐색하면 주어진 입력의 최대 범위로는 시간초과가 발생해 완탐으로 풀 수 없는 문제라 DP를 이용해 풀어야 한다. DP로는 O(N)에 풀 수 있는데 우선 DP 테이블부터 만들어보자. 10 30 10 50 100 20 40 20 40 30 50 60 20 80 위와 같은 입력이 주어졌다고 가정하면 0 40 30 100 180 130 230 0 10 50 60 130 210 210 270 0 20 50 80 110 190 230 290 0 40 50 100 120 150 290 위와 같은 표가 만들어지고 2, 3번째 행이 DP 테이블에 저장될 값들이다. 우선 각 줄의 스티커가 선택될 수 있는 경우는 현재 줄의 이전 스티커를 사용하지 않았거나 현..

문제 접근 방식 결국 문제에서 요구하는건 두 우주의 행성들의 대소관계가 같은지를 판단하는 것이기 때문에 이분 탐색으로 좌표 압축을 한 후에 좌표 압축 결과가 같은 배열 쌍이 존재할 때마다 카운트를 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..