[Swift] 프로그래머스 월간 코드 챌린지2 110 옮기기

Problem

 

코딩테스트 연습 - 110 옮기기

---

Solution

 

이번 문제의 핵심은 스택을 이용해서 풀어야 하는 것 입니다.

 

1. 문자열의 모든 "110" 삭제해준다.

 

여기서 스택을 사용하지 않으면 4번,18번,19번,21번 에서 시간초과가 나게 됩니다.

 

문자 하나식 쌓으며 가장 마지막 두 글자와 현재 글자를 비교해서 "110" 이라는 문자가 나오면

 

스택의 가장 마지막 두 문자를 지워줍니다.

 

"110"을 지웠을 때 그 이전에 있던 문자와 이후에 있던 문자가 합쳐져서

 

또 "110"이라는 문자열을 만들 수 있으므로 스택을 사용해야 합니다.

 

ex) 111111100 -> 111110 -> 111

 

그리고 나중에 110을 추가해줘야 하므로 더해서 따로 저장해줍니다.

 

func remove110(str:String,add:inout String) -> [String] {
    var stack:[String] = []
    for s in str {
        if stack.count >= 2 && stack[stack.count-2] == "1" && stack[stack.count-1] == "1" && s == "0" {
            stack.removeLast()
            stack.removeLast()
            add += "110"
            continue
        }
        stack.append(String(s))
    }
    return stack
}

 

2. 1에서 "110"을 지운 문자의 가장 마지막 "0"을 찾아낸다.

 

사전에 가장 앞에 오기 위한 규칙은 모든 "110"을 제거한 문자에서 가장 마지막 "0"에 "110"을 더하면 됩니다.

 

고로 가장 마지막 "0"이 있는 index를 찾아줍니다.

 

func findLast0(str:[String]) -> Int {
    for i in stride(from: str.count-1, through: 0, by: -1) {
        if str[i] == "0" {
            return i+1
        }
    }
    return 0
}

 

3. "110"을 지워준 문자열의 가장 마지막 "0"이 있는 인덱스에 "110"들을 추가해준다.

 

"110"을 지울 때 저장해놓은 add를 가장 마지막 "0"이 있는 index에 추가해줍니다.

 

func insert110ToRemoveString(str:String) -> String {
    var add:String = ""
    var removeString = remove110(str: str,add: &add)
    let index = findLast0(str: removeString)
    removeString.insert(add, at: index)
    return removeString.joined()
}

 

4. s에 담긴 모든 문자를 위와 같이 반복해서 반환한다.

 

func solution(_ s:[String]) -> [String] {
    return s.map{insert110ToRemoveString(str: $0)}
}

---

Source Code

 

---

P.S

 

"110"을 지우는 과정에서 스택을 사용하지 않고 while문을 사용하여 110을 지우고 break를 걸고

 

다시 지우고 하면서 "110"이 없을 때까지 반복했더니 8번,19번,21번에서 시간초과가 났다...

 

풀이법에 스택을 사용해야 한다는 것을 보고 해결했는데... 정말 한 끗 차이로 정답인지 아닌지가 갈리는 것 같다...