[백준] 31848 엉성한 도토리 분류기 (이진탐색)

park geonwoo·2024년 9월 13일
코딩테스트

코딩테스트

목록 보기
7/32

https://www.acmicpc.net/problem/31848

풀이

이 코드는 주어진 구멍 배열과 도토리의 크기를 이용하여, 도토리가 어느 구멍에 떨어지는지 찾아내는 문제를 해결하는 코드입니다. 이 코드는 이진 탐색을 활용하여 도토리가 빠지는 구멍을 효율적으로 찾습니다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(br.readLine());
		int prev = 0;
		int[] holeSize = new int[n + 1];
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i <= n; i++){
			int curr = Integer.parseInt(st.nextToken()) + i - 1;
			if(curr > prev) prev = curr;
			holeSize[i] = prev;
		}

		int q = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < q; i++) {
			int curr = Integer.parseInt(st.nextToken());
			int left = 1;
			int right = n + 1;
			while(left < right) {
				int mid = (left + right) / 2;
				if(holeSize[mid] >= curr) right = mid;
				else left = mid + 1;
			}
				sb.append(right).append(" ");
		}
		System.out.println(sb);
	}
}

주요 과정 설명

  1. 입력 처리:
    • BufferedReader와 StringTokenizer를 사용하여 빠르게 입력을 처리합니다.
    • 구멍의 개수 n과 각 구멍의 크기 배열 holeSize[]을 처리한 후, 도토리의 개수 q와 도토리의 크기 배열을 입력받습니다.
  2. 구멍 크기 배열 생성:
    • holeSize[] 배열은 각 구멍이 받아들일 수 있는 도토리의 크기를 저장합니다.
    • 여기서 중요한 점은, 구멍의 크기가 i에 따라 점점 줄어든다는 문제의 특성을 반영하여 holeSize 배열을 구축하는 방식입니다.
    • prev는 이전 구멍까지 고려한 현재 가능한 최대 구멍 크기를 저장합니다.
  3. 이진 탐색:
    • 각 도토리 크기에 대해, 도토리가 빠질 수 있는 첫 번째 구멍을 이진 탐색으로 찾아냅니다.
    • 이진 탐색을 통해 holeSize[] 배열에서 도토리 크기보다 크거나 같은 구멍을 빠르게 찾습니다.
    • 이진 탐색은 left와 right 포인터를 사용하여 배열을 절반씩 줄여가며 탐색합니다.
  4. 출력:
    • StringBuilder를 사용하여 결과를 모아서 한 번에 출력합니다. 이렇게 하면 출력 성능이 최적화됩니다.

구멍 크기 배열 생성 부분이 다소 복잡하게 보일 수 있지만, 본질적으로는 구멍의 크기를 증가시켜 나가는 과정입니다. 문제의 특성상, 각 구멍을 지날 때 도토리의 크기는 1씩 줄어듭니다. 이를 반영하기 위해 구멍의 크기를 처리하는 방식이 아래와 같이 동작합니다.

int prev = 0;
int[] holeSize = new int[n + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
    int curr = Integer.parseInt(st.nextToken()) + i - 1;
    if (curr > prev) prev = curr;
    holeSize[i] = prev;
}

핵심 개념

  • 각 구멍을 지날 때 도토리의 크기가 1씩 줄어드는 규칙이 있습니다.
  • 구멍의 크기는 각 구멍 번호에 의해 도토리 크기가 줄어들기 때문에, 이를 적절히 반영하는 구멍 크기 배열 holeSize[]를 만들어야 합니다.

코드 흐름 설명

  1. 구멍의 크기 조정:
    • 주어진 구멍 크기 a_i는 도토리가 구멍을 통과하면서 크기가 줄어드는 규칙을 반영해야 합니다. 따라서, 각 구멍의 크기에 구멍 번호 i에 따라 크기를 보정하는 작업이 필요합니다.
    • curr = Integer.parseInt(st.nextToken()) + i - 1;:
      • 이 부분은 i번 구멍을 지날 때의 크기를 계산하는 식입니다. st.nextToken()은 해당 구멍의 원래 크기를 의미하며, i - 1을 더해주는 이유는 도토리가 구멍을 지나갈 때마다 크기가 1씩 줄어들기 때문입니다.
      • 예를 들어, 구멍 1번의 크기가 5이고, 구멍을 지날 때마다 도토리 크기가 1씩 줄어든다면, 구멍 2번에서는 4, 구멍 3번에서는 3, 이런 식으로 처리해야 합니다.
  2. 이전 구멍과의 비교 (prev 사용):
    • if (curr > prev) prev = curr;:
      • prev는 이전까지 가장 큰 구멍의 크기를 저장합니다. 각 구멍의 크기를 확인하면서, 현재 구멍의 크기 curr이 prev보다 크면 prev를 갱신합니다.
      • 이 과정은 구멍 크기가 감소하지 않도록 보장하기 위함입니다. 즉, 도토리가 더 작은 구멍을 지나치게 되면 그 이후 구멍들의 크기도 최소한 그 구멍 크기만큼은 유지해야 합니다.
  3. 구멍 크기 배열에 저장:
    • holeSize[i] = prev;:
      • 현재 구멍 번호 i에 해당하는 크기를 prev에 저장된 값으로 설정합니다. 이렇게 하면, 구멍의 크기가 점차 커지거나 일정하게 유지되도록 보장됩니다.

예시

