[백준 34817] 쉬운 정렬 문제 [Java]

문제

http://boj.ma/34817

요약

• 인접한 요소가 K이하일 때만 swap해서, 오름차순 정렬이 가능한 배열인지 확인하자.
• N ≤ 200,000

---

풀이 과정

아이디어

정렬을 위해 순서를 뒤집어야 하는 쌍 중, 두 값의 차이가 K를 초과하지 않으면 정렬이 가능함을 알 수 있다.

아래는 문제 조건에서 정렬이 가능한 예시이다.

• K = 0, A = [ 0, 9, 9999 ]
• K = 1, A = [ 1, 0, 9999 ]

임의의 위치 i에서 오른쪽에 있는 값 중 가장 작은 값 A[j]가 A[i]의 차가 K를 초과한다면, 그 배열은 정렬이 불가능하다.

인접한 두 요소만 뒤집어 정렬해야 하지만, N ≤ 2e5 이므로, 매 번 오른쪽의 값 중 가장 작은 값을 구할 수 없으므로, 미리 구하자.

int[] suffixMin = new int[A.length];
suffixMin[A.length - 1] = A[A.length - 1];
for (int i = A.length - 2; i >= 0; --i) {
    suffixMin[i] = Math.min(suffixMin[i + 1], A[i]);
}

A[i]가 오른쪽 구간의 가장 작은 값 suffixMin[i + 1]보다 작을 때, 두 수의 차가 K를 초과하는지 검사해주자.

for (int i = 0; i < A.length - 1; ++i) {
    if (A[i] > suffixMin[i + 1] && A[i] - suffixMin[i + 1] > K) {
        return false;
    }
}
return true;

최적화

두 수의 차가 K가 초과하는지 검사하기 위해, 임의의 위치 i에서 오른쪽에 있는 값 중 무조건 가장 작은 값과 비교하지 않아도 된다.

A[i + 1]에 K를 더한 값이, 임의의 위치 i의 왼쪽 영역 중 가장 큰 값 보다 작다면 정렬을 수행할 수 없기 때문이다.

int max = -1;
for (int i = 1; i < A.length; ++i) {
    if (A[i] + K < max) {
        return false;
    }
    if (A[i] > max) max = A[i];
}
return true;

성능 분석

• 시간 복잡도: $O(N)$
• 제출결과: Accepted / 336ms / 38,768MB

---

회고

정렬을 수행하지 않고도, 주어진 교체 알고리즘을 준수하면서 정렬이 가능한지 확인하는 문제였다.

정렬 알고리즘을 사용하는 정렬은 “인접한 두 원소”에 대한 정렬 규칙이 성립이 성립하지 않기에, 효율적인 정렬을 구현하기 보다는 문제 정렬 여부를 구하는데 집중을 하게 되었다.

그 결과 $O(N)$ 풀이를 생각했지만, 오른쪽 구간에서 가장 작은 값을 찾아야 하는 필요성에 대해 다시 생각해보게 되었다.

K = 2, [ 1, 9, 7, 5, 3]의 경우 1과 9는 교체될 수 없는 경우를 생각하며 1은 3과 비교된다면 가능하다 생각했기 때문이다.

하지만 배열은 결국 오름차순 정렬이 되어야 하며, 임의의 위치 i까지의 값 중 가장 큰 값보다 A[i + 1] + K가 작은 경우를 이용해서도 판단할 수 있다는 점을 알게되었다.

이처럼 예외에 대한 테스트 케이스를 어떻게 떠올리냐에 따라 풀이가 더 효율적으로 구상할 수 있음을 알게되었고 앞으로도 문제 풀이 후 다양한 테스트 케이스를 떠올리며 최적화를 수행해야겠다 느꼈다.

---

참고

문제

http://boj.ma/34817

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/34817.java