📃문제
빙고 게임은 다음과 같은 방식으로 이루어진다.
먼저 아래와 같이 25개의 칸으로 이루어진 빙고판에 1부터 25까지 자연수를 한 칸에 하나씩 쓴다
다음은 사회자가 부르는 수를 차례로 지워나간다. 예를 들어 5, 10, 7이 불렸다면 이 세 수를 지운 뒤 빙고판의 모습은 다음과 같다.
차례로 수를 지워가다가 같은 가로줄, 세로줄 또는 대각선 위에 있는 5개의 모든 수가 지워지는 경우 그 줄에 선을 긋는다.
이러한 선이 세 개 이상 그어지는 순간 "빙고"라고 외치는데, 가장 먼저 외치는 사람이 게임의 승자가 된다.
철수는 친구들과 빙고 게임을 하고 있다. 철수가 빙고판에 쓴 수들과 사회자가 부르는 수의 순서가 주어질 때, 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지를 출력하는 프로그램을 작성하시오.
📃입력
첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 빙고판에 쓰여진 수와 사회자가 부르는 수는 각각 1부터 25까지의 수가 한 번씩 사용된다.
📃출력
첫째 줄에 사회자가 몇 번째 수를 부른 후 철수가 "빙고"를 외치게 되는지 출력한다.
📃예제 입력 1
11 12 2 24 10
16 1 13 3 25
6 20 5 21 17
19 4 8 14 9
22 15 7 23 18
5 10 7 16 2
4 22 8 17 13
3 18 1 6 25
12 19 23 14 21
11 24 9 20 15
📃예제 출력 1
15
✏️문제 탐색하기
5x5 빙고판에서 주어진 숫자를 차례로 지우면서 빙고의 개수를 확인하는 문제입니다. 빙고는 가로, 세로, 대각선의 한 줄이 모두 지워졌을 때 완성됩니다. 사회자가 몇 번째 숫자를 불렀을 때 빙고가 3줄 이상 완성되는지를 출력해야 합니다.
주어진 조건:
- 사회자가 부르는 숫자는 총 25개이며 빙고판의 숫자와 마찬가지로 1부터 25까지의 자연수가 중복 없이 한 번씩 등장.
- 빙고가 3줄 이상 완성되는 순간, 해당 숫자가 몇 번째로 불렸는지 출력. <- 이게 핵심
가능한 시간복잡도
check_bingo 함수는 가로줄 5개, 세로줄 5개, 대각선 2개를 확인.
각 줄의 숫자를 확인하는 데 O(5) 시간이 걸리므로, 전체적으로 O(12 5) = O(60)의 시간 복잡도가 소요.
이 함수는 각 숫자가 불릴 때마다 호출되므로, 최악의 경우 25번 호출될 수 있어 빙고 개수 확인의 총 시간 복잡도는 O(25 60) = O(1500)이다.
✏️알고리즘 선택
완전 탐색 알고리즘을 사용하여 각 숫자 호출 시마다 빙고판을 업데이트하고 모든 줄을 검사해 빙고 개수를 세는 방식으로 접근하는 것이 적합.
✏️코드 설계하기
- 5x5 빙고판과, 사회자가 부르는 25개의 숫자를 입력받아 bingo_list와 call_list로 저장합니다.
- bingo_list는 2차원 리스트로, call_list는 1차원 리스트로 저장합니다.
- check_bingo(bingo_list) 함수를 정의하여 현재 빙고판에서 완성된 빙고 줄의 개수를 반환합니다.
- 가로, 세로, 대각선의 줄을 검사하여 모두 0인 줄이 있을 경우 빙고 개수를 증가시킵니다.
- call_list에서 숫자를 하나씩 순서대로 가져와 bingo_list에서 해당 숫자를 찾아 0으로 변경합니다.
- 숫자를 지운 후 check_bingo 함수를 호출하여 현재 빙고 개수를 확인합니다.
- 빙고 개수가 3개 이상이 되면 몇 번째 숫자에서 빙고가 완성되었는지 출력하고 종료합니다.
✏️시도 회차 수정 사항
1회차
- 이번 문제는 꽤 애먹은 문제.. 갈피를 못 잡아서 생각보다 시간이 오래 걸렸고 머리도 많이 씀. 내가 바본가 싶을 정도 ㅠ
- for문과 if문이 너무 많아서 이게 맞나 싶어서 찾아 본 결과, all함수라는 게 있다고 한다. 함수 안에 iterable한 객체를 받아서 모든 요소가 True일 때 True를 반환함. 그래서 모든 요소가 True인지 확인할 때 즉 조건이 모두 만족될 때 자주 사용한다고 한다.
2회차
if check_bingo(bingo_list) >= 3:
print(i+1)
break- check_bingo 함수를 사용해서 값을 출력하게끔 구현해놨는데 반복문에 많아질 때 항상 헷갈리는 문제가 이번에도 발생,,, 위치를 가장 안쪽 for문에 위치해서 원하는 값이 안 나옴
결국 하나씩 타고 타고 계산하면서 알맞은 위치에 놓고 실행해보니 정답! 힘들었다,,,
✏️코드 구현
import sys
bingo_list = []
call_list = []
for i in range(10):
num = list(map(int, sys.stdin.readline().split()))
if i < 5:
bingo_list.append(num)
else:
call_list.extend(num)
def check_bingo(bingo_list):
count = 0
for k in range(5):
if all(bingo_list[k][h] == 0 for h in range(5)):
count += 1
for h in range(5):
if all(bingo_list[k][h] == 0 for k in range(5)):
count += 1
if all(bingo_list[k][k] == 0 for k in range(5)):
count += 1
if all(bingo_list[k][4 - k] == 0 for k in range(5)):
count += 1
return count
for i in range(len(call_list)):
for j in range(len(bingo_list)):
for k in range(len(bingo_list)):
if call_list[i] == bingo_list[j][k]:
bingo_list[j][k] = 0
if check_bingo(bingo_list) >= 3:
print(i+1)
break
