BOJ-2812 크게 만들기 Swift

문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

내가 푼 풀이

- N자리 숫자에서 K개를 지울 때, 가장 큰 수로 만들려면, 앞자리일수록 수가 커야 한다.

- 이 말은 N자리 숫자를 지워서 재배열하는 것이 아닌, 단순히 그 위치에 있는 숫자를 지우기 때문에, 앞자리 쪽일수록 큰 수가 배치되어야 큰 수가 되는 것이다.

- 앞자리 인덱스부터 스택에 담아서, 그다음 인덱스의 숫자가 클 경우, 스택에 들어가 있는 숫자들 중 작은 값들을 모두 지워낸다.

- 예로 스택에 [1,2,3] 이 담겨있을 때, 그다음 숫자가 4라면 스택에 있는 4보다 작은 숫자를 K횟수만큼 빼낸다.

- 위 방법은 만약 숫자가 내림차순이 된 경우, 다음 인덱스와 비교해도, 큰 수가 나오지 않기 때문에

54321 인경우 앞자리부터 이미 큰 값으로 배치가 되어있으므로 K횟수만큼 pop 한다.

 

예제)

7자리 숫자 1231234에서 숫자 3개를 지웠을 때

 

숫자 1 :

• stack: []
• 스택이 비어있으므로 넣는다.

숫자 2 :

• stack: [1]
• 스택에서 2보다 작은 숫자들은 pop 하고, 2를 넣는다
• stack: [2]

숫자 3 :

• stack: [2]
• 스택에서 3보다 작은숫자들은 pop하고, 3을 넣는다.
• stack: [3]

숫자 1 :

• stack: [3]
• 스택에서 1보다 작은숫자들은 없다. 1을 넣는다.
• stack: [3, 1]

숫자 2 :

• stack: [3, 1]
• 스택에서 2보다 작은 숫자 1을 pop하고, 2을 넣는다.
• stack: [3, 2]
• 여기서 3번의 횟수를 모두 사용하였다.

숫자 3 :

• stack: [3, 2]
• 스택에서 3보다 작은숫자 2가 있지만, 이미 제거 횟수를 모두 썼기에, 3을 넣는다.
• stack: [3, 2, 3]

숫자 4 :

• stack: [3, 2, 3]
• 스택에서 4보다 작은 숫자들이 있지만, 이미 제거 횟수를 모두 썼기에, 4를 넣는다.
• stack: [3, 2, 3, 4]

이로써 만들어 낼 수 있는 가장 큰 수는 3234가 된다.

 

위 방식대로 코드로 구현해 보자.

 

import Foundation

let input = readLine()!.split(separator: " ").map{ Int($0)! }
var rmCount = input[1]
var num = readLine()!.map{ Int(String($0))! }
var stack = [Int]()

// 앞자리부터 스택에 넣는다.
// 스택의 맨 뒤가 현재 원소보다 작을 경우, 현재 원소보다 작은값들은 k번 만큼 지워준다.
// 숫자가 내림차순으로 되있는 경우, k번 지울 수 없기에 뒷부분을 남은 횟수만큼 지워준다.
for i in 0..<input[0] {
    if stack.isEmpty {
        stack.append(num[i])
        continue
    }
    while !stack.isEmpty && stack[stack.count - 1] < num[i] && rmCount > 0 {
        rmCount -= 1
        stack.popLast()
    }
    stack.append(num[i])
}

if rmCount > 0 {
    while rmCount > 0 {
        rmCount -= 1
        stack.popLast()
    }
}
print(stack.map{ String($0)}.joined(separator: ""))