[프로그래머스][LV.0] 배열 만들기 2 | python3

 

문제 링크: 배열 만들기 2

 

문제 설명

문제 설명

정수 l과 r이 주어졌을 때, l 이상 r이하의 정수 중에서 숫자 "0"과 "5"로만 이루어진 모든 정수를 오름차순으로 저장한 배열을 return 하는 solution 함수를 완성해 주세요.
만약 그러한 정수가 없다면, -1이 담긴 배열을 return 합니다.

제한사항
- 1 ≤ l ≤ r ≤ 1,000,000

 

---

문제 풀이

좀 전에 풀어서 기억이 안나는데 아마 안풀려서 참고 해서 풀었던 것 같다. 그리고 다시 풀려고 보니 지금도 낑낑 거리는 게 레전드....

그래 그냥 5와 0 외의 숫자가 있으면 그냥 넘기면 된다. 

다시 풀려고 봤을때  r의 최대 숫자가 너무 커서 for문으로 돌려도 되나? 싶었는데(시간상) 상관없었나봄...
시간복잡도에 대해서도 제대로 공부해야 할 거 같다.

그리고 이 문제를 보니 기억이 났다. 이거 분명 뭔가 이진수를 이용해서 풀 수 있을 거 같다고 생각하고 그냥 넘겨서 따로 빼 놓은 문제였다. 

 

내코드

def solution(l, r):
    answer = []
    for n in range(l,r+1):
        if str(n) in ['1','2','3','4','6','7','8','9']:
            continue
        elif str(n) in ['1','2','3','4','6','7','8','9'] and str(n) in ['0']:
            continue
        elif str(n) in ['1','2','3','4','6','7','8','9'] and str(n) in ['5']:
            continue
        else:
            answer.append(n)
    if not answer:
        return [-1]
    return sorted(answer)

 

---

다른사람풀이

def solution(l, r):
    answer = []
    
    number = ['0', '5']
    
    for i in range(l, r+1):
        now = str(i)
        now_in = True
        for j in now:
            if j not in number:
                now_in = False
                break
        if now_in == True:
            answer.append(i)
    
    if answer:
        return answer
    else:
        return [-1]

리스트에 0과 5만 두고 다른 숫자가 나오면 바로 브레이크를 해버려서 빠져나온다.

for문을 두개나 도는데 과연 어느쪽이 더 빠를까??/

gpt한테 물어보니 이 코드가 훨씬 빠르다고 한다.

---

♠ 내 코드의 문제점

문제점

1. str(n) in ['1','2','3','4','6','7','8','9'] 검사가 잘못됨
   • str(n) 자체가 리스트 ['1','2','3','4','6','7','8','9']에 포함되는지 확인하는 코드인데, 이건 n이 한 자리 숫자가 아닐 때 항상 False가 됨.
   • 예를 들어 n=50일 때 str(n) == "50", 즉 "50" in ['1','2','3','4','6','7','8','9']는 False라서 필터링이 안 됨.
2. elif 조건이 의미 없음
   • elif str(n) in ['1','2','3','4','6','7','8','9'] and str(n) in ['0']:
     • str(n)이 ['1','2','3','4','6','7','8','9']에 포함되면서 동시에 ['0']에도 포함되어야 함.
     • 즉, 하나의 문자열이 ['0']과 ['1','2','3','4','6','7','8','9']에 동시에 포함될 수 없으므로 항상 False.
   • elif str(n) in ['1','2','3','4','6','7','8','9'] and str(n) in ['5']:
     • 위와 같은 이유로 항상 False.
3. sorted(answer)가 불필요
   • answer는 이미 오름차순으로 추가되기 때문에 sorted()를 호출할 필요가 없음.
4. 속도가 느린 이유
   • str(n) 변환이 불필요하게 여러 번 발생.
   • 잘못된 if-elif 조건이 많아서 불필요한 연산 수행.
   • 최악의 경우 O(N)의 시간복잡도인데, 불필요한 조건 검사로 인해 오히려 더 느려짐.

♠ 이 코드의 장점

장점

