수학과의 좌충우돌 프로그래밍

다음 큰 숫자(프로그래머스-level2) 본문

알고리즘/파이썬

다음 큰 숫자(프로그래머스-level2)

ssung.k 2018. 7. 30. 04:01

안녕하세요 강민성입니다.


프로그래머스에서 문제를 풀다보면 다음과 같은 문구를 보실 수 있을 겁니다. 


# 알고리즘 연습 문제가 개편 되었습니다. 이로 인해 함수 구성이 변경되어, 과거의 코드는 동작하지 않을 수 있습니다.


말 그대로 18년 5월 정도 부터 문제들이 약간씩 바뀌고 문제가 같더라도 테스트 케이스가 더 복잡해지고 정교해져서 옛날 풀이도 정답이 아닐 수 있습니다.


다른 블로그에 포스팅 된 글이나 프로그래머스 내에서 다른 사람의 풀이를 보실 때 참고하시길 바랍니다.


저는 개편된 후의 풀이임을 알립니다.



[ 문제 ]


자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.


조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.


조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.


조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.


예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.


자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.


제한 사항


n은 1,000,000 이하의 자연수 입니다.


입출력 예

n

 result

 78

83 

 15 

2



문제는 이해하기에 그닥 어려운 부분이 없으므로 바로 코드와 설명으로 넘어가겠습니다.


1
2
3
4
5
6
7
8
9
def solution(n):
 
    one_count = bin(n).count('1'# bin을 통해 10진수를 2진수로 바꿔줄 수 있고 
                          # count를 통해 1을 바로 세줄 수 있다.
    for i in range(n+1,1000001): # n보다 큰 수부터 제한사항에 만족하는 수까지 반복해준다.
 
        if bin(i).count('1'== one_count: # 1의 개수가 n가 같은 수가 나오면 그 수를 출력한다.
 
            return i
cs


다음과 같이 코드가 굉장히 짧습니다.


바로 파이썬의 두 가지 함수 bin 과 count 덕분입니다.



먼저 bin 부터 알아보도록 합시다.


다른 언어도 물론 이지만 파이썬 역시 함수의 이름으로 어떤 기능을 하는지 눈치를 챌 수 가 있는데요


2진수를 의미하는 Binary 의 앞 세 글자를 따서 이름을 지었습니다,


의미그대로 10진수를 2진수로 바꿔주는 함수로 사용하는 방법은 bin(10진수의 값) 을 하면 2진수로 출력해줍니다.


하지만 여기서 조심해야 할 점은 값을 수가 아닌 문자열로 출력해준다는 점 입니다.


비슷한 함수로는


16진수로 바꿔주는  hex(n) , 8진수로 바꿔주는 oct(n) 등이 있습니다.


혹시나 문자열로 출력되는 값을 다시 수로 바꾸고 싶다고 하면 eval 함수를 사용하면 됩니다.


eval("문자열")의 괄호 안에 문자열로 된 수식을 넣으면, eval 함수는 이 문자열을 수식으로 처리해서 계산한 후, 계산 값을 함수의 결과값으로 돌려줍니다.



다음으로는 count 함수에 대해 알아보겠습니다. 


count 역시 의미그래도 개수를 세어주는 함수입니다.


리스트나 문자열 등에서 사용할 수 있으며 사용 방법은 


count(x) 다음과 같이 표시해  리스트나 문자열 내에 x가 몇 개 있는지  그 개수를 돌려주는 함수입니다.



파이썬 같은 경우에는 다음과 같이 두 함수를 통해서 쉽게 알고리즘을 구현할 수 있는데 다른 언어같은 경우는 그렇지 않습니다.


예를 들어 bin 없이 2진수를 구하는 함수를 만들어보겠습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 2진수를 만드는 함수
 
def solution(n):
 
    bin_num = ''  # 빈 문자열을 하나 만들고
 
    while 1 <= n: # 1 보다 작아지면 반복문을 그만
 
        modNum = n % 2 # 2를 나눈 나머지를  modNum 변수에 담고
 
        bin_num = str(modNum) + bin_num # modNum 문자열에 계속 추가해준다.
 
        n = n // 2 # n은 2를 나눈 몫으로 계속 갱신해준다.
 
    int(bin_num) # 문자열인 bin_num 을 정수로 바꿔준다.
    
    return bin_num
cs




우리가 흔히 알고 있는 10진수를 2진수로 변환하는 방법 입니다.


코드로 이해하기 힘드시다면 한 가지 예를 통해 변환해보겠습니다.


10진수 25를 2진수로 바꾼다고 생각해봅시다.





다음과 같이 25를 2로 나누어 줍니다.


몫이 1이 나올때까지 계속 해서 나눠주며 나머지들을 아래서 부터 읽으면 2진수가 됩니다. 


10진수로 2진수로 바꾸는 방법은 아실거라는 가정하에 간단하게 설명을 마치도록 하겠습니다.




마무리


파이썬을 공부하면서 느끼는 건 정말 쉽고 편리하게 코드를 짤 수 있는 언어라는 점입니다. 


하지만 저런 알고리즘들을 함수들과 라이브러리에만 의존을 하게 된다면 파이썬 실력은 쑥쑥 늘어도


알고리즘 실력은 많이 안늘거 같아서 지금 처럼 여러 가지의 풀이법을 소개하도록 하겠습니당.


오늘도 읽어주셔서 감사합니다!





Comments