백준 20366 (같이 눈사람 만들래?) - java

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

 

문제

언니! 똑...똑똑...똑똑! 같이 눈사람 만들래~? ♪

언니 엘자와 동생 안나에게는 N개의 눈덩이가 있다. 각 눈덩이 i (1 ≤ i ≤ N)의 지름은 Hi 이다. 하나의 눈사람은 두 개의 눈덩이로 구성되며, 눈덩이 하나를 아래에 두고 그 눈덩이보다 크지 않은 다른 눈덩이를 쌓아올리는 방식으로 만들 수 있다. 이때, 눈사람의 키는 두 눈덩이 지름의 합과 같다.

엘자와 안나는 눈덩이 N개 중 서로 다른 4개를 골라서 눈사람을 각각 1개씩, 총 2개를 만들려고 한다. 두 자매는 두 눈사람의 키의 차이가 작을수록 두 눈사람의 사이가 좋을 것이라고 믿는다. 우리는 엘자와 안나가 가장 사이좋은 두 눈사람을 만들기 위해서 도와주려고 한다.

주어진 N개의 눈덩이를 이용하여 만들 수 있는 두 눈사람의 키 차이 중 최솟값을 구하는 프로그램을 작성하시오.

 

유형 : 투 포인터

 

접근 방식

• 단순하게 문제를 접근하자면 N개의 수에서 4개를 뽑아서 |(x1 + x2) - (x3 + x4)| 의 최솟값을 구하는 문제이다.
• N의 범위를 고려하여 문제를 해결하기 위해서 O(N^3)의 풀이법을 생각했고 투 포인터를 사용하면 된다.
• 우선 N개의 수를 정렬한다.
• N개의 수에서 2개를 뽑는다.
• 뽑은 수가 아닌 2개의 수를 투 포인터를 통해 찾는다.
  • 앞서 뽑은 2개의 수의 합과 최대한 근접한 수를 찾도록 조건문을 설정하면 된다.

 

전체 코드

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

public class Main {

    static int n;
    static int[] board;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());

        board = new int[n];
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < n ; i++){
            board[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(board);

        for(int i = 0 ; i < n - 1 ; i++){
            for(int j = i+1; j < n ; j++){
                int tmpSum = board[i] + board[j];

                find(i,j,tmpSum);
            }
        }

        System.out.println(result);

        br.close();
    }

    static int result = Integer.MAX_VALUE;
    static void find(int tmpX,int tmpY,int tmpSum){

        int l = 0;
        int r = n - 1;

        while(l < r){
            while(l == tmpX || l == tmpY){
                l++;
            }

            while(r == tmpY || r == tmpX){
                r--;
            }

            if(l >= r){
                break;
            }

            int tmp = board[l] + board[r];

            if(tmp == tmpSum){
                result = 0;
                break;
            }else if(tmp > tmpSum){
                result = Math.min(result, Math.abs(tmp - tmpSum));
                r--;
            }else{
                result = Math.min(result, Math.abs(tmp - tmpSum));
                l++;
            }
        }
    }


    static void print(){
        for(int i = 0 ; i <  n ; i++){
            System.out.print(board[i]+" ");
        }
        System.out.println();
    }
}