[프로그래머스] Swift - 110 옮기기

https://school.programmers.co.kr/learn/courses/30/lessons/77886

프로그래머스

 

2023.08.21 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

• 문자열 x에서 110을 뽑아낸다.
• 뽑아낸 110을 임의의 위치에 다시 삽입한다.
• 이렇게 바뀐 x가 사전 순으로 가장 앞으로 오는 경우의 x를 리턴해야 한다.

여기서 사전 순으로 앞에 온다는 것은 x에서 0이 앞쪽에 많을 때를 의미합니다.

1011과 0111이 있을 때 0111이 1011보다 사전 순으로 앞서는 수입니다.

즉, 우리는 0을 주어진 문자 x에서 최대한 앞쪽으로 보내야 하는 것입니다.

 

문제에서 주어진대로만 해석하면

1. 110을 1개 뽑아냄
2. 알맞은 위치에 110 삽입
3. 1~2번의 작업 반복

이렇게 해석할 수 있지만 이렇게 반복하면 문제를 해결하기 힘듭니다. (실행 시간이 매우 오래 걸림)

하나 떠오른 아이디어는 110을 매번 추출할 필요가 없다는 것입니다.

즉, 0110110111이 주어졌다면 여기서 발생 가능한 110을 우선 모두 제거합니다.

그러면 0111만 남게 됩니다. (연쇄적으로 생기는 110도 모두 제거)

 

원래 0110110111의 숫자 개수가 10개고 0111은 4개이기 때문에 제거된 숫자의 개수는 6개입니다.

즉 110을 총 2번 삭제한 것입니다.

 

이제 우리는 0111에 110을 2번 삽입하면 되는 문제로 바뀌었습니다.

 

여기서 한번 더 아이디어가 필요합니다.

이 문제에는 규칙이 있는데 괜히 조건으로 110을 삽입하라고 제시한 것이 아닙니다.

쌩으로 모든 위치에 110을 삽입해서 사전 순으로 앞인지 비교하는 것은 무조건 시간 초과가 발생합니다.

즉, 규칙을 찾아야합니다.

 

앞서 사전 순으로 앞에 위치시켜려면 0이 문자의 앞쪽에 최대한 많이 배치되어 있어야 한다고 했습니다.

여기서 좀 더 생각해보면 110은 111을 제외하고는 모든 3자리 숫자보다 뒤에 위치해야만 한다는 것입니다.

예를 들어 110은 100 보다 앞에 위치할 수 없습니다. 110100이 100110보다 사전 순이 뒤이기 때문입니다.

 

즉, 110은 111보다만 앞에 위치할 수 있다는 결론이 나옵니다.

여기까지만 아이디어를 도출하면 구현이 어려워집니다.

한 단계 더 생각을 해보면

110을 전부 제거한 x를 removedX라고 했을 때, removedX를 뒤부터 탐색하여 만나는 첫번째 0보다 110이 뒤에 있어야 한다는 규칙이 나옵니다.

 

앞선 예시에 0110110111에서 110을 제거하여 0111로 만들었는데 0111을 뒤에서부터 탐색하여 만나는 첫번째 0 뒤에 110을 몰빵하여 붙이면 정답인 0110110111이 나오게 됩니다.

 

조금만 생각해보면 당연한 결과입니다.

110은 1111보다만 앞에 위치할 수 있다 ➡️ 110은 최대한 뒤쪽에 위치시켜야 한다. ➡️ 뒤에서 부터 탐색했을 때 0을 만난다. ➡️ 해당 0을 포함하여 앞쪽으로 3개의 숫자를 뽑아내면 어떤 경우라도 110보다는 사전순으로 앞이나 같은 위치이다. ➡️ 넣어야 하는 110을 전부 해당 0 뒤에 붙이면 우리가 구하는 답이다.

 

이 흐름입니다. 처음 들으면 이해가 잘 안될 수 있지만 직접 테스트 케이스에 있는 숫자들로 적어보면 그 이유를 알 수 있을 것이라고 생각됩니다.!

 

