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

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

프로그래머스

---

우선 처음 제출한 코드이다.

def solution(numbers):
    answer = []
    
    for i in numbers:
        j = i+1
        while True:
            num = bin(i^j)
            if num.count("1") in [1,2]:
                answer.append(j)
                break
            j += 1
    return answer

 

이 코드로는 테케 9, 10에서 시간초과가 났다.

 

i+1부터 숫자들을 증가시켜주며 차례로 xor 연산을 하고, 다른 비트 수가 1개 또는 2개면 그 숫자를 선택해주었다.

 

원하는 숫자를 반복문으로 찾았기 때문에 매우 큰 수에서 시간초과가 난 것 같았다.

 

어떤 방법이 있을까 계속 고민해봤는데,

짝수인 경우 단순히 1을 더해준 숫자가 정답이다 이정도까지밖에 생각나지 않았다.

 

---

질문 게시판에 어떤 분이 좋은 방법을 적어두셨길래, 우선 이대로 코드를 짜봤다.

 

하 저거 보고 일단 정직하게 열심히 구현 해봤다.

def solution(numbers):
    answer = []
    
    for i in numbers:
        if i%2 == 0:
            answer.append(i+1)
        else:
            add = []
            for j in bin(i)[::-1]:
                if j == "0" or j=="b":
                    add.append("1")
                    break
                add.append("0")
            result = ''.join(reversed(add))
            k = int(result,2)
            answer.append(int(i) + k - k//2)
    return answer

부족하지만 이 코드로 통과할 수 있었다.

 

---

다른 사람들 풀이를 여러 개 구경했는데 다들 천재인 것 같다..

음 이런 문제는 수학머리 없으면 솔브 하기 힘들 것 같다는 생각이 들었다.

 

가장 위에 있던 풀이에서 도움받았던 댓글

나중에 이 문제 다시 풀 때 또 필요하면 보려고 캡처해둠

 

하 어렵다