[BOJ] 백준 1337 - 올바른 배열 풀이

1. 문제

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

1337번: 올바른 배열

 

2. 풀이

백준 실버 4에 해당하는 문제이며, 문제에 대한 실마리를 찾는데 오래 걸렸던 문제이다.

처음 생각은 배열을 정렬하고, 배열의 원소 하나를 기준으로 잡고, 그 수로부터 연속된 수가 배열에 몇개가 있는지 카운트하며 그 수를 4에서 빼준 값 중 최솟값을 찾으려고 했다. 이 방식의 문제점은 예제 입력 2에서 바로 알 수 있다.

예제 입력 2에서 8492를 기준으로 잡고 연속된 수는 8493 하나가 있다. 나머지 수는 연속된 수가 없기 때문에 결과가 4를 가지며 8492를 기준으로 잡았을 때는 결과가 3이 나온다.
하지만 예제 입력에서 5, 7, 9를 보면 6과 8을 추가하면 5, 6, 7, 8, 9라는 올바른 배열을 얻을 수 있기 때문에 이 방법은 잘못된 방법이다.

그러면 어떻게 풀어야 할까?

우선 기준이 되는 수를 잡는 것은 동일하다. 이때 이 기준으로 잡은 수에서 +4를 해준 수를 구한다.
그 후 기준이 되는 수를 제외한 나머지 수를 탐색하면서 기준이 되는 수보다 크거나 같고 기준이 되는 수에 +4를 해준 수보다 작거나 같은 수가 있다면 카운트를 하나씩 더해준다.

예시를 보면 훨씬 이해하기 쉽다.

예제 입력 1을 보면 배열에는 5, 6, 7이라는 값이 들어가 있다. 이는 이미 정렬되어 있으므로 정렬할 필요가 없다.
그 후 반복문에 들어가는데, 이때 배열의 크기가 5보다 작으므로 기준이 되는 수를 탐색할 반복문의 인덱스를 1로 조정해줄 필요가 있다. 그 후 반복문을 돌면서 기준이 되는 수인 5를 잡고 거기에 +4를 해준 9를 구한다.
두 번째 반복문을 돌면서 탐색하는 수가 5보다 크거나 같고 9보다 작다면 카운트를 하나씩 더해주며 두 번째 반복문이 끝나면 카운트 수를 계속 최댓값으로 유지시킨다. 즉 기준이 되는 수를 포함하여 5, 6, 7은 범위 안에 포함되므로 카운트의 값이 3이며 결과는 5 - 3 = 2가 되는 것이다.

예제 입력 2를 보면 5, 7, 9, 8492, 8493, 192398이 들어가 있다. 정렬되어 있지 않으므로 정렬해주고 반복문에 들어간다.
동일하게 5를 기준으로 잡고 +4를 해준 9를 구한다. 배열의 크기가 5보다 크므로 탐색할 반복문의 인덱스는 입력받은 배열의 사이즈가 된다. 그 후 동일하게 탐색을 해주면 범위 안에 들어가는 수는 5, 7, 9가 되고 5 - 3 = 2라는 결과를 얻는다. 예제 입력 2에서는 배열의 크기가 5보다 크므로 한 번만 도는 것이 아닌 7, 9 ...를 탐색하면서 기준점을 잡고 반복문을 돈다. 돌면서 얻은 카운트 값을 최댓값으로 유지시키고 마지막에 5에서 최대 값을 빼주면 정답!!!!!

 

3. 소스 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public 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));

        List<Integer> numList = new ArrayList<>();
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            numList.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(numList);

        int cnt = 0;
        int minCnt = 0;
        int loopStand = T < 5 ? 1 : T;

        for (int i = 0; i < loopStand; i++) {
            int standardNum = numList.get(i) + 4;

            for (int j = 0; j < T - i; j++) {
                int compareNum = numList.get(i + j);
                if (compareNum >= numList.get(i) && compareNum <= standardNum) {
                    cnt += 1;
                }
            }
            minCnt = Math.max(cnt, minCnt);
            cnt = 0;
        }

        bw.write(Integer.toString(5 - minCnt));
        bw.flush();
        br.close();
    }
}