정리해보면

1. x에서 110을 전부 제거한 removedX 구하기
2. x의 크기와 removedX의 크기를 비교하여 제거된 110의 개수 구하기
3. removedX를 역순으로 탐색하며 0이 처음 발견되면 110을 해당 0 뒤에 전부 삽입
4. 만약 removedX에 0이 1개도 없다면 110은 removedX의 맨 앞에 전부 삽입합니다. (110에는 어쨌든 0이 1개 존재하기 때문에 1로만 이루어진 수보다는 사전 순으로 앞서게 됩니다.)

 

풀이

1. 110을 제거하는 remove110 함수 구현

// O(N)
fileprivate func remove110(_ num: String) -> String {
    var stack = [String]()
    
    for _char in num {
        let char = String(_char)
        if stack.count < 2 {
            stack.append(String(char))
        } else {
            let pop1 = stack.removeLast()
            let pop2 = stack.removeLast()
            let lastThreeWord = pop2 + pop1 + char
            if lastThreeWord != "110" {
                stack.append(contentsOf: [pop2, pop1, char])
            }
        }
    }
    
    return stack.joined()
}

여기서 num이 문자열 x를 의미합니다.

이 함수를 구현하는 방식이 생각보다 중요했습니다. num을 탐색하여 110을 제거하고 제거하고 남은 문자열에서 다시 탐색해서 110을 제거하는 방식을 사용하면 시간 초과에 걸리게 됩니다.

따라서 스택을 활용하여 시간 복잡도를 O(N)으로 낮추는 방식을 사용했습니다.

 

방식

1. num을 순회 하며 char를 받아옴
2. stack에 char를 넣는다.
3. stack에 가장 최근에 넣은 2개와 이제 넣어야 할 char를 비교하여 110이면 제거한다.

이 방식으로 하면 stack에는 110만 전부 제거된 문자열만 남게됩니다. (연쇄적으로 생기는 110도 모두 제거됩니다.)

마치 테트리스처럼 새로 붙은 숫자가 최근에 넣은 숫자와 합쳐져 110을 이루면 삭제하는 로직입니다.

이 방식은 다른 문제에서도 많이 사용될 것 같으니 따로 기억을 해둬야 할 것 같습니다.

 

2. 110을 삽입하는 insert110 구현

// O(N)
fileprivate func insert110(removedNum: String, cnt: Int) -> String {
    let reversedRemovedNum = Array(removedNum).reversed()
    var result = ""
    let target = Array(repeating: "011", count: cnt).joined()
    var isInserted = false
        
    for i in reversedRemovedNum {
        if i == "0" && !isInserted {
            result.append(target)
            isInserted = true
        }
        result.append(i)
    }
    
    if !isInserted {
        result.append(target)
    }
    
    return String(result.reversed())
}

앞서 설명한 방식처럼 removedNum을 역순으로 순회하며 0이 처음 발견되면 110들을 삽입하는 코드입니다.

정확히 말하면 110이 아닌 011을 삽입하고 있는데 그 이유는 역순이기 때문에 나중에 reversed()를 해줘야 해서 거꾸로 넣고 있기 때문입니다.

 

3. solution 함수 구현

fileprivate func solution(_ s:[String]) -> [String] {
    var result = [String]()
    
    for num in s {
        let removedNum = remove110(num)
        let cnt = (num.count - removedNum.count) / 3    // 제거된 110의 수
        
        let insertedNum = insert110(removedNum: removedNum, cnt: cnt)
        result.append(insertedNum)
    }
    
    return result
}

앞서 만든 remove110과 insert110을 사용합니다.

 

 

마무리

엄청나게 복잡한 알고리즘 기법이 필요한 것은 아니었지만 규칙을 찾는 것이 꽤 어려웠던 문제입니다.

110이라는 특수한 수를 조건으로 준 이유를 찾고 정확한 위치에 삽입하는 것이 중요했습니다.

110을 제거하는 로직 또한 시간 초과에 걸리지 않게 구현해야 했습니다.