Kotlin] 백준 1655번 문제 풀이

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

1655번: 가운데를 말해요

이 문제는 도저히 모르겠어서... 다른 분의 도움을 빌림 ㅇ.<

 

https://hongcoding.tistory.com/93

[백준] 1655 가운데를 말해요 (Python 파이썬)

 

이 문제는 끊임없이 가운데를 유지해야하는 문제이다.

즉, 가운데를 쫙 갈라놓고, 양쪽으로 값을 쏙쏙 집어넣으면 되는 문제이다. 

그래서 알아서 값을 정렬해줄 방법이 필요하다. 그런데 일일히 정렬하면 시간제한에 걸려버리므로, Heap 방식으로 우선순위를 정렬해줄 우선순위 큐를 이용한다.

기본적으로 큐는 선입선출이 원칙이지만, 우선순위 큐는 순서를 정해두면 해당 순서대로 정렬한다. 코틀린에서는 PriorityQueue 클래스로 제공하고 있다.

근데 그렇게 무지성으로 오른쪽 왼쪽 집어넣으면 종내에는 그냥 갈라놓은 것 밖에 더 되냐고? 그렇기 때문에 값을 넣을때마다 양 끝점을 비교해서 왼쪽에서 가장 큰 값보다 오른쪽에서 가장 작은 값이 더 작다면 변경해주는 작업이 필요하다.

그리고 (임의로 정하는 거지만) 어느 쪽을 기준값으로 정할지 선택하여 해당 peek를 중간값으로 설정한다. 이 문제에선 짝수일 때 가장 작은 값을 선택해야 하므로 왼쪽부터 값을 넣고, 왼쪽의 peek를 중간값으로 지정한다.

또한, peek로 꺼냈을 때 가장 왼쪽에선 가장 큰 값을, 오른쪽에선 가장 작은 값을 꺼내야하므로 왼쪽은 내림차순 정렬을, 오른쪽은 오름차순 정렬을 해야한다.

예시를 보자. 표에서 중간 줄이 그어진 곳이 중간값이다.

7
1
5
2
10
-99
7
5

 

1회차 - [1]

1(peek)

 

2회차 - [1,5]

1(peek)

5(peek)

 

3회차 - [1, 2, 5]

1

2(peek)

5(peek)

 

4회차 - [1, 2, 5, 10]

1

2(peek)

5(peek)

10

 

5회차 - [-99, 1, 2, 5, 10]

-99

1

2(peek)

5(peek)

10

 

6회차 - [-99, 1, 2, 5, 7, 10]

-99

1

2(peek)

5(peek)

7

10

 

7회차 - [-99, 1, 2, 5, 5, 7, 10]

-99

1

2

5(peek)

5(peek)

7

10

1 1 2 2 2 2 5 로 잘 구해진 것을 볼 수 있다 .

 

 

마아아아아안 약에 다음에 -25가 들어왔다 가정해보자.

8회차 - [-99, -25, 1, 2, 5, 5, 7, 10]

-99

1

2

5(peek)

-25(peek)

5

7

10

그럼 왼쪽의 peak보다 오른쪽의 peak가 값이 더 낮은 상황이 발생한다. 

이 때는 서로의 큐에서 poll을 통해 각 값을 추출한 뒤 add 하면 우선순위 큐의 구조상 정렬을 맞추게 된다.

-99

1

2

-25(peek)

5(peek)

5

7

10

 (우선순위 큐의 정렬)

-99

-25

1

2(peek)

5(peek)

5

7

10

 

따라서, 다음 중간값은 2가 된다.

 

이를 코드로 쓰면,

import java.util.PriorityQueue

fun main(args: Array<String>) {
    question1655()
}

fun question1655() {
    val count = readln().toInt()
    val minQueue = PriorityQueue<Int>(reverseOrder())
    val maxQueue = PriorityQueue<Int>()
    val stringBuilder = StringBuilder()

    for(i in 1 .. count) {
        val number = readln().toInt()

        if(minQueue.size == maxQueue.size) {
            minQueue.add(number)
        } else {
            maxQueue.add(number)
        }

        if(minQueue.isNotEmpty() && maxQueue.isNotEmpty()) {
            if(minQueue.peek() > maxQueue.peek()) {
                val minPop = minQueue.poll()
                val maxPop = maxQueue.poll()

                maxQueue.add(minPop)
                minQueue.add(maxPop)
            }
        }

        stringBuilder.append("${minQueue.peek()}\n")

    }

    println(stringBuilder)

}

 

(눈물나는 시간초과 ^-ㅠ .. 0.1초 너무한거 아니냐고)