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

문제는 쉬웠는데 시간 초과가 2개 발생한다.

• 처음 짯던 코드...
• 뭐가 문제인지 모르겠다. 였고...

def solution(numbers):
    answer = []
    
    for i in numbers:
        bin_i = bin(i)[2:]
        bin_i_list = list(bin_i)
        j = i
        while True:
            j += 1
            bin_j = bin(j)[2:]
            bin_j_list = list(bin_j)
            if len(bin_i_list) < len(bin_j_list):
                bin_i_list.insert(0, "0")
            count = 0
            for bi,bj in zip(bin_i_list,bin_j_list):
                if bi != bj:
                    count += 1
            if count <= 2:
                break
        answer.append(j)
    return answer
    
    정확성  테스트
테스트 1 〉	통과 (6.41ms, 10.4MB)
테스트 2 〉	통과 (753.48ms, 22.8MB)
테스트 3 〉	통과 (1.27ms, 10.1MB)
테스트 4 〉	통과 (3.41ms, 10.4MB)
테스트 5 〉	통과 (8.88ms, 10.4MB)
테스트 6 〉	통과 (8.92ms, 10.3MB)
테스트 7 〉	통과 (1544.91ms, 23.8MB)
테스트 8 〉	통과 (911.41ms, 23.3MB)
테스트 9 〉	통과 (1357.31ms, 23MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)

• 더 풀어서 써야하나? 하면서 고쳐봤는데 더 느려짐. ㅋㅋㅋ

def solution(numbers):
    answer = []
    
    for i in numbers:
        bin_i = bin(i)[2:]
        bin_i_list = list(bin_i)
        j = i
        while True:
            j += 1
            bin_j = bin(j)[2:]
            bin_j_list = list(bin_j)
            bi_len = len(bin_i_list)
            bj_len = len(bin_j_list)
            if bi_len < bj_len:
                bin_i_list.insert(0, "0")
            count = 0
            for k in reversed(range(bj_len)):
                if bin_i_list[k] != bin_j_list[k]:
                    count += 1
                    if count > 2:
                        continue
            if count <= 2:
                break
        answer.append(j)
    return answer
    
    정확성  테스트
테스트 1 〉	통과 (7.13ms, 10.3MB)
테스트 2 〉	통과 (909.03ms, 22.8MB)
테스트 3 〉	통과 (0.89ms, 10.2MB)
테스트 4 〉	통과 (4.18ms, 10.3MB)
테스트 5 〉	통과 (13.35ms, 10.3MB)
테스트 6 〉	통과 (8.07ms, 10.2MB)
테스트 7 〉	통과 (2115.68ms, 23.9MB)
테스트 8 〉	통과 (1226.75ms, 23.2MB)
테스트 9 〉	통과 (1712.45ms, 23.1MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)

• 그래서 다시 처음의 소스로 돌아가서, 짝수일 때는 뒤가 0이니까 1 자리수만 바꿔주면 되서 그거 처리해봄.
• 아주 조금 빨라졌네? 개미 발가락 만큼... ㅡ.ㅡ;

def solution(numbers):
    answer = []
    
    for i in numbers:
        if i % 2 == 0:
            j = i + 1
        else:
            bin_i = bin(i)[2:]
            bin_i_list = list(bin_i)
            j = i
            while True:
                j += 1
                bin_j = bin(j)[2:]
                bin_j_list = list(bin_j)
                if len(bin_i_list) < len(bin_j_list):
                    bin_i_list.insert(0, "0")
                count = 0
                for bi,bj in zip(bin_i_list,bin_j_list):
                    if bi != bj:
                        count += 1
                if count <= 2:
                    break
        answer.append(j)
    return answer
    
    정확성  테스트
테스트 1 〉	통과 (2.57ms, 10.2MB)
테스트 2 〉	통과 (673.15ms, 22.9MB)
테스트 3 〉	통과 (0.79ms, 10.3MB)
테스트 4 〉	통과 (3.20ms, 10.3MB)
테스트 5 〉	통과 (8.29ms, 10.2MB)
테스트 6 〉	통과 (5.27ms, 10.3MB)
테스트 7 〉	통과 (1515.28ms, 23.7MB)
테스트 8 〉	통과 (917.98ms, 23.2MB)
테스트 9 〉	통과 (1085.89ms, 22.9MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)

• 응... 안되쥬?
• 테스트 10번 11번은 홀수만 넣어둔 듯 ㅡ.ㅡ;
• 이게 그렇게 큰 숫자구나...

• 그래서 문제를 다시 찬찬히 읽어보기로 ㅋㅋㅋ

 

문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수	비트	다른 비트의 개수
2	000...0010
3	000...0011	1

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

수	비트	다른 비트의 개수
7	000...0111
8	000...1000	4
9	000...1001	3
10	000...1010	3
11	000...1011	2

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 1015

---

입출력 예

numbers	result
[2,7]	[3,11]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

 

풀이

• 이거 다시 보니 규칙을 찾는 문제 같다.
• for문으로 무한으로 돌릴게 아니라 "01"인걸 찾아서 "10"으로 바꿔주면 되는 것 같음. "11"이면 "100"인데... 이러면 3개가 달라지니까 101로 해줘야함.
• 그래서 시간 초과 나는 알고리즘으로 한번 뽑아봄.

 0  1      0b0      0b1
 1  2      0b1     0b10
 2  3     0b10     0b11
 3  5     0b11    0b101
 4  5    0b100    0b101
 5  6    0b101    0b110
 6  7    0b110    0b111
 7 11    0b111   0b1011
 8  9   0b1000   0b1001
 9 10   0b1001   0b1010
