[백준 - 1898번] 이전 수열은 어떤 수열일까? - Java

문제 링크

https://solved.ac/contribute/1898/list

문제

티어: 골드 2
알고리즘: 그리디

입력

첫 줄에 수열의 길이 n이 주어진다. (3 ≤ n ≤ 50,000) 이후 n개의 줄에 수열을 이루는 수가 한 개씩 차례대로 주어진다.

출력

n개의 줄에 걸쳐, 조건을 만족하는 수열 중 오름차순으로 가장 앞에 오는 수열을 출력한다.

풀이

조건을 만족하면서 오름차순으로 가장 앞에 오는 수열을 출력해야 한다.

내가 푼 방식은 다음과 같다.
N이 8인 경우 8부터 1까지 반복한다.

8을 기존 수열에 어떤 수에 부여하는 것이 오름차순으로 가장 앞에 오는 수열로 만들까?
일단 8은 2번 조건을 만족해야 해서 7 8 중 하나에 부여해야 한다.

그러면 기존 수열에 7, 8의 위치를 파악한다. 더 작은 수를 만들어야 하기 때문에 둘 중 더 뒤에 위치한 7에 8을 부여한다.

다음 7은 기존 수열에 어떤 수에 부여하는 것이 오름차순으로 가장 앞에 오는 수열로 만들까?
7은 2번 조건을 만족해야하기 때문에 6 7 8 중 하나에 부여해야 한다.
여기서 7에는 8을 이미 부여했기 때문에 최종 후보는 6 8이다.

그런데 여기서 중요한 점은 8에는 무조건 7를 부여해야 한다. 왜냐하면 다음 수부터는 2번 조건을 만족하는 값이 없기 때문이다. 그래서 이러한 경우에는 위치를 따지지 않는다.

이를 구현하는 것은 어렵지 않다. 각 넘버는 3개나 2개의 숫자 중 하나를 부여받을 수 있다.

예를 들어 8은 -> 7 8
7은 -> 6 7 8이다.

앞에서 8를 7에 부여했기 때문에
8은 -> 7이 되며, 하나만 남아 있는 경우는 위치를 따지지 않고 부여하면 된다.

그래서
8
8
5
7
3
6
4
2
1

이 입력의 대한 출력은
7
4
8
2
6
5
3
1
이며, 그리디 풀이의 시간 복잡도는 O(N)이다.

소스 코드

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

public class Main {
    static int N;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      int[] per = new int[N];
      int[][] nums = new int[N + 1][2]; //0 -> index, 1 -> 남은 수
      nums[0][0] = -1;
      int[] changeNum = new int[N + 1];
      for(int i=0; i<N; i++) {
          int num = Integer.parseInt(br.readLine());
          per[i] = num;
          nums[num][0] = i;
          if(num == 1 || num == N) {
              nums[num][1] = 2;
          } else {
              nums[num][1] = 3;
          }
      }
      
      for(int i=N; i>=1; i--) {
          ArrayList<Integer> list = new ArrayList<>();
          if(i == N) {
              fillList(N, N-1, list, changeNum);
          } else if(i == 1) {
              fillList(2, 1, list, changeNum);
          } else {
              fillList(i + 1, i - 1, list, changeNum);
          }
          
          int num = 0;
          for(int j=0; j<list.size(); j++) {
              if(nums[list.get(j)][1] == 1) {
                  //하나 남은 경우
                  num = list.get(j);
                  break;
              }
              if(nums[num][0] < nums[list.get(j)][0]) {
                  num = list.get(j);
              }
          }
          changeNum[num] = i;
          
          for(int j=i + 1; j>= i - 1; j--) {
              if(j != N + 1) {
                  nums[j][1] -= 1;
              }
          }
      }
      
      StringBuilder sb = new StringBuilder();
      for(int i=0; i<N; i++) {
          sb.append(changeNum[per[i]]).append("\n");
      }
      System.out.println(sb.toString().trim());
  }
  
  static void fillList(int start, int end, ArrayList<Integer> list, int[] changeNum) {
      for(int i=start; i>=end; i--) {
          if(changeNum[i] == 0) {
              list.add(i);
          }
      }
  }
}