[BOJ / 백준] 6603번 로또 파이썬(Python) 문제 풀이

문제

 

문제 링크 : https://www.acmicpc.net/problem/6603

6603번: 로또

 

 

 

 

CODE

방법 1

: itertools의 combinations 사용

import sys
from itertools import combinations

input = sys.stdin.readline

while True:
    nums = list(map(int, input().split()))
    if len(nums) == 1 and nums[0] == 0:
        break

    length = nums.pop(0)

    for comb in combinations(nums, 6):
        temp = list(map(str, comb))
        print(" ".join(temp))
    print()

 

 

방법 2

: DFS / 백트래킹

import sys

input = sys.stdin.readline


def dfs(lotto, nums, visited):
    if len(lotto) == 6:
        for i in range(6):
            print(nums[lotto[i]], end=' ')
        print()
        return

    t_visited = visited[:]
    for i in range(len(t_visited)):
        if not t_visited[i]:
            t_visited[i] = True
            dfs(lotto + [i], nums, t_visited)


while True:
    nums = list(map(int, input().split()))
    if len(nums) == 1 and nums[0] == 0:
        break

    length = nums.pop(0)

    visited = [False] * len(nums)
    dfs([], nums, visited)
    print()

 

 

 

 

풀이

💡 idea

- DFS 연습 하려고 찾은 문제인데 보자마자 조합쓰면 풀리겠는데,,,싶어진 문제

- 그래서 itertools의 combinations를 사용한 방법 1, 

  백트래킹으로 푼 방법 2로 두 번 코드를 작성해보았다

 

- combinations를 사용하는 것이 시간도 단축되고(차이는 적지만) 코드도 간단하다

    * 맞은 사람들 코드를 구경하니 다들 itertools로 푸셨네요

 

- 처음 제출할 때에는 사전 순 출력을 위해 sort를 해주었었는데, 입력이 오름차순으로 주어진다는 조건이 있어서 정렬하지 않아도 무관했다..!

 

 

 

 

 

결과

방법 1) combinations

 

방법 2) 백트래킹