[Python/코테 공부] 1로 만들기

[Python/코테 공부] 1로 만들기

1로만들기

 

내 풀이

무작정 모든 원소를 탐색해서 나누기 계속하는 것 보다, 어떤 규칙성이 있을 것 같아서 노트에 정리해보았다.

 

내가 찾은 1로만들기 규칙성

 

규칙성을 찾다 보니,

n이 1일 때는 0,

그 외에는 i가 1씩 늘어날 때 2^i 이상 2^(i+1) 미만에서 i번 만큼의 연산을 하는 것을 찾았다.

 

그래서 이를 아래와 같은 코드로 작성했다.

 

def solution(num_list):
    answer = 0
    
    for n in num_list:
        if n == 1: 
            continue 
        for i in range(1, 5):
            if n >= 2**i and n < 2**(i+1):
                answer += i
                break
        
    return answer

 

테스트 결과

내 풀이 테스트 결과

 

효율이 아주 나쁜것은 아니지만, 그래도 for문을 2번 사용하긴 한다.

 

다른 사람의 풀이에서 내가 찾은 방법과 비슷하지만, for문을 1번 사용한 풀이를 찾았다.

 

다른 사람의 풀이

def solution(num_list):
    return sum(len(bin(i)) - 3 for i in num_list)

 

num_list의 원소를 각각 2진수로 바꾼 뒤, 길이를 이용해서 풀었다.

 

i가 2의 제곱으로 늘어날 때 bin(i)는 아래의 표와 같다.

i	bin(i)
1	0b1
2	0b10
4	0b100
8	0b1000

 

이 bin의 길이에서 3을 뺀 값들을 더하면 최종 연산 횟수의 합이 구해진다.

 

내가 2의 제곱에 대해 for문을 사용한 부분을 이렇게 이진수로 바꿔서 for문 없이 간단하게 풀었다.

 

* 저번에도 이진수를 이용한 문제가 있었는데, 잘 활용하면 아주 유용할듯 하다.

* https://hsyaloe.tistory.com/86

[Python/코테공부] 배열 만들기 2

 

테스트 결과

확실히 for 문을 한 번만 사용해서 더 빠르다.

 

bin 이용시 테스트 결과

 

 

 

* 문제 출처: 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/181880

프로그래머스