아래는 구멍 크기 예시와 함께 배열을 구성하는 과정을 설명한 것입니다.

예시 1

입력: 5 6 1 4 9 2 8 10 3 7 (구멍 크기)

  1. i = 1: 구멍 1번의 크기는 5 + 1 - 1 = 5, prev는 5가 된다.
    • holeSize[1] = 5
  2. i = 2: 구멍 2번의 크기는 6 + 2 - 1 = 7, prev는 7로 갱신된다.
    • holeSize[2] = 7
  3. i = 3: 구멍 3번의 크기는 1 + 3 - 1 = 3, prev는 7이 더 크므로 갱신되지 않는다.
    • holeSize[3] = 7
  4. i = 4: 구멍 4번의 크기는 4 + 4 - 1 = 7, prev는 그대로 유지된다.
    • holeSize[4] = 7
  5. i = 5: 구멍 5번의 크기는 9 + 5 - 1 = 13, prev는 13으로 갱신된다.
    • holeSize[5] = 13
  6. ... 이런 식으로 마지막까지 구멍 크기를 계산하면서 holeSize[] 배열이 완성됩니다.
[0, 5, 7, 7, 7, 13, 13, 14, 15, 15, 15]

요약

  • 이 과정은 각 구멍이 받아들일 수 있는 최대 크기의 도토리를 고려하여 구멍 크기 배열을 생성하는 방법입니다.
  • 도토리 크기가 줄어드는 특성을 고려해 구멍 크기를 조정하고, 감소하지 않도록 보장하는 역할을 합니다.
  • 이진 탐색을 위해 구멍 크기를 적절하게 계산해둔 배열을 사용하게 되므로 이후 탐색 과정에서 빠르게 도토리가 빠질 구멍을 찾을 수 있습니다.

시간 복잡도

  • 이 구멍 크기 배열을 만드는 과정은 N개의 구멍에 대해 한 번의 루프만 실행되므로, O(N) 시간 복잡도를 가집니다.

알고리즘

  1. 구멍 크기 배열 계산:
    • 각 구멍의 크기를 holeSize[]에 저장하는 과정은 선형 시간 복잡도 O(n)입니다.
    • 구멍의 크기는 (i + 주어진 구멍 크기 - 1)로 계산하여 점차 커지도록 prev 값을 업데이트하면서 배열을 구축합니다.
  2. 이진 탐색 (Binary Search):
    • 도토리의 크기보다 크거나 같은 구멍을 찾기 위해 각 도토리에 대해 holeSize[] 배열에서 이진 탐색을 수행합니다.
    • 이진 탐색은 배열을 절반씩 탐색하므로, 각 도토리에 대해 O(log n)의 시간이 소요됩니다.

시간 복잡도 분석

  1. 구멍 크기 배열 생성:
    • 구멍의 개수 n에 대해 O(n) 시간이 소요됩니다.
  2. 도토리 처리:
    • 각 도토리에 대해 이진 탐색을 수행하며, 이진 탐색의 시간 복잡도는 O(log n)입니다.
    • 도토리의 개수가 q이므로, 총 시간 복잡도는 O(q * log n)이 됩니다.
  3. 최종 시간 복잡도:
    • 구멍 크기 배열을 만드는 데 O(n), 도토리별로 이진 탐색을 수행하는 데 O(q * log n)의 시간이 소요됩니다.
    • 따라서 전체 시간 복잡도는 O(n + q * log n)입니다.

자료구조

  1. 배열:
    • 구멍의 크기를 저장하는 holeSize[] 배열을 사용합니다. 크기는 n+1로, 1-based indexing을 사용하여 구멍의 번호를 쉽게 참조할 수 있습니다.
  2. 이진 탐색:
    • 이진 탐색을 사용하여 도토리가 빠지는 첫 번째 구멍을 빠르게 찾습니다. 이진 탐색은 정렬된 배열에서 특정 값을 빠르게 찾기 위해 사용되는 효율적인 탐색 방법입니다.
  3. StringBuilder:
    • 출력 성능을 최적화하기 위해 사용됩니다. 출력 값을 미리 모아서 한 번에 출력함으로써 반복적인 출력에서 발생하는 성능 저하를 방지합니다.

코드의 흐름

  1. 구멍 크기 배열 초기화:
    • 각 구멍의 크기를 계산하여 holeSize[] 배열에 저장합니다. 이때 이전 구멍 크기와 현재 구멍의 크기를 비교하면서 점점 더 큰 구멍 크기를 유지합니다.
  2. 이진 탐색으로 도토리 처리:
    • 각 도토리에 대해 이진 탐색을 수행하여 구멍을 찾아내고, 그 결과를 StringBuilder에 저장합니다.
  3. 출력:
    • 최종 결과를 System.out.println()으로 출력합니다.

결론

이 코드는 도토리 크기와 구멍 크기를 비교하여 도토리가 빠질 수 있는 구멍을 효율적으로 찾는 문제를 해결하기 위해 이진 탐색 알고리즘을 사용했습니다. 시간 복잡도는 O(n + q * log n)로, 최대 입력 범위인 n = 100,000과 q = 100,000일 때도 충분히 효율적으로 동작합니다.

profile
park geonwoo
이전 포스트

[프로그래머스] 게임 맵 최단거리 (BFS)

다음 포스트

[백준] 1749 점수따먹기 (누적합, 카데인 알고리즘)

0개의 댓글