[JAVA] BOJ 백준 20366번 - 같이 눈사람 만들래?

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

처음 시도한 방법은 투포인터 안에 투포인터를 시도했는데, 유사했으나 포인터를 이동하는 부분에서 통과할 수 없던 풀이였다. 따라서 통과한 풀이는 이중 for문을 통해 구간을 정하고, 그 안쪽 구간에서 투포인터를 돌리는 방법으로 해결했다.

 

• 바깥쪽 구간 : i  ~  j
• 안쪽 구간 : innerStart  ~  innerEnd

int result = Integer.MAX_VALUE;

for (int i = 0; i < N; i++) {
    for (int j = i+1; j < N; j++) {
        int innerStart = i+1;
        int innerEnd = j-1;

        int outerSize = arr[i] + arr[j];

        while (innerStart < innerEnd) {
            int innerSize = arr[innerStart] + arr[innerEnd];
            result = Math.min(result, Math.abs(outerSize - innerSize));

            if (outerSize > innerSize) {
                innerStart++;
            }
            else if (outerSize < innerSize) {
                innerEnd--;
            }
            else break;
        }
        if (result == 0) break;
    }
    if (result == 0) break;
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B20366.java

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

class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

        int result = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                int innerStart = i+1;
                int innerEnd = j-1;

                int outerSize = arr[i] + arr[j];

                while (innerStart < innerEnd) {
                    int innerSize = arr[innerStart] + arr[innerEnd];
                    result = Math.min(result, Math.abs(outerSize - innerSize));

                    if (outerSize > innerSize) {
                        innerStart++;
                    }
                    else if (outerSize < innerSize) {
                        innerEnd--;
                    }
                    else break;
                }
                if (result == 0) break;
            }
            if (result == 0) break;
        }

        bw.write(result+"");

        br.close();
        bw.flush();
        bw.close();
    }
}

---

4. 결과 및 회고

오래 붙잡은 문제였는데, 조금 더 빨리 푸는 연습을 하자.