1. 올바른 조건 검사
   • 숫자를 문자열로 변환한 후, 각 자리 숫자가 '0' 또는 '5'만 포함하는지 검사.
   • for j in now:를 통해 자리 수 하나하나 검사하며, '0' 또는 '5'가 아닌 숫자가 나오면 break로 중단.
   • 시간 단축 효과가 있음.
2. 불필요한 sorted() 없음
   • 리스트에 추가하는 순서가 이미 정렬된 상태이므로 정렬이 필요 없음.
3. 빠른 탐색 구조
   • 숫자의 자리수를 검사하는 방식이므로 최악의 경우에도 O(KN) (K는 숫자의 자릿수, 최대 6).
   • 첫 번째 코드보다 훨씬 빠름.

♠ 두 코드 속도 비교

1. 최악의 경우 (l=1, r=1,000,000)
   • 첫 번째 코드: 불필요한 연산이 많아 더 느림.
   • 두 번째 코드: 숫자를 문자열로 변환한 뒤 자리수를 검사하는 방식이라 상대적으로 빠름.
2. 숫자 범위가 커질 때 (예: l=1, r=10,000,000)
   • 첫 번째 코드는 r+1까지 for 문을 도는 방식이라 더 심각하게 느려짐.
   • 두 번째 코드도 느려지지만, 불필요한 연산이 적기 때문에 그나마 더 빠름.

더 개선된 코드도 알려줬다..

def solution(l, r):
    answer = []
    for i in range(l, r+1):
        if set(str(i)) <= {'0', '5'}:
            answer.append(i)
    return answer if answer else [-1]

def solution(l, r):
    answer = [num for num in range(l, r + 1) if set(str(num)) <= {'0', '5'}]
    
    return answer if answer else [-1]

def solution(l, r):
    answer = []
    for num in range(l, r + 1):
        if not set(str(num)) - set(['0', '5']):
            answer.append(num)
    return answer if answer else [-1]

다른사람코드에 비슷한 코드가 있었다.

이 코드의 장점

1. set(str(i)) <= {'0', '5'}:
   • 문자열을 set으로 변환하면 중복 없이 숫자만 남음.
   • 예를 들어 "550" → {'5', '0'}인데, {'5', '0'}가 {'0', '5'}의 부분집합이면 올바른 숫자.
   • 불필요한 for 루프 제거, 더 간결함.
2. 최악의 경우에도 O(KN)
   • 기존 코드보다 연산이 줄어듦.
   • set 비교 연산이 빠르므로 최적화 효과가 큼.

** set의 비교연산자는 부분집합으로 계산한다.

---

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

    for i in range(l, r+1):
        if all([num in ['0', '5'] for num in str(i)]):
            answer.append(i)

    if len(answer) == 0:
        answer.append(-1)

    return answer

 

♣ all() 함수 동작

all() 함수는 리스트의 모든 값이 True인지 확인하는 함수입니다.

 

all([True, True, True]) # True all([False, False, False]) # False all([True, False, True]) # False

적용 예제

✅ 숫자가 '0'과 '5'로만 이루어진 경우 (i = 505)

if all([True, True, True]): # all()이 True 반환 answer.append(505)

✔️ 505는 answer 리스트에 추가됨.

❌ 숫자에 '0'과 '5' 이외의 숫자가 포함된 경우 (i = 123)

if all([False, False, False]): # all()이 False 반환 answer.append(123) # 실행 안 됨

❌ 123은 answer에 추가되지 않음.

---

def solution(l, r):
    answer = []
    i = 1
    n = 5

    while True:
        if n > r: break
        n = 5 * int(bin(i)[2:])
        if l <= n <= r:
            answer.append(n)
        i += 1

    return [-1] if len(answer) == 0 else answer

 이진법풀이....이렇게 생각해서 옮길 수 있다는 게 신기하다.

def solution(l, r):
    ret = []
    def f(lim, val):
        if lim == 0:
            ret.append(val)
            return

        f(lim - 1, val * 10 + 5)
        f(lim - 1, val * 10)

    f(6, 0)

    return list(i for i in ret if l <= i <= r)[::-1] or [-1]

이진법과 재귀함수 풀이