백준 13274 수열 Kotlin (정렬)

문제 출처 : https://www.acmicpc.net/problem/13274

13274번: 수열

문제

지훈이는 수열을 좋아한다. 지금 지훈이는 size 가 N 인 수열을 가지고 놀고 있다. 지훈이는 K 개의 쿼리에 따라 수열을 변화시킬 것인데, 쿼리의 형식 및 작업 과정은 다음과 같다.

• L R X : 수열을 오름차순으로 정렬한 결과를 A[1], A[2], … , A[N]이라 하자. 우선 A[L], A[L+1], … , A[R]에 X 만큼 더한다. 그 결과 수열을 다시 오름차순으로 정렬한다.

쿼리들을 순서대로 모두 수행한 후의 수열을 출력하라.

입력

첫째 줄에 N 과 K 가 띄어쓰기로 구분되어 주어진다. (N <= 100000, 1 <= K <= 1000)

둘째 줄에 절댓값이 10^18 이하인, 수열을 이루는 N 개의 숫자가 주어진다.

셋째 줄부터 K+2 번째 줄까지 쿼리 L R X 가 주어진다. (1<=L<=R<=N, |X| <= 10^9)

출력

쿼리들을 순서대로 모두 수행한 후의 수열을 출력한다.

알고리즘 분류

• 구현
• 정렬

풀이

심플한 문제 제목처럼 간단한 풀이로 풀 수 있지만, 실수를 유발하는 문제이다.

N이 100000, k가 1000 이기 때문에,

N을 k번 정렬한다고 하면 1억으로 대략 1초의 시간이 걸린다.

즉, 정렬의 시간 복잡도가 항상 O(N)에 근접해야  O(K*N) == O(1억)으로 통과할 수 있다는 것이다.

 

그러면 어떻게 하면 쿼리마다 정렬을 O(N)의 시간복잡도를 보장할 수 있을까?

결론부터 말하면 본인은 분할 정복 기반 정렬인 병합 정렬의 정복 과정을 이용했다.

 

1 2 3 4 5 6 7 의 리스트에서, left가 3 right가 5, x가 3으로 주어지면, 정렬 전 리스트는

1 2 6 7 8 6 7 이 된다.

 

left에서 right까지의 값을 변경했지만, 여전히 left에서 right 구간은 정렬이 되어있는 상태이다.

이 말인 즉슨,

0~left-1 구간, left ~right 구간, right+1 ~end 구간은 각각 여전히 정렬이 되어있는 상태라는 것이다.

위의 그래프를 이 세 구간으로 나누면 다음과 같다.

 

1 2 6 7 8 6 7 

 

이제 새로운 리스트 temp에 0번부터 6번 인덱스까지 값을 넣을 건데,

세 리스트를 파 vs 빨, 빨 vs 주 순으로 넣을 건데, 각각의 리스트에 맨 앞 숫자들을 서로 비교하면 된다.

이때 사용한 숫자는 제외시켜, 빨간 리스트의 6을 temp에 넣었다면 빨간 리스트의 맨 앞 숫자는 7이 된다.

 

파란색 리스트는 주황색 리스트보단 항상 작음을 보장하지만, 빨간색 리스트와의 값은 비교를 해보아야 한다.(x가 양수가 아니라 음수인 경우)

 

1 vs 6

temp = {1}

파란색 리스트의 첫 번째 인덱스와 빨갈색 리스트의 첫 번째 리스트를 비교하여 더 작은 값인 파란색 리스트의 첫 번째 인덱스 값을 temp의 첫 번째 칸에 넣는다.

 

2 vs 6

temp = {1, 2}

그 다음 파란색 리스트의 두 번째 인덱스와 빨간색 리스트의 첫 번째 리스트를 비교하여 더 작은 값인 파란색 리스트의 두 번째 인덱스 값을 temp의 두 번째 칸에 넣는다.

 

파란색 리스트의 값을 모두 사용했으니, 이제 빨간색 리스트와 주황색 리스트를 비교한다.

 

6 vs 6

값이 같을 땐 아무거나 넣자.

나는 빨간색 리스트의 6을 사용하겠다.

temp = {1, 2, 6}

 

7 vs 6

temp = {1, 2, 6, 6}

 

7 vs 7

temp = {1, 2, 6, 6, 7}

 

8 vs 7

temp = {1, 2, 6, 6, 7, 7}

 

이제 주황색 리스트도 모두 사용하였기 때문에,

빨간색 리스트의 남은 값들을 temp의 뒤에 삽입하면 된다.

 

temp = {1, 2, 6, 6, 7, 7, 8}

 

위의 방식으로 정렬한 결과, 인덱스는 총 n번 만큼 움직였기 때문에 O(N)의 시간 복잡도를 보장하는 것이다.

 

정렬에 대해 공부한 사람은 어디서 본 방식과 비슷하다고 느낄 것이다.

병합/합병 정렬에서 병합하는 부분의 동작과 동일하다.

다만, 병합 정렬에선 두 개의 리스트씩 정렬 및 병합하지만, 위의 방식은,

(1+1)+1 느낌이다.

 

이렇게 정렬된 temp 리스트를 다시 원본 리스트인 arr리스트에 복사해주는데 또 O(N)의 시간 복잡도가 소요된다.

그러면 전체 알고리즘은O(K * 2N)인데, 1초 내에 통과된다.

시간 복잡도는 대락적인 기준이며, 1억의 연산이 1초가 걸린다는 것도 대략적인 측정인 것이 위에서 O(N)과 유사하여야 한다고 한 이유이다.

 

코드

import java.util.*
fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,k) = br.readLine().split(' ').map{it.toInt()}
    val tk = StringTokenizer(br.readLine())
    val arr = LongArray(n){tk.nextToken().toLong()}
    val temp = LongArray(n)
    arr.sort()
    for(i in 0 until k){
        var idx=0
        var (l,r,x) = br.readLine().split(' ').map{it.toInt()}
        l--
        var it =l
        for(i in 0 until l){
            while(it<r && arr[it]+x<=arr[i]){
                temp[idx++]=arr[it++]+x
            }
            temp[idx++]=arr[i]
        }
        for(i in r until n){
            while(it<r && arr[it]+x <=arr[i]){
                temp[idx++]=arr[it++]+x
            }
            temp[idx++]=arr[i]
        }
        while(it<r){
            temp[idx++]=arr[it++]+x
        }
        for(j in 0 until n){
            arr[j] = temp[j]
        }
    }
    for(i in 0 until n){
        write("${arr[i]} ")
    }
    close()
}