문제 링크

문제 풀이 아이디어

사전 순

문제에서 제시한 목표는 110과 111의 위치를 바꾸어서 사전순으로 가장 앞에 오는 문자열을 찾아서 return 하는 것입니다. 같은 갯수의 0과 1로 사전 순으로 가장 앞에 오는 문자열을 만들기 위해서는 0을 최대한 앞에 배치하고 1을 최대한 뒤에 배치해야 합니다.

따라서 110과 111의 위치를 바꿀 때는 앞에 있는 111을 뒤로 보내고 뒤에 있는 110을 앞으로 보내야 합니다.

시간 복잡도

s의 길이가 최대 1,000,000이고 s의 원소 (= 문자열)의 길이도 최대 1,000,000입니다. 따라서 매번 완전탐색을 하면서 110과 111을 찾아서 그때그때 자리를 바꾸어 주면 시간초과입니다. 문자열을 1번만 순회해서 문제를 풀어야 합니다.

110을 일단 전부 찾는다.

문자열을 1번만 순회한다는 조건이 들어가므로 110과 111을 그때그때 자리를 바꾸어주지 않고 일단 110을 전부 찾겠습니다. 그리고 나서 111앞에 110를 모두 넣어주면 되는 것입니다. 그렇게 하면 모든 110과 111을 순차적으로 교환해주는 것과 동일한 결과가 나옵니다.

110을 찾기 위해서는 stack을 사용해야 합니다. 예를 들어 11”110”0에서 중간에 위치한 “110”을 빼면 또 다른 110이 나오기 때문에 문자열을 순차적으로 탐색해서는 모든 110을 찾을 수 없습니다. 문자열을 처음부터 stack에 넣으면서 110을 찾으면 pop하는 방식으로 110을 모두 찾습니다.

110들을 배치한다.

case 1) 111 앞에 배치한다.

자 이제 남은 문자열의 111을 찾아서 그 앞에 110들을 배치하면 됩니다. 하지만 만약에 111이 여러개 있다면 어떻게 해야할까요? 가장 처음 확인했듯이 사전 순으로 가장 앞에 오는 문자열을 만들기 위해서는 111을 최대한 뒤로 110을 최대한 앞으로 보내야 합니다. 따라서 복수의 111이 있다면 가장 앞에 위치한 111 앞에 110들을 배치합니다.

case 2) 111이 없다면?

만약에 남은 문자열에 111이 없다면 어떻게 해야할까요? 이 경우에는 가장 사전 순으로 빠른 문자열을 만들어주기 위해서는 가장 뒤에 있는 문자열 0을 찾고 그 뒤에 110들을 붙여주면 됩니다. 문자열 0이 최대한 앞에 있어야 사전 순으로 빠른 문자열을 만들 수 있기 때문입니다.

case 1 + 2) 가장 뒤에 있는 문자열 0뒤에 배치한다

사실 1번 케이스와 2번 케이스 모두 가장 뒤에 있는 문자열 0뒤에 배치하면 됩니다. 1번 케이스의 경우 가장 앞의 111 앞에 배치한다고 했는데요. 사실 가장 앞에 있는 111 뒤에는 0이 올 수 없습니다. 만약 0이 오게 되면 “110”이 되기 때문입니다. 이런 케이스는 110을 전부 찾아내서 pop한 경우에는 생길 수 없겠죠.

따라서 우리는 111은 신경쓰지 말고 가장 뒤에있는 0 뒤에 110들을 붙여주면 됩니다.

코드

func solution(_ s:[String]) -> [String] {
    
    // 각각의 문자열을 [String]으로 바꾼다.
    let strings = s.map { $0.map { String($0) } }
    
    // 정답 배열
    var ans = [String]()
    
    // 각각 string에 대해서 정답 구하기
    for string in strings {
        // 110을 제외한 문자열을 담을 stack
        var stack = [String]()
        // 110의 갯수
        var numOf110 = 0
        
        // 모든 문자열을 순회하면서
        for s in string {
            // 현재 문자열이 110이면 (= stack의 길이 2이상, 현재 s가 0, stack의 마지막 2개의 문자가 1인 경우)
            if stack.count >= 2 && (stack[stack.count - 2] == "1" && stack[stack.count - 1] == "1" && s == "0") {
                _ = stack.popLast()
                _ = stack.popLast()
                numOf110 += 1
            // 아니면 push
            } else {
                stack.append(s)
            }
        }
        
        // 마지막 0의 위치를 찾는다. (-> 그 뒤에 110들을 위치해야 하므로)
        var lastZero = -1
        
        for i in (0..<stack.count).reversed() {
            if stack[i] == "0" {
                lastZero = i
                break
            }
        }
        
        // 110로만 이루어진 문자열
        let string110 = Array(repeating: "110", count: numOf110).joined()
        
        // 마지막 0의 위치가 -1인 경우 (= 110을 제외한 나머지 문자열이 모두 1로 이루어짐)
            // 110 문자열 뒤에 1로만 이루어진 문자열만 붙이면 된다.
        // 마지막 0의 위치가 -1이 아닌 경우 (= 110을 제외한 나머지 문자열에 0이 포함된 경우)
            // 마지막 0의 위치에 뒤에 110 문자열을 이어 붙인다.
        var result = lastZero == -1 ? string110 : ""
        
        for i in 0..<stack.count {
            result += stack[i]
            // 마지막 0의 위치에 110문자열 이어 붙이기
            if i == lastZero {
                result += string110
            }
        }
        
        ans.append(result)
        
    }
    
    return ans
}