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

목차

문제 : boj7570

 

 

필요 알고리즘

• 그리디 알고리즘
  
  • 모든 경우에 적용되는 규칙을 적용해 푸는 그리디 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  이게 특정 위치의 수를 원하는 위치로 보낼 수 있었으면 좀 쉬웠겠는데, 맨 앞이나 맨 뒤로만 보낼 수 있는 부분 때문에 좀 생각하기 어려워지는 것 같다.

 

  내가 정한 규칙은, 가장 긴 +1씩 증가하는 부분 수열을 고정시키고 나머지 애들을 어떻게든 움직여보는 것이다. 어린이 숫자가 +1씩 증가하는 순서대로 연속해서 증가하는 부분 수열(떨어져있어도 상관없음)을 뜻한다. 이건 움직일 어린이는 마음대로 선택할 수 있지만, 움직일 수 있는 위치는 맨 앞이나 맨 뒤만 가능하므로 정한 규칙이다.

 

  무슨말이냐면, 아래의 예시를 보자. 여기서 +1씩 증가하는 부분수열은 '1 -> 2 -> 3'과 '4 -> 5 -> 6' 이다. 둘 다 길이가 동일하므로 둘 중 하나를 고정시킨 후 나머지들을 앞쪽부터 혹은 뒤쪽부터 순서를 맞춰주면 된다. '4, 5, 6'을 고정시켰다고 해보자. 그럼 '3'을 맨 앞으로 -> '2'를 맨 앞으로 -> '1'을 맨 앞으로 보내면 된다.

6
4 5 6 1 2 3

 

  하나 더 보자. 아래의 경우 '1 -> 2'와 '3 -> 4 -> 5 -> 6'이 +1씩 증가하는 부분수열이다. 이 중 '3 -> 4 -> 5 -> 6'이 더 기니깐 이걸 고정하고 나머지 1과 2를 앞이나 뒤로 움직여 순서를 맞춰주면 된다. 이 때, 어떻게 맞추는진 신경쓰지 않아도 된다. 그냥 가장 긴 연속하는 증가하는 부분수열에 포함되지 않는 애들은 전부 움직여야만 하고, 방법이야 어떻든 무조건 1,2,3,4,5,6 순서대로 만들 수 있다.

6
3 1 4 5 2 6

 

  참고로, 단순히 가장 긴 증가하는 부분 수열은 규칙이 될 수 없음을 다음을 통해 알 수 있다. 아래에서 가장 긴 +1씩 증가하는 부분 수열은 '1 -> 2 -> 3', '4 -> 5' 라서 답은 2가 된다. 그냥 가장 긴 증가하는 부분 수열은 '1 -> 2 -> 4 -> 5' 이지만 이걸 고르면 답이 될 수 없음을 알 수 있다.

5
1 2 4 3 5

 

 

  그럼 말한대로 구현을 해주면 된다. 맨 아래 첨부된 코드의 로직을 말로 써보면

1. arr[] 배열에 각 어린이 숫자가 입력으로 들어온 위치를 기입한다. 즉, 어린이 숫자 기준으로 입력 들어온 순서를 정렬한 셈이다.

2. arr[] 배열을 순서대로 보면서 입력 들어온 순서가 연속으로 증가하는 가장 긴 구간을 찾으면 그게 '가장 긴 +1씩 증가하는 부분 수열'의 길이이다.

 

코드 : github

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        if (n == 1) {
            System.out.println(0);
            return;
        }

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

        int max = 1;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (arr[i] > arr[i-1]) {
                if (++cnt > max)
                    max = cnt;
            } else {
                cnt = 1;
            }
        }
        System.out.println(n-max);
    }
}