#1655 가운데를 말해요

문제

---

 

코드

---

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.PriorityQueue

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val sb = StringBuilder()
    val n = br.readLine().toInt()
    val minHeap = PriorityQueue<Int>()
    val maxHeap = PriorityQueue<Int>(reverseOrder())

    for (i in 0..<n) {
        val k = br.readLine().toInt()
        if (maxHeap.isNotEmpty() && maxHeap.peek() < k) { // max ~ min 순
            minHeap.offer(k)
        } else {
            maxHeap.offer(k)
        }

        if (maxHeap.size - minHeap.size > 1) {
            minHeap.offer(maxHeap.poll())
        } else if (minHeap.size > maxHeap.size) {
            maxHeap.offer(minHeap.poll())
        }
        sb.append("${maxHeap.peek()}\n")
    }
    println(sb)
    br.close()
}

 

풀이

---

처음엔 큐를 사용하는것 대신 정렬을 사용해서 풀어도 될 것 같다고 생각했다.

fun main() {
    val n = readln().toInt()
    val numbers = IntArray(n) { 10001 }
    for(i in 0 ..n) {
        numbers[i] = readln().toInt()
        numbers.sort()
        println(numbers[(i)/2])
    }
}

이런 식으로 배열을 가장 큰 수로 지정해두고, 정렬 후 중간 인덱스만을 출력하는 방식으로 구현했다

처음에 구현할 때, 시간 초과가 날 것이라고 생각했는데 메모리 초과 오류가 발생했다

sort를 너무 많이 하게 돼서 발생한 것 같다ㅋㅋ

 

그래서 우선순위 큐 사용 방법을 찾아봤다

java.util의 PriorityQueue 클래스를 사용

 

 

 

priorityQueue 사용법

 

1. 선언

val pq = PriorityQueue<Int>()

 

2. 값 추가

pq.offer(10)

 

3. 값 제거

pq.poll()

 

근데 priorityQueue로 풀어도 index를 통한 접근이 힘들다는 문제가 있다

중간 인덱스로의 접근을 위해 결과를 출력할 때만 list로 변환해서 인덱스로 값을 접근하도록 했는데

우선순위 큐가 힙 구조라서, 실제로 출력하거나 list로 변환했을 땐 힙의 내부 배열을 그대로 출력함

그래서 1, 2, 5를 큐에 넣었을 때 1, 2, 5로 출력되는 것이 아니라 1, 5, 2 으로 출력되는 것

 

따라서 다른 문제 풀이 방법이 필요했다

구글링 하다가 얼떨결에 힌트를 얻어버렸는데, 최소 힙과 최대 힙을 활용하는 문제였다

 

혼자 어떤 식으로 구현해야할지 한참 고민하다가

결국 최소 힙과 최대 힙 관련해서 블로그를 몇개 읽어보았다

 

---

 

조건을 대략적으로 정리해보면

1. 최대 힙의 크기가 최소 힙의 크기보다 1 크거나 같아야 함.

2. 최대 힙의 최대 원소 < 최소 힙의 최소 원소 의 조건을 만족해야 함

3. 최대 힙의 peek가 result

4. 1의 조건을 만족하기 위해 숫자를 최대 힙에 넣었는데, 2의 조건을 만족하지 않는다면 해당 숫자를 최소 힙의 최소 원소와 swap

 

---

 

그래서 구현한 코드가 아래와 같음

import java.util.PriorityQueue

fun main() {
    val n = readln().toInt()
    val minHeap = PriorityQueue<Int>() // 오름차순 -> 최소값 peek
    val maxHeap = PriorityQueue<Int>(reverseOrder()) // 내림차순 -> 최대값 peek

    for (i in 0..<n) {
        val k = readln().toInt()
        if (maxHeap.size - minHeap.size == 1) {
            minHeap.offer(k)
        } else {
            maxHeap.offer(k)
        }
        if (maxHeap.isNotEmpty() && minHeap.isNotEmpty() && maxHeap.peek() > minHeap.peek()) {
            val mintmp = minHeap.poll()
            val maxtmp = maxHeap.poll()
            maxHeap.offer(mintmp)
            minHeap.offer(maxtmp)
        }
        println(maxHeap.peek())
    }
}

이렇게 작성했더니, 시간 초과 오류가 발생했다.

poll 함수의 시간 복잡도는 O(log n) 시간이기 때문에 poll 문제는 아닌 것 같은데,,

 

그래서 조건 1을 기준으로 먼저 값을 넣지 않고, 2를 기준으로 구현해보기로 했다.

fun main() {
    val n = readln().toInt()
    val minHeap = PriorityQueue<Int>()
    val maxHeap = PriorityQueue<Int>(reverseOrder())

    for(i in 0..<n){
        val k = readln().toInt()
        if (maxHeap.isNotEmpty() && maxHeap.peek()<k) { // max ~ min 순
            minHeap.offer(k)
        } else {
            maxHeap.offer(k)
        }

        if (maxHeap.size - minHeap.size > 1) {
            minHeap.offer(maxHeap.poll())
        } else if (minHeap.size - maxHeap.size >=  1) {
            maxHeap.offer(minHeap.poll())
        }

        println(maxHeap.peek())
    }
}

이렇게 구현했는데, 이것 역시 시간초과가 발생함.

 

로직에는 문제가 없어 보이는데,, offer나 poll 자체에 시간 초과가 발생할 문제도 없고,,

for문도 O(n) 밖에 안되기 때문에,,

 

예제를 터미널에 붙여넣기 했을 때, 엔터를 입력하지 않으면 마지막까지 결과 값이 출력되지 않는 것 때문에 시간초과가 나나 싶어서 string 변수를 하나 선언해서, 각 반복문마다 해당 문자열에 추가하고 반복문 종료 후 한꺼번에 출력하는 것으로 수정했다

근데 계속해서 시간 초과가 발생해서, 다른사람들의 java 코드를 살펴보다가 stringBuilder를 발견했다

 

이렇게 하다가 string의 문제점을 발견했다!

이건 따로 블로그에 정리해서 링크를 걸어두겠다

https://devyewon.tistory.com/192

 

 

이것을 수정해도 메모리 초과가 발생해서 어떤 문제인지 또 고민하다가, 예전에 자바로 알고리즘을 풀었을 때 Buffer를 사용했던 기억이 났다. 그래서 이거도 같은 문제인가 싶었다

이것도 차이점을 따로 블로그에 정리해서 링크를 걸어두겠다~

 

 

결국 로직에는 문제가 없었던 걸로,,

 

최종 수정 코드는 위에 코드 부분을 참고