[Programmers][Swift] 110 옮기기 - Level3

 

[프로그래머스] 110 옮기기[ 링크 ]

간단한 문제 요약

0과 1로 이루어진 어떤 문자열 x에 대해서 x에 있는 "110"을 뽑아, 임의의 위치에 삽입합니다."를 반복하여 만들어진 x를 사전 순으로 만들자. (최대한 작은 수로 만들자)

문제 풀이

110을 전부 추출하고, 나머지 문자열들에 대해서 마지막 원소부터 0이 존재하는지 여부 체크 후 해당 원소 뒤에 붙이거나, 0이 없다면 110 배열을 붙인다면 사전순으로 정렬됨.

 

110을 추출해서 뒤로 옮기거나 앞으로 옮긴 결과.. 110이 이어져있다는게 특징이었는데 규칙 찾기가 어렵다..

 

문제를 풀면서 String.Index를 적극 활용했는데 시간초과가 걸렸다.

let solution: ([String]) -> [String] = { $0.map(minimize) }
func minimize(_ s: String) -> String {
  var ooz = "", notOptimizedString = ""
  for c in s {
    notOptimizedString += String(c)
    if notOptimizedString.hasSuffix("110") {
      notOptimizedString.removeLast(3)
      ooz += "110"
    }
  }
  
  if let zeroIdx = notOptimizedString.lastIndex(of: "0") {
    let insertionIdx = notOptimizedString.index(after: zeroIdx)
    notOptimizedString.insert(contentsOf: ooz, at: insertionIdx)
    return notOptimizedString
  } else {
    return ooz + notOptimizedString
  }
}

 

 

문자열을 다룰 때 String.Index를 활용해 문자열에 대해서 삽입, 삭제연산을 수행하도록 초기에 구현했다. 그리고 시간초과가 나서 52.4/100점을 맞았다.

 

아래 코드 처럼 문자열도 배열로 만들어서 삽입, 삭제하는 연산이 좀 효율적인것 같다.

코드

let solution: ([String]) -> [String] = { $0.map(minimize) }
func minimize(_ s: String) -> String {
  var ooz: [String] = [], notOptimized: [String] = []
  for c in s {
    notOptimized.append(String(c))
    if notOptimized.count >= 3 && notOptimized.suffix(3).elementsEqual(["1","1","0"]) {
      notOptimized.removeLast(3)
      "110".forEach { ooz.append(String($0))}
    }
  }
  
  if let zeroIdx = notOptimized.lastIndex(of: "0") {
    notOptimized.insert(contentsOf: ooz, at: zeroIdx+1)
    return notOptimized.joined()
  } else {
    return (ooz + notOptimized).joined()
  }
}