문제 풀이 아이디어

규칙성을 찾아라?

처음에는 아래 처럼 쭉 써놓고 규칙성을 찾기 위해 노력해봤습니다만… 상당히 복잡하고 조건이 까다로워서 구현하기가 쉽지 않았습니다. dfs나 순열을 사용해볼까도 생각을 했습니다만 n이 최대 1,000,000입니다. 2진수로 변환하면 그 길이는 어마어마할 것입니다…

/*
 1
 10
 100
 1000
 
 11
 
 101
 110
 
 1001
 1010
 1100
 
 111
 1011
 1101
 1110
 
 10011
 10101
 10110
 */

브루탈 포스!

해결책은 브루탈 포스였습니다. 다음 값을 구할 때 이진수로 구하는 것이 아니라 일단 십진수로 구한 다음에 이진수로 변환해서 1의 갯수를 세서 확인하는 방식으로 구하면 됩니다.

코드

func solution(_ n:Int) -> Int {
    // 다음 숫자는 n보다 크므로 1을 더한다.
    var ans = n + 1
    // n의 "1" 갯수
    let oneCount = String(n, radix: 2).filter { $0 == "1" }.count
    
    // n의 "1" 갯수와 ans의 "1" 갯수가 동일해질 때까지 ans를 늘리기
    while true {
        let ansOneCount = String(ans, radix: 2).filter { $0 == "1" }.count
        if ansOneCount == oneCount {
            break
        }
        ans += 1
    }
    
    return ans
}