[Swift] [61일차] 1561_LEET 0,1 잘 배치하기

핀·2025년 2월 6일

SwiftAlgorithm

목록 보기

64/105

3211. Generate Binary Strings Without Adjacent Zeros

문제 설명

정수 n이 주어짐

그 길이의 이진수 중에서 가능한 경우의수를 배열로 출력
인지 알았는데, 이제 길이2 부분 문자열에 대해서 "1"을 소지하고 있어야한다.
그니까 이게 "001"은 안되고, "010"은 된다는 소리 !

문제풀이

처음에는 이렇게 그냥 무식하게 풀어내려고 했는데, 점점 할 수록 쓸데없는 조건이 붙는것을 확인했다.
가령 "11"일때는 앞에 0을 붙여야하는데, 그러면 0부터 반복문을 다돌려야하나? 그러면 일일히 또 반복문 돌리면서 1개수 파악해줘야하나? 등..

import Foundation

class Solution {
    func validStrings(_ n: Int) -> [String] {
        var MAX_VALUE = Int(pow(2.0, Double(n)))
        var MIN_VALUE = Int(pow(2.0, Double(n - 1))) - 1
        var answer = [String]()
        for i in MIN_VALUE ..< MAX_VALUE {
            answer.append(String(i, radix: 2))
        }
        return answer
    }
}

그래서 생각하다보니 이거 DFS같이해서 앞에서부터 출발해서 이전꺼에 1이들어있냐 안들어있냐 같은거로 판단해주면 될 것 같은데? 라는 생각이 들어서 바로 작성해봤다.

import Foundation

class Solution {
    func validStrings(_ n: Int) -> [String] {
        var test_Array = Array(repeating: 0, count: n)
        var answer = [String]()

        func dfs(_ index: Int, _ before: Int, _ arr: [Int]) {
            if index == n { // 끝났을 때
                print(arr)
                return
            }
            var tmp = arr

            if before == 1 { // 이전이 1일때만 여기서 책임없이 0 넣어줄 수 있는 것
                tmp[index] = 0
                dfs(index + 1, 0, tmp)
            }
            tmp[index] = 1
            dfs(index + 1, 1, tmp)
            if index + 1 == n {}
        }
        dfs(0, 1, test_Array)
        return ["!"]
    }
}

print(Solution().validStrings(3))

어느정도 윤곽을 갖추니까 다음과 같이 잘 뜬 것을 볼 수 있다.

이제 그러면 이걸 뭐 이진법으로 할필요도없이 String으로 바꿔서 이걸 join시켜주면 끝날 것이다.

[0, 1, 0]
[0, 1, 1]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]

배열에 있는 것들 합쳐주기

 let answer_string = arr.map { String($0) }.joined()

최종코드

class Solution {
    func validStrings(_ n: Int) -> [String] {
        var test_Array = Array(repeating: 0, count: n)
        var answer = [String]()

        func dfs(_ index: Int, _ before: Int, _ arr: [Int]) {
            if index == n { // 끝났을 때
                let answer_string = arr.map { String($0) }.joined()

                answer.append(answer_string)
                return
            }
            var tmp = arr

            if before == 1 { // 이전이 1일때만 여기서 책임없이 0 넣어줄 수 있는 것
                tmp[index] = 0
                dfs(index + 1, 0, tmp)
            }
            tmp[index] = 1
            dfs(index + 1, 1, tmp)
            if index + 1 == n {}
        }
        dfs(0, 1, test_Array)
        return answer
    }
}

엄청 효율적으로 잘 푼것 같아서 이것보다 더빠른 코드를 살펴봤다.

class Solution {
    private var arr: [Character]!
    private var result: [String] = []
    
    func validStrings(_ n: Int) -> [String] {
        arr = Array<Character>(repeating: "0", count: n)
        resolveCharacterAt(index: 0)
        
        return result
    }
    
    private func resolveCharacterAt(index: Int) {
        guard index < arr.count else {
            result.append(String(arr))
            return
        }
        
        if index > 0 {
            if arr[index - 1] == "0" {
                arr[index] = "1"
                resolveCharacterAt(index: index + 1)
            } else {
                arr[index] = "0"
                resolveCharacterAt(index: index + 1)
                
                arr[index] = "1"
                resolveCharacterAt(index: index + 1)
            }
        } else {
            arr[index] = "0"
            resolveCharacterAt(index: index + 1)
            
            arr[index] = "1"
            resolveCharacterAt(index: index + 1)
        }
    }
}