10 11   0b1010   0b1011
11 13   0b1011   0b1101
12 13   0b1100   0b1101
13 14   0b1101   0b1110
14 15   0b1110   0b1111
15 23   0b1111  0b10111
16 17  0b10000  0b10001
17 18  0b10001  0b10010
18 19  0b10010  0b10011
19 21  0b10011  0b10101
20 21  0b10100  0b10101
21 22  0b10101  0b10110
22 23  0b10110  0b10111
23 27  0b10111  0b11011
24 25  0b11000  0b11001
25 26  0b11001  0b11010
26 27  0b11010  0b11011
27 29  0b11011  0b11101
28 29  0b11100  0b11101
29 30  0b11101  0b11110
30 31  0b11110  0b11111
31 47  0b11111 0b101111
32 33 0b100000 0b100001
33 34 0b100001 0b100010
34 35 0b100010 0b100011
35 37 0b100011 0b100101
36 37 0b100100 0b100101
37 38 0b100101 0b100110
38 39 0b100110 0b100111
39 43 0b100111 0b101011
40 41 0b101000 0b101001
41 42 0b101001 0b101010
42 43 0b101010 0b101011
43 45 0b101011 0b101101
44 45 0b101100 0b101101
45 46 0b101101 0b101110
46 47 0b101110 0b101111
47 55 0b101111 0b110111
48 49 0b110000 0b110001
49 50 0b110001 0b110010

• 짝수일 때는 +1 해주면 되고, 홀수일 때도 +1이 되는 애들이 있음. 근데 +1이 안되는 숫자가 있음.
  • 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, ...
• 흠... 뭐지? 랜덤인가? 어?
  • 3, 7, 11, 15, 19,
  • 23, 27, 31, 35, 39,
  • 43, 47, ...
• 3,7,11,15,19... 반복이네...
• 도와줘요! 울프람알파! 4n - 1?

• 저걸 알아냈어도 안 빨라짐 ㅡ.ㅡ;

def solution(numbers):
    answer = []
    
    for i in numbers:
        if (i + 1) % 4 != 0:
            j = i + 1
        else:
            bin_i = bin(i)[2:]
            bin_i_list = list(bin_i)
            j = i
            while True:
                j += 1
                bin_j = bin(j)[2:]
                bin_j_list = list(bin_j)
                if len(bin_i_list) < len(bin_j_list):
                    bin_i_list.insert(0, "0")
                count = 0
                for bi,bj in zip(bin_i_list,bin_j_list):
                    if bi != bj:
                        count += 1
                if count <= 2:
                    break
            
        #print(i, j, bin(i), bin(j))
        answer.append(j)
    return answer

• 여기서 규칙을 찾아야되네...

 3  5     0b11    0b101
 7 11    0b111   0b1011
11 13   0b1011   0b1101
15 23   0b1111  0b10111
19 21  0b10011  0b10101

23 27  0b10111  0b11011
27 29  0b11011  0b11101
31 47  0b11111 0b101111
35 37 0b100011 0b100101
39 43 0b100111 0b101011

43 45 0b101011 0b101101
47 55 0b101111 0b110111

• 찾았다!!! 이후로는 이진수 문자열을 리스트로 만들고 01을 찾아서 10으로 고치고 다시 문자열 합치고 십진수로 만들어서 결과에 추가하면 끝.

def solution(numbers):
    answer = []
    
    for i in numbers:
        if (i + 1) % 4 != 0:
            j = i + 1
        else:
            bin_i = bin(i)[2:]
            bin_i_list = list(bin_i)
            bin_i_list.insert(0, "0")
            bin_i_list_len = len(bin_i_list)
            for i in reversed(range(bin_i_list_len)):
                if bin_i_list[i] == '0':
                    bin_i_list[i] = '1'
                    if i != bin_i_list_len - 1:
                        bin_i_list[i+1] = '0'
                        break
            bin_i = ''.join(bin_i_list)
            j = int(bin_i,2)
        answer.append(j)
    return answer

정확성  테스트
테스트 1 〉	통과 (0.44ms, 10.3MB)
테스트 2 〉	통과 (45.82ms, 23MB)
테스트 3 〉	통과 (0.06ms, 10.3MB)
테스트 4 〉	통과 (0.34ms, 10.2MB)
테스트 5 〉	통과 (0.45ms, 10.2MB)
테스트 6 〉	통과 (0.75ms, 10.2MB)
테스트 7 〉	통과 (64.88ms, 23.4MB)
테스트 8 〉	통과 (52.68ms, 22.9MB)
테스트 9 〉	통과 (50.72ms, 22.6MB)
테스트 10 〉	통과 (336.17ms, 23.8MB)
테스트 11 〉	통과 (330.90ms, 23.8MB)

와- 점수 개 많이주네?

• 기분 좋게 다른 사람 풀이도 보러갔더니 후덜덜...
• 왜 인공지능이 알고리즘 문제를 풀고 있엉 ㅠ.ㅠ

핵고수의 풀이법...

def solution(numbers):
    answer = []
    for idx, val in enumerate(numbers):
        answer.append(((val ^ (val+1)) >> 2) +val +1)

    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.40ms, 10.3MB)
테스트 2 〉	통과 (33.20ms, 22.8MB)
테스트 3 〉	통과 (0.04ms, 10.2MB)
테스트 4 〉	통과 (0.31ms, 10.4MB)
테스트 5 〉	통과 (0.27ms, 10.2MB)
테스트 6 〉	통과 (0.24ms, 10.4MB)
테스트 7 〉	통과 (23.40ms, 23.7MB)
테스트 8 〉	통과 (21.95ms, 23.4MB)
테스트 9 〉	통과 (27.19ms, 22.9MB)
테스트 10 〉	통과 (21.85ms, 25.4MB)
테스트 11 〉	통과 (38.45ms, 25.4MB)

난 아직 멀었구나... ㅡ.ㅡ;