백준 2812 크게 만들기

출처: www.acmicpc.net/problem/2812

분류: Greedy

---

접근방식

주어진 수에서 k개를 지워서 가장 큰 수를 만들어야 하는 문제입니다.

앞에서부터 스택에 담는데, 스택의 뒤에서부터 해당 수보다 작은 수는 다 지워내고 추가합니다.

저희는 k개를 지워야 하므로 지울 때마다 k의 개수를 줄여나갑니다.

k가 0이 되었다면 더이상 지울만큼 지웠으므로 그냥 스택에 담아줍니다.

정리해보면 

주어진 문자열에서 현재 확인할 숫자 n을 가지고

스택을 뒤에서부터 확인하면서 크거나 같을 때까지 반복합니다.

// 현재 대상이 되는 수 n
// stack의 뒤에서부터 확인하는 인덱스 i

while i >= 0 {
  if n <= stack[i] {
    // n이 stack의 수 보다 작거나 같으면 그냥 추가
    stack.append(n)
    break
  } else {
    // n이 더 작다면 
    stack.removeLast()
    k -= 1
    i -= 1
    // 다 지워버렸다면 추가해주고 끝냄
    if i == -1 || k == 0 {
    	stack.append(n)
    }
  }
}

 

 

 

해결방법

비교 과정에서 크거나 같은지만 비교하면 되므로 "1", "2" 이런 캐릭터를 굳이 숫자로 변환하지 않고 바로 비교했습니다.

let n = readLine()!.split(separator: " ").map{Int($0)!}
var numStr = readLine()!

var k = n[1]
var cuttedNumber = [Character]()

for originChar in numStr {
  if k == 0 {
    cuttedNumber.append(originChar)
    continue
  }
  
  if cuttedNumber.isEmpty {
    cuttedNumber.append(originChar)
    continue
  }
  
  var idx = cuttedNumber.count-1
  while idx >= 0 {
    if cuttedNumber[idx] >= originChar {
      // 비교대상보다 작거나 같으면 그냥 뒤에 추가
      cuttedNumber.append(originChar)
      break
    } else {
      // 더 크다면 마지막을 잘라냄
      cuttedNumber.removeLast()
      k -= 1
      idx -= 1
      if idx == -1 || k == 0 {
        cuttedNumber.append(originChar)
        break
      }
    }
  }
}

cuttedNumber.enumerated().forEach{ if $0.offset < (n[0]-n[1]) {print($0.element, terminator: "")} }

 

배운점

간단해보이는데, 풀 수 있을 것 같은데!!!!! 

매번 잘 못풀겠네요... 갈 길이 멀군요

하지만 오늘도 조금씩 꾸준히 앞으로...