Programmers / 2개 이하로 다른 비트 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 2개 이하로 다른 비트 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/77885

프로그래머스

문제 설명

양의 정수 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

---

입출력 예numbersresult

[2,7]

[3,11]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

---

나의 풀이

 

첫번째 풀이

길이만큼 다른 것 반환하기 - 런타임 에러

길이가 다르면 앞부분에 0을 채움

def solution(numbers):
    answer = []
    for i in range(len(numbers)):
        answer.append(convers(numbers[i]))
    return answer


def convers(n):
    num = n
    arr = []
    while True:
        num += 1
        cnt = 0
        bin_n = list(bin(n)[2:])
        bin_c = list(bin(num)[2:])

        if len(bin_n) < len(bin_c):
            while len(bin_n) != len(bin_c):
                bin_n.insert(0, "0")
        for i in range(len(bin_c)):
            if bin_n[i] != bin_c[i]:
                cnt += 1
        arr.append(cnt)
        if cnt <= 2:
            break
    print(arr)
    return len(arr) + n

두번째 풀이

 

해당 수가 10진법에서 짝수인 경우와 홀수인 경우 판단

결국 해당 수가 10진법에서 가장 작은 수이어야함

 

짝수인 경우 

예시) 

2를 비트 변환하면 10

끝자리의 0을 1로 바꾸어주고 해당 수를 10진법으로 리턴하면 됨

(어차피 최소가 된다는 조건에 부합)

 

홀수인 경우

예시)

3을 비트 변환하면 011

101, 111, 110

이 세개의 수를 10진법으로 변환하면 

101: 5, 110: 6, 111: 7

 

011

101

 

7을 비트 변환하면 0111

1011, 1001,1111

 

 7(0111) 은 가장 뒤쪽에 있는 0을 1로 바꿔주고 그다음 비트를 0으로 바꿔준다.

 즉, 11(1011)이 답이다.

 

규칙을 찾아주며 해당 수들을 찾으면 더 간단

 

모범답안

def solution(numbers):
    answer = []
    for i in range(len(numbers)):
        if numbers[i] % 2 == 0:
            answer.append(numbers[i] + 1)
        else:
            bin_num = "0"
            bin_num += bin(numbers[i])[2:]
            bin_num = bin_num[:bin_num.rindex('0')] + '10' + bin_num[bin_num.rindex('0') + 2:]
            answer.append(int(bin_num, 2))
            
    return answer

---

※ 알아야 할 것

-  rindex: 문자열 중에서 sub 문자열이 발견되어지는 가장 큰 색인(index: 가장 오른쪽에 있는 색인)이 반환

※ 형식
str.rindex(sub)
str.rindex(sub, start)
str.rindex(sub, start, end)

---

/// 예제

1 2 3 4 5 6 7 8 9 10 11

test_str = 'This is a string'   # 'This is a string' print(test_str.rindex('i'))  # 13   # 'This is a string' print(test_str.rindex('i', 0))  # 13   # 'This is ' print(test_str.rindex('i', 0, 7))  # 5   Colored by Color Scripter

cs

출처: https://hackedbypsychedelphia.blogspot.com/2021/11/python-rindex.html