[코드트리] 이상한 진수 2 /완전탐색, 이진수to십진수

 

https://www.codetree.ai/missions/5/problems/awkward-digits-2?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

이상한 진수

---

0 이상의 정수 N을 2진법으로 나타낸 뒤, 그 숫자들 중 정확히 한 숫자만을 바꾼 숫자 a가 주어졌을 때, 가능한 숫자 N 중 최댓값을 찾는 프로그램을 작성해보세요.

 

입력 예시

1010

 

출력예시

14

 

 

 

 

 

 

 

이진수를 어떻게 십진수로 변한해야할 지 모르겠어서 해설을 봤다.

 

 

 

 

 

코드

import sys

INT_MIN = -sys.maxsize

#바이너리값 리스트로 입력받기 input() 을 int 값으로 변경해서 리스트 생성
binary = list(map(int, input()))
length = len(binary)

INT_MIN = -sys.maxsize
ans = INT_MIN
for i in range(length):
    #i번째 자리수를 바꾸기 
    binary[i] = 1-binary[i]

    #십진수로 변환
    num = 0
    for j in range(length):
        num += (2**(length-j-1)) * binary[j]


    ans = max(ans, num)
    binary[i] = 1-binary[i]

print(ans)

 

우선 import sys 를 통해 sys 모듈을 임포트한다. 해당 모듈을 임포트한 이유는 int의 최솟값을 구해놓기 위해서이다. 일단 초기화 시키기 위해서이다.

그 후 binary를 리스트로 입력받는다. 이때 이 배열은 int 배열로 만약 1011 이 들어온다면 1, 0, 1, 1 이 들어가게된다.

binary 의 크기는 해당 이진수의 자릿값이 된다. 이를 따로 변수 length 에 len(binary)를 통해 구해놓는다.

자릿수 만큼 반복을 반복한다.

전체 자릿수를 한번씩 변경해봐야하므로 우선 binary[0]부터 binary[length-1] 까지 진행한다.

i번째 자리수를 바꾸려면 binary[i] = 1-binary[i] 로 한다. 왜냐면 숫자가 0, 1밖에 없기 때문이다.

그 후 십진수로 변환을하기 위해 자리수 만큼 또 반복한다.

num 변수에는 십진수로 바꾸기 위한 공식을 넣는데

나는 

num += (2**(length-j-1)) * binary[j] 공식을 통해  {2의 해당자리수제곱 * 해당 자리에 해당하는 수} 를 더해가며 십진수를 완성시켰다 

해설에서는

for j in range(length):

num = num * 2 + binary[j]

 

방법을 사용했는데 이것은 왼쪽에서 오른쪽으로 순회하며 num을 업데이트 시켜주는 방법이다. 우리가 십진수를 이진수로 변환할때는 해당 수를 2로 나누고 그 수를 또 2로 나누고 안 나눠질 때 까지 나눈 후 나머지를 거꾸로 읽어주는 방식이었다. 

해설의 코드는 이 방식을 거꾸로 적용한 것으로 해당수*2 + 나머지 를 해서 위로 올라가는 방법이다.

아래 사진을 참고하자.

 

 

오늘 배운 점은 

-sys 모듈로 

INT_MIN 을 -sys.maxsize 로 초기화시킬수 있다는 점과

-이진수를 십진수로 변환할때 

num = num*2 + binary[j] 로 거꾸로 계산해주면 된다는 점

-이진수의 i번째 자리를 바꾸려면 binary[i] = 1-binary[i]를 해주면 된다는 점 

- 이진수를 입력받을 때는 리스트로 입력받아도 된다는 점 binary = list(int, input())