[백준] 6603. 로또 - 문제 풀이 (+파이썬 코드)

Question. 백준 6603. 로또

 

조합 문제다.

리스트에서 6개 숫자를 뽑아 만들 수 있는 조합을 사전 순으로 출력하는 것이다.

 

 

---

Answer.

 

python의 내장 함수 combinations를 사용하면 되지만 

실제 코딩 테스트에서는 itertools를 못 쓰게 하는 경우도 있어 직접 함수를 구현했다.

 

import sys
input = sys.stdin.readline
def solve(nums):
    results = []

    def dfs(nums, pos, sublist=[]):
        if sublist and len(sublist) == 6:
            results.append(sublist[:])

        for i in range(pos+1, len(nums)):
            dfs(nums, i, sublist + [nums[i]])

    dfs(nums, -1, [])
    return results

if __name__ == "__main__":
    while True:
        k, *S = map(int, input().split())
        if k == 0:
            break

        ans = solve(S)

        for i in ans:
            print(*i)
        print()

 

*(asterisk)를 이용하면 list에 있는 데이터를 가변적으로 unpack해서 쓸 수 있다.

파이썬의 Asterisk(*) 이해하기

 

sol 1)
Time Complexity	O(N^2)
Space Complexity	O(N) <- ?정확하지 않음