알고리즘) 백준 11279번 최대힙 Swift

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

11279번: 최대 힙

---

예제

입력	출력
13 0 1 2 0 0 3 2 1 0 0 0 0 0	0 2 1 3 2 1 0 0

 

---

문제 접근

처음엔 아래 코드와 같이 작성했습니다.

1. 자연수 입력 시 배열에 자연수를 넣는다.
2. 0 입력 시 배열을 오름차순으로 정렬하여 마지막 값을 빼내어 출력한다. 

⬇️⬇️⬇️

let N = Int(readLine()!)!
var arr = [Int]()

for _ in 0..<N {
	let x = Int(readLine()!)!
    if x == 0 {
    	arr.sort()
        print(arr.popLast() ?? 0)
    } else {
        arr.append(x)
    }
}

sort는 시간복잡도가 O(N log N) 이고 popLast는 O(1) 이기 때문에 그래도 통과할 거라 생각했습니다.
하지만 시간 제한은 1초밖에 되지 않아 시간초과 발생했습니다.

화려하게(?) API를 사용하면 시간초과를 피하기 어렵습니다. 단순하게 접근해 보았습니다.

1. for문을 돌려 최대 값과 배열의 위치를 찾아냅니다.
2. 최대값을 꼭 제거할 필요는 없으므로 제일 작은 값(자연수만 추가하므로 0)을 넣습니다.

늘 생각하는 건데 배열에 넣어라, 빼라 써 있어도 그대로 구현하면 시간초과나 메모리초과가 발생하는 것 같습니다.
조금만 다르게 생각하면 코드가 깔끔하진 않아도 좋은 결과가 나오네요.

 

풀이