정글사관학교 11일차 TIL: 숫자 야구(#2503), 독일 로또(#6603)

오늘은 1주차 알고리즘 시험날.

 

문제는 #1924, #2503, #6603이 나왔고 1시간 반 동안 푼 문제는 #1924와 #6603으로 3문제 중 2문제. 오늘 시험 목표가 2문제 이상 맞추기였으니 선방은 했는데, 생각보다 1924와 6603을 쉽게 풀어 2503까지 풀지 못한 건 좀 아쉽긴 하다.

 

시험이 끝나고 바로 2주차 문제가 주어졌으나, 오늘은 푼 문제를 리뷰하면서 시간을 보냈다. 오후에는 #2503을 푸는데 시간을 썼다. 어렵다고 생각했지만 조금 해보니 어느 정도 감이 잡히더라. 스트라이크와 볼을 if문 두 번으로 처리하는 개념만 잘 생각하면 괜찮다.

 

오히려 쉽게 풀었던 #6603에서 시간을 많이 썼는데, 재귀를 이용한 다른 풀이를 익히느라 고생했다. 시험에서는 조합을 이용해 쉽게 풀었으나 원래 문제(및 코치님)의 의도는 재귀를 이용해 풀라는 뜻이었다고 한다. 실제로도 난이도는 #2503이 solved.ac에서 실버 4인 것과 달리 #6603이 실버 2였다. 아마 재귀를 이용할 경우 어려운 난이도여서 그런듯. 개인적으로 재귀는 정말 손에 잘 익지 않아 이를 연습하느라 시간을 많이 썼다.

 

차례대로 푼 문제를 리뷰해보자.

 

1. 2007년 문제 (#1924)

 

문제
오늘은 2007년 1월 1일 월요일이다. 그렇다면 2007년 x월 y일은 무슨 요일일까? 이를 알아내는 프로그램을 작성하시오.

입력
첫째 줄에 빈 칸을 사이에 두고 x(1 ≤ x ≤ 12)와 y(1 ≤ y ≤ 31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다.

출력
첫째 줄에 x월 y일이 무슨 요일인지에 따라 SUN, MON, TUE, WED, THU, FRI, SAT중 하나를 출력한다.

이 문제는 y일에 x월에 해당하는 일자 수 만큼 더해준 뒤, 최종 y를 7로 나눈 나머지로 요일을 구하면 된다. 코드를 보면 쉽게 이해가 가능하다.

 

from sys import stdin

x, y = map(int, stdin.readline().split())
 #         1    2    3    4    5    6    7    8    9    10    11    12
month_add = [31, 28, 31, 30,  31,  30,  31,  31,  30,   31,   30,  31]

#y에 달만큼 업데이트
if x != 1:
    for i in range(x-1):
        y += month_add[i]

date = ['SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT']

for i in range(7):
    if y % 7 == i:
        print(date[i])

 

2. 숫자 야구 (#2503)

이 문제는 내용이 기니까 직접 들어가서 확인해보도록 하자. 풀이의 논리와 코드를 함께 보자.

 

풀이는 다음과 같다.

 

먼저, 입력을 받기 위해 세팅하고 123부터 987까지 모든 경우의 순열을 생성한다.

from sys import stdin
from itertools import permutations

count = int(stdin.readline()) #민혁이가 내지르는 질문 개수
sub_list = [list(map(int, stdin.readline().split())) for _ in range(count)] #민혁이의 예상 답안, 그에 대한 strike, ball을 담은 리스트

num_list = list(range(1, 10)) # 1부터 9까지 자연수를 담은 리스트. 순열을 만들기 위해 사용.

total_case = permutations(num_list, 3) # 서로 다른 세 자연수로 만든 모든 경우의 수에 해당하는 순열
ans = [] #최종 답안 저장

 

이 중 한 순열을 뽑아내서 민혁이가 질문하는 예상 답안과 비교해 strike, ball을 계산한다. (이 때 strike, ball을 s_cnt, b_cnt라 하자.)

 

내가 계산한 strike, ball과 영수가 대답했던 s, b와 비교해 s==s_cnt, b==b_cnt인 경우에만 뽑아낸 순열을 정답 리스트에 저장한다. 최종적으로 모든 순열에 대해 for문을 돌려서 답안 리스트를 뽑아낸다. 마지막으로, 답안 리스트의 원소 개수(len)을 정답으로 반환한다.

for i in total_case:
    # i = tuple
    cnt =0
    for j in sub_list:
        num = list(map(int, str(j[0])))
        s = int(j[1])
        b = int(j[2])
        s_cnt = 0
        b_cnt = 0
        for k in range(3):
            if num[k] in i:
                if k == i.index(num[k]):
                    s_cnt +=1
                    # print("s_cnt is: ", s_cnt)
                else:
                    b_cnt +=1
        if (s != s_cnt) or (b != b_cnt):
            break
        else:
            cnt +=1
            if cnt == count:
                ans.append(i)

전체 코드는 아래와 같다.

 

from sys import stdin
from itertools import permutations

count = int(stdin.readline())
sub_list = [list(map(int, stdin.readline().split())) for _ in range(count)]

num_list = list(range(1, 10))

total_case = permutations(num_list, 3)
ans = []

for i in total_case:
    # i = tuple
    cnt =0
    for j in sub_list:
        num = list(map(int, str(j[0])))
        s = int(j[1])
        b = int(j[2])
        s_cnt = 0
        b_cnt = 0
        for k in range(3):
            if num[k] in i:
                if k == i.index(num[k]):
                    s_cnt +=1
                    # print("s_cnt is: ", s_cnt)
                else:
                    b_cnt +=1
        if (s != s_cnt) or (b != b_cnt):
            break
        else:
            cnt +=1
            if cnt == count:
                ans.append(i)

print(len(ans))

 

 

3. 독일 로또 (#6603)

문제
독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다.
([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. 

출력
각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

 

풀이 1: 순열을 이용

순열을 이용한 풀이는 정말 정말 간단한 편인데, 딱히 설명할 것도 없다. 그냥 각 입력에 대한 kPs 를 구하면 끝이다. 너무 간단해서 더 얘기하면 입 아프다.

 

# Solution 1: 순열을 이용한 풀이

from sys import stdin
from itertools import combinations


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

for case in lists:
    k = case[0]
    for j in combinations(case[1:], 6):
        print(" ".join(list(map(str, j))))
    print()

 

 

풀이 2: 재귀를 이용

하지만 재귀를 이용하게 되면 이야기는 완전히 달라진다... 아직도 재귀가 손에 익지 않아 아래 풀이는 계속 손으로 쓰고 머리로 익혀야 할듯.

 

재귀를 짤 때는 크게 두 가지를 고려해야 한다.

 

1. 종료 조건
2. 재귀를 이용한 반복문

가장 먼저 종료 조건부터 짠다. 종료 조건을 짤 때는 아래에서 짜게 될 재귀 반복문이 가장 작은 곳에서 출발하거나 가장 큰 곳에서 출발할 텐데 특정 지점에 재귀문이 도달하게 될 경우 return하는 식으로 짠다.

 

if (종료 조건):
    Action 1
    Action 2
	return

이후에는 재귀를 호출해 반복문을 짜는데, 이때 재귀에 들어가는 값을 1씩 올리거나 내려서 종료 조건에 도달할 때까지 반복하도록 한다.

for i in range():
    if (조건 만족):
        재귀(i+1)

 

본 문제에서는 아래와 같이 문제를 풀었다.

 

# Solution 2: 재귀를 이용한 풀이
from sys import stdin

def lotto_pick(chosen, idx):
    # 1. 종료 조건 짜기: 아래에서 올린 입력값이 특정 선에 도달하면 종료를 선언하도록 설계
    if len(chosen) == 6: # 총 6개 골라야 하는데 6개 다 골랐을 경우
        print(" ".join(list(map(str, chosen))))
        print() #숫자끼리 칸 띄우기
        return

    # 2. 재귀 호출해 반복문 짜기 => 이때 재귀에 들어가는 값을 1씩 올린다.
    for i in range(idx, 50): # 로또에 들어가는 숫자: 1부터 49
        if i in picks: # picks는 입력에 들어가는 테스트 케이스를 의미. 즉, 1부터 49 사이 숫자(i) 중 테스트 케이스에 존재한다면
            chosen.append(i) # 그 숫자를 로또에 넣을 숫자로 지정해라.
            lotto_pick(chosen, i+1) # 고르고 나면 lotto_pick을 2부터 49까지 스캔. 또 하면 3부터, 4부터, ... 49까지.
            chosen.pop() # 위에서 lotto_pick이 6까지 채우고 나면 맨 끝에 채워진 애를 빼낸다. 다른 애를 채워 넣어야 하니.
pick_num = 1

while pick_num !=0:
    testcase = list(map(int, stdin.readline().split()))
    pick_num = testcase[0] # k 개수
    picks = testcase[1:] # 리스트 k
    lotto_pick([], 1) # 재귀는 가장 작은 값부터 출발
    print()