백준 - 크게 만들기(Swift)

백준 - 크게 만들기(Swift)

 

 

 문제 설명

 

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

2812번: 크게 만들기

 

 나의 풀이

 

처음에는 큰 숫자가 앞에 있어야한다는 것을 알았기에 투 포인터로 이용해서 문제를 풀었다. 하지만 500,000인 상태에서 투 포인터를 계속 앞으로 리셋하면서 돌리는 것은 말도안되는 시간복잡도를 결과로 내놓는다.

 

이 때문에 다른 풀이를 참고하다가 스택을 사용하는 것을 알게되었다.

스택이라는 추가적인 자료구조를 사용함으로써 새로 들어오는 값에 대해서는 마지막값과 비교하는 로직을 담을 수 있게 되었다. 

(기존의 투 포인터는 한번 숫자를 빼면 처음부터 다시 시작했기에 시간초과가 나왔다.)

 

마지막에 0..<k에 대해서 또 제거하는 이유는 다음값이 더 큰 값은 없으면서 제거를 해야할 때이기 때문에 맨 마지막이 제일 작은 숫자이므로 지우는 것이다.

 

 

 

import Foundation

let input = readLine()!.components(separatedBy:" ").map{Int($0)!}

let n = input[0]
var k = input[1]

var arr = readLine()!.map{Int(String($0))!}

var stack: [Int] = []

for x in arr {
    while k > 0 && !stack.isEmpty && stack.last! < x {
        stack.removeLast()
        k -= 1
    }
    stack.append(x)
}

(0..<k).forEach { _ in
    stack.removeLast()
}

print(stack.map{String($0)}.joined())

 

 

 

 

 피드백

 

스택 자료구조를 왜 생각하지 못했나 싶다.. 좀 더 유연하게 생각하는 능력을 길러야겠다.