[백준] 20366 같이 눈사람 만들래?

1. 문제

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

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

2. 접근방법

2가지 방법으로 풀이 했음.

 

첫번째 방법은

정렬 후 2중 포문으로 하나의 눈사람을 만들고

투포인터로 사용하지 않은 나머지 눈뭉치를 이용해

만들어논 눈사람과 가장 비슷한 값을 가지는 눈사람을

만들어 값을 비교하는 방법과 (N^3 + N * log(N))

 

두번째 방법은

2중 포문을 이용해 만들 수 있는 모든 눈사람 조합을 구한 뒤

눈사람 크기에 따라 정렬 후

차이가 최소이려면 두 값이 붙어 있어야 한다는 조건으로 (이 부분에 반례가 있을 것 같았는데 찾지 못해서 그대로 진행)

붙어있는 두 눈사람이 같은 눈덩이를 사용하지 않았을 때만

값을 비교하는 방법으로 풀이했다. (2 * N^2 + N^2 * log ( N^2 ) )

ex)

5 1 3 6 9 -> (눈사람 조합) ->

6 8 11 14 4 7 10 9 12 15 -> (정렬) ->

4 6 7 8 9 10 11 12 14 15 -> (붙어 있는 두 값의 차이 구하기) ->

2(X) 1(X) 1(O) 1(X) 1(O) 1(O) 1(O) 2(X) 1(X) -> (중복 눈덩이 사용 X, 정상 눈사람 O)

-> O 중 최소값 1

 

3. 자바 코드

첫번째

package Gold;

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

public class G3_20366같이눈사람만들래 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int arr[] = new int[N];
		for (int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		Arrays.sort(arr);
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				int snowMan1 = arr[i] + arr[j];
				int start = 0;
				int end = N - 1;
				while (start < end) {
					if (start == i || start == j) {
						start++;
						continue;
					}
					if (end == i || end == j) {
						end--;
						continue;
					}
					int snowMan2 = arr[start] + arr[end];
					min = Math.min(min, Math.abs(snowMan1 - snowMan2));
					if (snowMan1 > snowMan2)
						start++;
					else if (snowMan1 < snowMan2)
						end--;
					else {
						System.out.println(0);
						return;
					}
				}
			}
		}
		System.out.println(min);
	}
}

두번째

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class G3_20366같이눈사람만들래v2 {
	static class sumthing {
		int x1;
		int x2;
		int sum;

		public sumthing(int x1, int x2, int sum) {
			this.x1 = x1;
			this.x2 = x2;
			this.sum = sum;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int arr[] = new int[N];
		for (int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		ArrayList<sumthing> arrList = new ArrayList<sumthing>();
		for (int i = 0; i < N; i++)
			for (int j = i + 1; j < N; j++)
				arrList.add(new sumthing(i, j, arr[i] + arr[j]));
		arrList.sort((sumthing o1, sumthing o2) -> o1.sum-o2.sum);
		int min = Integer.MAX_VALUE;
		for(int i = 0 ; i < arrList.size()-1; i++) {
			sumthing x1 = arrList.get(i);
			sumthing x2 = arrList.get(i+1);
			if(x1.x1 == x2.x1 || x1.x1 == x2.x2 ||x1.x2 == x2.x1 || x1.x2 == x2.x2)
				continue;
			min = Math.min(min, x2.sum-x1.sum);
			if(min == 0)
				break;
		}
		System.out.println(min);
	}

}

4. 마치며

두번째 방법이 빅오로 보면 더 작은데

N이 작다보니 첫번째가 속도가 더 빠르더라고 하더라