Algorithm / 2개 이하로 다른 비트

문제

프로그래머스 / 2개 이하로 다른 비트

1) 문제 풀이

func solution(_ numbers:[Int64]) -> [Int64] {
    var answer: [Int64] = []
    
    for num in numbers {
        var count = 3
        var result = num
        
        while count > 2 {
            result += 1
            let distance = (num ^ result).nonzeroBitCount
            
            if distance <= 2 {
                answer.append(result)
            }
            
            count = distance
        }
        
    }
    
    return answer
}

결과

2) 코드 개선

⚠️ 문제점 분석

• 불필요한 while 루프
  • count > 2일 때 루프를 돌고 있지만, 조건이 만족해도 루프는 계속 돌아가는 상황
  • if distance <= 2이면 answer.append(result)만 하고 루프 종료를 하지 않음 -> count 값만 바꾸고 루프 계속
• 시간 복잡도
  • while 루프에서 result += 1씩 증가시키므로 최악의 경우 선형 탐색 -> 느림
  • 특히, 큰 수일 경우 매우 비효율적

✅ 개선 포인트

• 핵심 규칙
  • 짝수인 수 = 바로 다음 수는 비트 차이가 1
  • 홀수인 수: 가장 오른쪽 0을 1로 바꾸고, 그 다음 비트를 0으로 바꾸면 비트 차이 2
  • num + 1 + (num ^ (num + 1)) >> 2로 계산할 수 있음

func solution(_ numbers: [Int64]) -> [Int64] {
    return numbers.map { num in
        if num % 2 == 0 {
            return num + 1
        } else {
            var bit: Int64 = 1
            while (num & bit) != 0 {
                bit <<= 1
            }
            return num + bit - (bit >> 1)
        }
    }
}

결과