[백준] 20366. 같이 눈사람 만들래? (Java)

 

문제

20366번: 같이 눈사람 만들래?

 

알고리즘

투 포인터

 

풀이

4개의 눈덩이를 골라야하므로 완전 탐색을 할 경우 O(n⁴) 의 시간 복잡도를 가질 것이고 n이 최대 600이므로 시간 초과가 날 것이다.

따라서 투 포인터를 이용하여 O(n³)의 시간 복잡도로 해결한다.

 

4개의 눈덩이가 크기 순으로 나열되어있다면

1, 4 번째 눈덩이를 합치고, 2, 3 번째 눈덩이를 합쳐야 두 눈사람의 키 차이가 가장 작을 것이다.

 

따라서

[0~N-1] 범위의 엘사의 첫번째 눈덩이 i 와

[i+3 ~ N-1] 범위의 엘사의 두번째 눈덩이 j를 정해

엘사의 눈사람의 키를 구하고,

 

안나의 첫번째 눈덩이 left = i + 1 와 안나의 두번째 눈덩이 right = j - 1 을 시작으로

안나의 눈사람의 키를 구해 엘사의 눈사람의 키와 비교하여 최솟값을 갱신하고,

안나의 눈사람의 키가 더 작다면 left를 1 늘리고 안나의 눈사람의 키가 더 크다면 right를 1 줄인다.

 

위 과정을 left 와 right가 같아질 때까지, 즉 안나의 모든 눈덩이 조합을 확인했을 때까지 반복한다.

 

만약 두 눈사람의 키가 똑같다면 그보다 최솟값이 없으므로 0을 출력하고 프로그램을 종료한다.

 

 

코드

package baekjoon.m10;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_20366 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int[] snowball = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++)
			snowball[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(snowball);

		int min = Integer.MAX_VALUE;

		for (int i = 0; i < N; i++) {
			for (int j = i + 3; j < N; j++) {

				int elsa = snowball[i] + snowball[j];

				int left = i + 1;
				int right = j - 1;
				
				while(left < right) {
					int anna = snowball[left] + snowball[right];
					
					if(anna < elsa) left++;
					else if(anna > elsa) right--;
					else if(anna == elsa) {
						System.out.println(0);
						return;
					}
					
					min = Math.min(min, Math.abs(elsa - anna));
				}
			}
		}
		
		System.out.println(min);
	}
}