본문 바로가기
PS/BOJ

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

by Nahwasa 2023. 3. 16.

목차

    문제 : 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);
        }
    }

     

    댓글