[백준] 7570 - 줄 세우기 (자바 Java)

[Gold III] 줄 세우기 - 7570

문제 링크

성능 요약

메모리: 208284 KB, 시간: 800 ms

분류

다이나믹 프로그래밍(dp), 그리디 알고리즘(greedy)

문제 설명

대한 어린이집에 올해 입학한 어린이들이 놀이터에 한 줄로 서있다. 모든 어린이들에게는 입학할 때 주어진 번호가 있고 모두 옷에 번호표를 달고 있다. 그런데 어린이들은 아직 번호 순서대로 줄을 잘 서지 못하므로 선생님이 다음과 같은 방법을 사용해서 번호순서대로 줄을 세우려고 한다.

방법: 줄 서있는 어린이 중 한 명을 선택하여 제일 앞이나 제일 뒤로 보낸다.

위의 방법을 사용할 때 어린이가 이동해서 빈자리가 생기는 경우에는 빈자리의 뒤에 있는 어린이들이 한 걸음씩 앞으로 걸어와서 빈자리를 메꾼다.

예를 들어, 5명의 어린이들에게 1부터 5까지의 번호가 주어져 있고, 다음과 같은 순서로 줄 서있다고 하자.

5 2 4 1 3

위 방법을 이용해서 다음과 같이 번호순서대로 줄을 세울 수 있다.

1. 1번 어린이를 제일 앞으로 보낸다. (5 2 4 1 3 → 1 5 2 4 3)
2. 4번 어린이를 제일 뒤로 보낸다. (1 5 2 4 3 → 1 5 2 3 4)
3. 5번 어린이를 제일 뒤로 보낸다. (1 5 2 3 4 → 1 2 3 4 5)

위의 예에서는 세 명의 어린이를 제일 앞이나 제일 뒤로 보내 번호순서대로 줄을 세웠다. 그리고 두 명 이하의 어린이를 제일 앞이나 제일 뒤로 보내는 방법으로는 번호순서대로 줄을 세울 수 없다. 그러므로 이 경우에는 최소한 세 명의 어린이를 이동하여야 번호순서대로 줄을 세울 수 있다.

이 문제는 처음에 줄서있는 상태에서 위 방법을 이용해서 번호순서대로 줄을 세울 때 앞이나 뒤로 보내는 어린이 수의 최솟값을 찾는 것이다.

입력

입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하나씩 들어있다. 단, 어린이 수는 1이상 1,000,000이하의 정수로 제한되고, 어린이 수가 N이면 어린이들의 번호는 1부터 N까지의 정수이다.

출력

입력에서 주어진 어린이들의 줄에 대해 번호순서대로 줄을 세우기 위해 제일 앞이나 제일 뒤로 보내는 어린이 수의 최솟값을 출력해야 한다.

---

케이스를 몇 개 찾다가 가장 긴 연속된 수열의 개수를 찾으면 된다는 것을 깨달았다.

 

2 4 3 1 5 가 있을 때, 가장 긴 연속된 수열은 [2, 3] 또는 [4, 5]이다.

 

이 수를 제외하고 나머지를 앞, 또는 뒤로 보내면 번호 순서대로 줄을 세울 수 있다.

 

처음에는 O(N^2)의 시간복잡도를 가지는 알고리즘으로, 연속된 수열을 찾으려고 했는데, N이 최대 1,000,000이어서 시간 초과가 났다.

 

그래서 좀 더 효율적인 방법을 찾았는데, 답을 제출하고 보니 이것보다 간단한 방법이 있었다.

 

아무튼 내 풀이는 HashMap을 이용해서 자신보다 작은 값이 map에 포함되어 있을 경우, 그 값+1한 것을 다시 map에 넣었다.

 

포함되지 않았을 경우에는 이미 val+1이 방문되었다면, 1 이상으로 연속된 수열의 길이가 나올 가능성이 없기 때문에 map에 추가하지 않았다.

 

이렇게 나름대로 효율적으로 구현한다고 해서, 문제를 통과할 수는 있었다.

 

보다 간단한 풀이는 dp를 활용해서 입력될 때마다 dp[i] = dp[i-1]+1을 해주는 것이었다.

 

i-1이 이미 입력되었다면 dp는 1일 것이고, 거기에 1을 더하게 될 것이다. 만약 앞에 i-1이 존재하지 않는다면 dp 값은 0이니까 길이는 1이 될 것이다.

 

쉬운 방법을 생각해내는 것은 정말 어려운 것 같다..~

 

package BOJ.Gold.g3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_7570_줄세우기 {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());


        int ans = 1;
        HashMap<Integer, Integer> map = new HashMap<>();
        boolean[] visited = new boolean[N + 1];
        for (int i = 0; i < N; i++) {
            int val = arr[i];
            visited[val] = true;
            if (map.containsKey(val - 1)) {
                map.put(val, map.get(val - 1) + 1);
                ans = Math.max(map.get(val - 1) + 1, ans);
                map.remove(val - 1);
            } else {
                if (val == N || visited[val + 1]) {
                    continue;
                }
                map.put(val, 1);
            }

        }
        System.out.println(N - ans);


    }

}