[Programmers] 배열 만들기 2

문제 설명

정수 l과 r이 주어졌을 때, l 이상 r이하의 정수 중에서 숫자 "0"과 "5"로만 이루어진 모든 정수를 오름차순으로 저장한 배열을 return 하는 solution 함수를 완성해 주세요.

만약 그러한 정수가 없다면, -1이 담긴 배열을 return 합니다.

 

제한사항

• 1 ≤ l ≤ r ≤ 1,000,000
  

 

---

문제 풀이

접근 전략

주어진 l과 r 사이의 range에서 얻어낸 i가, str로 변환했을때 모두 "0" 이나 "5"로 이루어져 있는 가를 확인했다. all 메소드를 쳐서 모두 "0" 이나 "5"라면, answer에 추가하는 방식으로 진행했고, 비어있으면 [-1]를 반환하도록 했다.

 

코드

def solution(l, r):
    answer = []
    for i in range(l,r+1):
        if all(j in ["0", "5"] for j in str(i)):
            answer.append(i)
            
    if not answer:
        answer = [-1]
        
    return answer

결과 및 해석

위의 코드는 각 범위에 대해서 해당 범위를 스캔하며 조건에 맞는 숫자가 있는지를 찾음. 만약 조건에 맞는 원소가 없다면 [-1]를 반환하도록 함. all 은 주로 조건 검사에 자주 쓰이는데, iterable한 자료형을 입력받아서 모두 참이면 True를 반환해줌.

 

chatGPT 형님은 비트마스크를 사용해서 코드를 개선함. 0과 5로만 이루어진 숫자는 이진수와 매우 유사하기 때문에, 이진수에서 0은 0으로, 1은 5로 대응되는 방식으로 응용함. 이 점을 이용하면, 비트마스크를 사용하여 0부터 20까지 (1부터 2 ** 20, 제한사항이 1,000,000 까지이므로) 의 모든 이진수를 생성하고, 이를 10진수로 변환하여 0과 5로만 이루어진 숫자를 생성해버렸음. 1 << 20 이거는 왼쪽 쉬프트 연산이고, 1 << 20 은 1의 비트를 20칸 이동시켜서 2 ** 20을 만드는 것임. 그래서 range(1 << 20) 은 range(2, 2 ** 20)과 같은 범위를 표현하고 있음. 아무래도 처리 속도에 있어서는 이진수가 아니면 검사를 안하기에 개선 할 수 있어보이긴 함.

 

def solution(l, r):
    answer = []

    # 가능한 이진수를 생성하고, 이를 10진수로 변환한다.
    for i in range(1 << 20):
        num = int(bin(i)[2:].replace('1', '5'))

        # 변환된 숫자가 주어진 범위 내에 있으면, 답에 추가한다.
        if l <= num <= r:
            answer.append(num)

    if not answer:
        answer = [-1]

    return sorted(answer)