[백준] 6603번 로또 -Python -조합, 백트래킹

카카오 온라인 코딩 테스트를 준비하기 위해 슬슬 알고리즘 문제들을 풀 때가 왔다.

간단하게 정리만 하고 다음 문제를 풀러 가자

백준 6603번 로또 문제는 여러 가지 알고리즘으로 문제를 풀 수 있다.

파이썬과 조합 함수 (itertools 모듈에 combinations 함수)를 사용하면 정말 쉽게 풀 수 있지만, 백트래킹으로도 풀어보고 싶어서 두 번 풀었다.

 

조합을 이용한 풀이법

---

combinations 함수를 호출하면 자동으로 사전 순으로 정렬해주기 때문에 정말 간단하게 풀 수 있는 문제이다.

정답 코드를 첨부하겠다.

from itertools import combinations
import sys
input=sys.stdin.readline

while 1:
    arr = input().split()

    if arr.pop(0) == '0':
        break

    for i in combinations(arr, 6):
        print(" ".join(i))

    print()

따로 정리할 개념도 없는 것 같다. 존재하는 좋은 함수들을 이용하는 게 가장 좋은 결과지만, 사실 실력이 늘진 않을 것 같아서 백트래킹으로 문제를 풀어보았다.

 

백트래킹을 이용한 풀이법

---

문제를 풀기 위해 제외할 규칙을 찾아보았다.

1. DFS를 사용하여 순회하되, 직전에 방문했던 노드보다 큰 값의 노드를 방문해야 한다.

2. 각 자리에 올 수 있는 원소는 'S'의 모든 원소가 아니다.

이 두 가지 조건을 잘 이용해 배제하여 문제를 풀어보자.

 

먼저 2번 조건을 적용시켜보자

예제의 입력 중 "7 1 2 3 4 5 6 7"이 입력된다고 가정해 보자. 0번 인덱스의 숫자는 'k'에 해당하는 값이니 pop(0)으로 제거해주면 [1, 2, 3, 4, 5, 6, 7]이 남는다. 조합을 찾기 위해 첫 번째 자리의 값을 1로 선택하면 문제없이 여러 개의 조합을 찾아낼 수 있지만, 4로 선택 시 적절한 조합이 존재하지 않는다. 오름차순 선택 조건 때문이다.

위 규칙을 적용하면 각 자리에 올 수 있는 숫자는 다음과 같다.

#ex) arr = [7, 1, 2, 3, 4, 5, 6, 7]
w = arr[0] - 5
range_arr = [arr[1+i:w+1+i] for i in range(6)]

각 자릿수를 i번째 자릿수라고 하면, arr배열에서 각 자릿수에 가능한 원소들의 인덱스는 [1 + i] ~ [k - 5+ (1 + i)]이다.

위 코드의 결과로 만들어진 range_arr는 [[1, 2], [2, 3], [3, 4,], [4, 5], [5, 6], [6, 7]]이다.

 

다음은 1번 조건을 만족시키는 DFS를 만들어보자.

def re_lotto(n,T):
    global range_arr
    for i in range_arr[n]:
        if i in T:
            continue
        else:
            if T[n-1] > i:
                continue
            if n < 5 :
                T[n] = i
                re_lotto(n+1,T)
                T[n + 1] = 0
            else:
                print(' '.join(map(str, T[:-1])),end=' ')
                print(i)


def lotto():
    global range_arr
    for i in range_arr[0]:
        T = [0,0,0,0,0,0]
        T[0] = i
        re_lotto(1,T)

lotto 함수를 먼저 실행하여 선택된 노드들이 표시될 T를 초기화시켜주고, DFS를 실행한다.

re_lotto 함수를 재귀적으로 실행하며 조건에 맞는 6개의 조합을 찾아낸 후 출력하게 된다.

배제 조건은 두 가지로 잡았다.

1. 이전에 방문했던 노드인가?

2. 방문했던 노드보다 작은 값인가?

두 조건에 해당한다면 다음 반복문으로 바로 넘어가게 알고리즘을 작성했다.

전체 코드

 

결과

---

제공된 는 모듈을 사용한 경우와 직접 알고리즘을 구현한 코드의 결과가 많이 차이가 나지 않는 것 같아서 기분이 좋다.

아래가 조합, 위가 백트래킹이다.

 

다음 문제 풀러 가자~