[백준(BOJ)] 2812 크게 만들기 - 스위프트(Swift)

[Gold III] 크게 만들기 - 2812

문제 링크

성능 요약

메모리: 86700 KB, 시간: 80 ms

분류

자료 구조, 그리디 알고리즘, 스택

문제 설명

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

입력

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

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

출력

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

 

풀이

우선 최댓값을 구하기 위해서 중요한 점은 가장 앞자리의 숫자가 커야한다는 점이라고 생각하여 스택에 차례대로 값들을 저장하였습니다. 

값들을 넣을 때 만약 스택에 있는 값이 들어올 값보다 작다면 해당 숫자를 제거해야 최댓값이 될 수 있습니다. 

따라서 들어올 값과 스택을 비교하여 k만큼 제거되지 않았고, 만약 스택에 있는 값이 들어올 값보다 작다면 제거를 해준 뒤 k를 감소시킵니다. 

 

하지만 위의 방법만으로는 k가 완전하게 제거되지 않는 경우도 있습니다. 

예를 들어
8 2

9 9 9 9 1 1 1 1 

이러한 값이 있다면 k만큼 값을 제거하지 못하게 됩니다.

따라서 k가 남은만큼 스택의 마지막 값을 제거해주면 됩니다. 제거가 되지 않은 값이 있다는 것은 위에 들어온 숫자가 더 작다는 것을 의미하기 때문입니다.

 

이를 그림으로 보면 다음과 같습니다.

풀이 과정

 

다음은 코드입니다.

let nk = readLine()!.split(separator: " ").map { Int($0)! }
let n = nk[0]
var k = nk[1]
let number = Array(readLine()!) // Char로 진행해도 크기 비교 가능 (아스키 코드)
var stack = [Character]()

for num in number {
    while k > 0 && !stack.isEmpty && stack.last! < num {   // k 개수만큼 제거되지 않았고, 해당 스택이 비지 않았거나 스택 마지막 값이 들어온 값보다 작은 경우
        stack.removeLast()  // 해당 값들을 제거
        k -= 1
    }
    stack.append(num)   // 값들 제거 후 추가
}

(0..<k).forEach { _ in  // k만큼 제거되지 않은 경우 -> k만큼 제거되게끔 값들 제거
    stack.removeLast()
}

print(String(stack))    // Char 배열을 한 줄에 나타낼 수 있음

 

해당 문제를 통해

 

1. 꼭 Int와 같은 정수형이 아니라 Char를 통해서도 크기를 비교할 수 있음을 알았습니다. 왜냐하면 Char는 아스키 코드를 가지기 때문입니다.

 

2. 또한 배열을 한 줄로 출력하기 위해 String(stack)과 같은 형식으로 출력하면 된다는 것을 배웠습니다.