백준 2812번 - 크게 만들기(Swift)

문제

www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

설명

n과 k를 입력받은 다음 들어오는 N자리 숫자는 Int로 저장하지 않고 인덱스를 통해 숫자 하나하나에 접근하기 위해 Character 배열로 저장한다. 숫자의 왼편부터 제일 오른편 숫자까지 하나씩 검사하며 지금 스택의 top에 있는 숫자와 비교한다. top보다 지금 검사하고 있는 수가 더 크다면 스택에서 top을 pop한 후에 지금 검사하고 있는 수를 집어넣고 k를 1만큼 감소시킨다.

모든 루프를 마친 후 stack의 0번째부터 stack.count - k - 1번째 인덱스에 있는 수들을 하나씩 출력하면 정답이다.

 

코드

첫 제출에는 시간초과가 났었다. swift에 익숙하지 않아서 어디서 시간초과가 났는지 알아맞추기가 힘들었다. 대충 의심가는 부분이 하나 있었는데, 내가 numbers를 [Character]이 아닌 String 타입으로 저장했기 때문에 numbers\[numbers.index(numbers.startIndex, offsetBy: i)\] 요따구로 접근했었는데, 여기서 인덱스 계산하다가 시간 초과가 나는 것 같았다.

Array(readLine()!)을 통해 String?을 [Character]로 만들어 숫자 인덱스로 접근할 수 있게 고치니 AC 받았다.

// AC
var top = 0
var stack: [Character] = []

let inputValues = readLine()!.split(separator: " ").map { Int($0)! }
var n: Int = inputValues[0]
var k: Int = inputValues[1]
var numbers: [Character] = Array(readLine()!) // 문자열을 문자 배열로 만들어 준다.
for i in 0...n-1 {
    while k > 0 && !stack.isEmpty && stack.last! < numbers[i] {
        stack.popLast()
        k -= 1
    }
    stack.append(numbers[i])
}

for i in 0...(stack.count - k - 1) {
    print(stack[i], terminator: "")
}

// TLE
import Foundation

var top = 0
var stack: [Character] = []

let inputValues = readLine()!.split(separator: " ").map { Int($0)! }
var n: Int = inputValues[0]
var k: Int = inputValues[1]
var numbers: String = readLine()!

for i in 0...n-1 {
    while k != 0 && !stack.isEmpty && stack.last! < numbers[numbers.index(numbers.startIndex, offsetBy: i)] {
        stack.popLast()
        k -= 1
    }
    stack.append(numbers[numbers.index(numbers.startIndex, offsetBy: i)])
}

for i in 0...(stack.count - k - 1) {
    print(stack[i], terminator: "")
}