[프로그래머스/Swift] 77885번 - 2개 이하로 다른 비트

🔗 문제 링크

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

💡 구현 아이디어

문제 풀이에 사용한 상황은 2가지

1. number가 2^n - 1 인 숫자이다.
2. number가 2^n - 1 이 아닌 숫자이다.

1번의 상황은 n을 구해서 2^(n+1) - 1 + 2^(n-1) 을 계산하면 답이 나온다.

2번의 상황은 (최소 number 보다 커야하므로) 가장 낮은 비트 부터 탐색을 하며 0을 발견하면 1로 바꿔주고 (그중 가장 작은 숫자여야 하므로) 다시 역으로 탐색해서 1을 만나면 0으로 바꿔주고 숫자를 변환한다.

💻 코드

import Foundation

func solution(_ numbers:[Int64]) -> [Int64] {
  var result: [Int64] = []
  for number in numbers {
    if number == 0 {
      result.append(1)
      continue
    }
    let log2N = Int64(log2(Double(number)))
    
    if Int64(pow(2.0, Double(log2N+1)))-1 == number { // 2^n - 1인 경우
      let n = Int64(log2(Double(number))) + 1
      let temp = Int64(pow(2.0,Double(n+1)) - 1 - pow(2.0,Double(n-1)))
      result.append(temp)
    } else {
      var tempArr: [String] = String(number, radix: 2).map { String($0) }
      var idx: Int = 0
      for i in (0..<tempArr.count).reversed() {
        if tempArr[i] == "0" {
          idx = i + 1
          tempArr[i] = "1"
          break
        }
      }
      for i in idx..<tempArr.count {
        if tempArr[i] == "1" {
          tempArr[i] = "0"
          break
        }
      }
      let int64N: Int64 = Int64(tempArr.joined(), radix: 2)!
      result.append(int64N)
    }
  }
  return result
}

❌ 틀린 이유 및 틀린 부분

• 0이 입력된 경우를 처리해 주지않았음 - 숫자가 1부터 시작한다고 생각을 해버렸다..(문제 똑디 읽자!)

⏳ 시간 복잡도

• O(N) : 각 비트를 하나씩 확인하는 과정이 N번씩 총 2번 돌아감

📌 풀이 또는 기억할 정보

역시 이런 문제는 비트연산자를 잘 아는 사람은 쉽게 푸는 문제였다.. 다른 사람의 풀이를 확인했더니 아래와 같은 풀이가 등장하였다

func solution(_ numbers:[Int64]) -> [Int64] {
    return numbers.map {
        if $0 % 2 == 0 { return $0 + 1 }
        else {
            let last = (~$0) & ($0+1)
            return ($0 | last) & ~(last>>1)
        }
    }
}

사실 이런 풀이는 어느정도 생각을 한다고 나오는 풀이는 아니라고 생각한다 각 비트 연산자를 잘섞고 시프트 연산자까지 사용을 했으니… 이 부분은 나중에 한번 정리를 해봐야하지 않나 싶다. 물론 비트 연산자를 실사용하기에는 머리가 너무 아파오기에 가끔 쓸까 말까하겠지만 혹시 모르기 때문에!! 정리를 해두자..