[Boj_22963] 3초 정렬

📎 문제 링크

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

 

▸ 문제

지금 여러분이 평화롭게 문제를 보고 있는 사이, 이미 강당 밖에는 극단 원리주의 민초파 테러리스트 김준원이 학교를 점령했다.

입력받은 수열을 3초 안에 오름차순으로 정렬된 상태로 만들지 않으면 강당에 설치해놓은 민초 폭탄이 터진다.

당신은 수열의 어떤 원소 Ai를 다른 수 X로 바꿀 수 있다.

이 연산에는 1초가 걸린다.

3...

2...

1...

 

▸ 입력

첫째 줄에 당신이 정렬된 상태로 만들어야 하는 수열의 길이 N이 주어진다.

둘째 줄에 수열의 원소들을 나타내는 N개의 정수 A1,A2,⋯,AN이 공백으로 구분되어 주어진다.

 

▸ 출력

3번의 연산 안에 수열을 오름차순으로 정렬된 상태로 만들 수 있으면,

• 첫째 줄에 YES를 출력한다.
• 둘째 줄부터, 수열을 정렬된 상태로 만들 수 있는 방법을 다음과 같은 형태로 출력한다.
  • 첫째 줄에, 연산 횟수 K를 출력한다.
  • 이후, K개의 줄에 걸쳐, 적용할 연산을 순서대로 출력한다.
    구체적으로, 각 줄에 두 정수 i와 X를 출력한다. 이는, 원소 Ai를 X로 바꾸는 연산을 의미한다. (1≤i≤N, 1≤X≤1000000000)
    연산의 횟수를 최소화할 필요가 없으며, 가능한 방법이 여럿 있으면 아무 방법이나 하나 출력해도 괜찮다. 같은 원소를 여러 번 수정해도 된다.
    3번의 연산 안에 수열을 오름차순으로 정렬된 상태로 만들 수 없으면,
• 첫째 줄에 NO를 출력한다.

 

▸ 제한

• 1≤N≤200000
•  1≤Ai≤1000000000 (1≤i≤N)
• 이미 오름차순으로 정렬된 수열은 주어지지 않는다.

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 1
• 🔔  문제 유형 : 다이나믹 프로그래밍, 가장 긴 증가하는 부분 수열: o(n log n)
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

먼저, 조건에 맞게 수열의 길이 N과 수열 A를 입력받았다.

이때, 수열의 마지막 값이 항상 최댓값이라는 보장이 없으므로, 배열의 크기를 n+1로 설정하고 끝 값을 최댓값으로 설정했다.

 

그리고 연산 횟수를 구하기 위해 이분 탐색을 활용하여 LIS의 길이를 계산했다.

수열의 길이 N에서 LIS의 길이를 빼면, 수열 A를 오름차순으로 만들기 위한 최소 연산 횟수를 구할 수 있다.

 

연산 횟수가 3보다 크다면, 3번의 연산 안에 수열을 오름차순으로 정렬하는 것이 불가능하므로 "NO"를 출력한다.

 

반대로, 3번의 연산 안에 수열을 정렬할 수 있다면, "YES"를 출력한 후 연산 횟수 K와 변경할 인덱스 및 값을 출력한다.

 

변경할 인덱스와 값을 찾기 위해, length 배열을 활용하여 LIS에 포함된 원소들을 역추적한다.

length[i]는 A[i]가 LIS에서 몇 번째 요소인지 나타내므로, 이를 역순으로 탐색하며  LIS 원소들을 저장한다.

이렇게 구한 LIS 원소와 원래 배열을 비교하여, LIS에 속하지 않은 원소들을 찾아 적절한 값으로 변경한다.

 

배열을 역순으로 탐색하며,

현재 원소 A[i]가 LIS의 해당 위치 값과 같다면 그대로 둔다.

그렇지 않다면, 바로 다음 원소(A[i+1])로 변경하여 오름차순을 유지한다.

 

변경된 연산을 기록하여 출력하면 문제를 해결할 수 있다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 41904KB
시간 : 304ms

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

public class Main {
    static int n;
    static int[] A, length;
    static final int MAX = 1000000000;
    static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine()); // 수열의 길이
        A = new int[n+1]; // 수열
        length = new int[n]; // 각 원소가 LIS의 몇 번째 위치인지 저장
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        A[n] = MAX;

        // 연산 횟수 구하기
        int lisCnt = getLis();
        int k = n - lisCnt; // 연산 횟수

        // 3번의 연산으로 오름차순을 만들 수 없음
        if (k > 3) {
            System.out.println("NO");
            return;
        }

        // 3번의 연산으로 오름차순을 만들 수 있음
        StringBuilder sb = new StringBuilder();
        sb.append("YES").append("\n").append(k).append("\n");

        int cnt = lisCnt;
        int[] lis = new int[n];
        for (int i = n-1; i >= 0; i--) {
            if (length[i] == cnt) {
                lis[cnt--] = A[i];
            }
        }

        cnt = lisCnt;
        for (int i = n-1; i >= 0; i--) {
            if (A[i] == lis[cnt]) {
                cnt--;
                continue;
            }

            int x = A[i+1];
            sb.append(i+1).append(" ").append(x).append("\n");
            A[i] = x;
        }

        System.out.println(sb.toString());
    }

    private static int getLis() {
        int[] lis = new int[n+1];
        int len = 0, idx;

        Arrays.fill(lis, INF);
        lis[0] = 0;

        for (int i = 0; i < n; i++) {
            idx = binarySearch(0, len+1, A[i], lis);
            lis[idx] = A[i];
            length[i] = idx;
            len = Math.max(len, idx);
        }

        return len;
    }

    private static int binarySearch(int start, int end, int target, int[] lis) {
        int mid;
        while (start < end) {
            mid = start + (end-start) / 2;
            if (lis[mid] <= target) start = mid+1;
            else end = mid;
        }

        return end;
    }
}

 

어렵다.. 너무 어렵다.. 다른 사람의 풀이를 참고해서 풀었는데도 이해가 안 가서 힘겹게 해결했다...
블로그에 포스팅하려고 다시 문제를 풀고 풀이 과정을 적으면서 많이 정리됐지만
일주일 뒤에 꼭 다시 풀어봐야지... 😂😭

 

 

 

 

 

📃 reference

• https://koder0205.tistory.com/229