[백준 6603번] 완전 탐색 기법

 

 

[백준 6603번 - 로또]

 

https://www.acmicpc.net/problem/6603

6603번: 로또

 

(오답)

문제점: "독일 로또는 수 6개를 고른다"는 조건을 고려주지 않았다.

고칠점: 문제의 조건을 꼭 확인하고 시작하자.

import sys
from itertools import permutations
arr=[]

while True:
    a=list(map(int, sys.stdin.readline().split()))
    arr.append(a)
    if a[0]==0: break

for a in arr:
    for nums in list(permutations(a)):
        for n in nums:
            print(n, end=' ')
        print()
    if a==0: break

for a in arr:
    if a[0]==0:
        break

    else:
        a.pop(0)
        for nums in list(permutations(a)):
            print(map(''.join,nums))
        print()

 

 

📍 여기서 "S의 원소는 오름차순으로 주어진다"를 어떻게 처리하면 좋을지 고민해봤다.

from itertools import permutations, combinations
test=[1,2,3]
print(list(permutations(test,2))) #[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
print(list(combinations(test,2))) #[(1, 2), (1, 3), (2, 3)]

➡ 결국, 조합을 사용하란 의미와 같다.

  (permutations, combinations 출력 결과를 비교하면 알 수 있음)

 

 

 

(정답)

*메모리 29452KB, 72ms

*조합으로 바꿔서 바로 정답을 맞출 수 있었다.

import sys
from itertools import combinations
arr=[]

while True:
    a=list(map(int, sys.stdin.readline().split()))
    arr.append(a)
    if a[0]==0: break

for a in arr:
    if a[0]==0:
        break
    else:
        a.pop(0)
        for nums in list(combinations(a,6)):
            for n in nums:
                print(n,end=' ')
            print()
        print()

 

 

(정답2)

*메모리 29200KB, 68ms

*시간과 메모리 둘 다 줄일 수 있었다.

from itertools import combinations

while True:
    k,*s=list(map(int, input().split()))
    if k==0:
        break
    else:
        for nums in combinations(s,6):
            print(' '.join(map(str, nums)))
        print()

 

 

 

 

<공부>

 

📍 permutations(리스트, N): N개의 원소로 리스트의 순열 구하기

📍 list(permutations(리스트)): 리스트로 바꿔줘야 순열 결과를 확인할 수 있다.

from itertools import permutations
test=[1,2,3]
print(list(permutations(test,2)))

 

📍첫번째 값과 나머지 값들을 나누는 방법

*args: 파라미터를 몇 개 받을 지 모르는 경우 사용한다. (튜플 형태로 전달)

k, *s = list(map(int,input().split()))
print(k, s) # 7 [1, 2, 3, 4, 5, 6, 7]