용꿀
꼬마개발자허니
용꿀
전체 방문자
오늘
어제
  • 분류 전체보기 (250)
    • 개발 (77)
      • 스프링 입문 (7)
      • 스프링 기본 (9)
      • ToDo List using JPA (2)
      • 스프링 개념 (9)
      • 스프링 부트와 AWS로 혼자 구현하는 웹 서비스 (8)
      • 스프링 MVC (3)
      • CS (21)
      • 개발 팁 (8)
      • 스프링 MSA (5)
      • 곰터뷰🐻 (5)
    • 알고리즘 (169)
      • 알고리즘 문제 풀이 (165)
    • 잡동사니 (1)
      • 노래 가사 (1)
hELLO · Designed By 정상우.
용꿀

꼬마개발자허니

[프로그래머스 Lv.2] 2개 이하로 다른 비트 (Python)
알고리즘/알고리즘 문제 풀이

[프로그래머스 Lv.2] 2개 이하로 다른 비트 (Python)

2024. 11. 17. 11:40

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/77885

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

풀이

x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수를 구하는 함수를 구현하는 문제이다.

구현 문제이기에 우선 간단한 예시를 통해 규칙을 찾아야 한다. 2부터 시작하여 규칙을 찾아보겠다.

2는 이진수로 10이고 2보다 크고 2와 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 11로 3이다.

3은 이진수로 11이고 3보다 크고 3과 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 101으로 5이다.

4는 이진수로 100이고 4보다 크고 4와 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 101으로 5이다.

5는 이진수로 101이고 5보다 크고 5와 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 110으로 6이다.

6은 이진수로 110이고 6보다 크고 6과 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 111으로 7이다.

7은 이진수로 111이고 7보다 크고 7과 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 1011으로 11이다.

 

위의 예시들을 살펴보았을 때 찾을 수 있는 규칙은 우선 짝수일 때는 쉽게 찾을 수 있다. 짝수는 이진수로 하였을 때 맨 마지막 자리가 0이므로, 단순하게 맨 마지막 자리의 수를 1로 변경하는 것, 즉 원래 수에 1을 더하는 것으로 답을 구할 수 있다.

어려운 것은 홀수일 때의 규칙을 찾는 것이다. 5의 경우를 살펴보면 101이 110으로 바뀌었기에 처음으로 0인 나온 시점의 다음 비트와 함께 10으로 변경하면 되는 것이 아닌가 의심해 볼 수 있다. 101 -> 110

3도 확인해보면 011 -> 101로 변경되고, 7의 경우에도 0111 -> 1011로 바뀌게 되기에 5의 경우에서 가정한 방법이 옳게 된 가정임을 확인할 수 있다.

 

이제 위에서 찾아낸 방식인 짝수는 1을 더하고, 홀수는 처음으로 0이 나온 경우 그다음 비트와 함께 10으로 변경하는 것을 코드로 구현하면 된다.

def to_binary(number): # 십진수를 이진수로 변환하는 메서드
    binaries = []
    
    while number > 0: # 이진수를 구하려는 숫자를 지속적으로 2로 나누면서 0보다 큰 경우에 반복
        binary = number % 2 # 2로 나눈 나머지를
        binaries.append(str(binary)) # 배열에 저장
        number //= 2 # 2로 나누어 다음 binary 값을 계산할 수 있도록 함
    
    return "".join(binaries[::-1]) # 2로 나눈 나머지들을 역순으로 하면 이는 십진수를 이진수로 변환한 값


def solution(numbers):
    answer = []
    
    for number in numbers:
        if number % 2 == 0: # 숫자가 짝수이면
            answer.append(number + 1) # 단순히 1을 더한 값이 정답
        else: # 숫자가 짝수이면
            bnry = f"0{to_binary(number)}" # 이진수로 변환한 숫자 중
            tgt = bnry.rindex('0') # 첫번째로 0이 나타나는 시점에서
            bnry = f"{bnry[:tgt]}10{bnry[tgt+2:]}" # 그다음 비트와 함께 10으로 변환한 값이
            answer.append(int(bnry, 2)) # 정답
            
    return answer

'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글

[프로그래머스 Lv.2] 줄 서는 방법 (Python)  (0) 2024.11.20
[프로그래머스 Lv.2] 스킬트리 (Python)  (0) 2024.11.17
[프로그래머스 Lv.3] 섬 연결하기 (Python)  (0) 2024.10.20
[프로그래머스 Lv.3] 보석 쇼핑 (Python)  (0) 2024.10.15
[프로그래머스 Lv.3] 디스크 컨트롤러 (Python)  (2) 2024.10.12
    '알고리즘/알고리즘 문제 풀이' 카테고리의 다른 글
    • [프로그래머스 Lv.2] 줄 서는 방법 (Python)
    • [프로그래머스 Lv.2] 스킬트리 (Python)
    • [프로그래머스 Lv.3] 섬 연결하기 (Python)
    • [프로그래머스 Lv.3] 보석 쇼핑 (Python)
    용꿀
    용꿀

    티스토리툴바