[백준 17281] ⚾ 야구 (python)

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

17281번: ⚾

⚾ 문제

주어진 야구 룰 대로 구현하여 점수를 구하는 문제

주어진 조건 중 일부를 구현을 어떻게하면 좋을지 생각했는데, 원하는 형태로 구현에 실패했음

다른 사람의 코드를 일부 참고하고서야 성공 할 수 있었다.

정답 코드

import sys
from itertools import permutations
N = int(sys.stdin.readline())
game = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
# 조건
# 1. 한 이닝에 3아웃이 발생하면 이닝 종료
# 2. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않으면 이닝 종료하지않음
# 3. 1번 이닝에서 6번 타자가 마지막이면 2번 이닝은 7번 타자부터 시작
# 4. 경기가 시작하기 전에 타순을 정해줘야함, 단 4번타자는 고정 1번 선수
order = [i for i in range(1,9)] # 고정된 4번타자 제외하고 순서를 정해주자.
result = float('-inf')
for x in permutations(order,8): # 8명의 순서의 조합을 따져본다.
    x = list(x)
    batter = x[:3] + [0] + x[3:] # 4번 조건. 1~3번 타자(랜덤 3명) / 1번 선수 (1번 선수) / 4~8번 타자(랜덤 5명)
    number, point = 0, 0 # 타수와 점수
    for i in range(N): # 각 이닝에 대해
        out = 0 #이닝이 돌면 out은 0으로 초기화
        p1 = p2 = p3 = 0 # 1~3루의 현재 상태
        while out < 3: # 1번, 2번 조건. out이 3번이 되기 전까지 반복
            #여기서부터 야구 룰
            if game[i][batter[number]] == 0:
                out += 1 
            elif game[i][batter[number]] == 1: 
                point += p3 
                p1, p2, p3 = 1, p1, p2
            elif game[i][batter[number]] == 2: 
                point += p2 + p3 
                p1, p2, p3 = 0, 1, p1
            elif game[i][batter[number]] == 3:
                point += p1 + p2 + p3
                p1, p2, p3 = 0, 0, 1
            elif game[i][batter[number]] == 4:
                point += p1 + p2 + p3 + 1
                p1, p2, p3 = 0, 0, 0
            number += 1 # 타순 증가
            if number == 9: #타순이 9가 되면
                number = 0 #다시 0으로 초기화
    # 3번 조건. 이닝이 끝나도 number을 초기화 하지 않으므로 다음이닝에 타순 유지
    result = max(result, point)
print(result)

이 문제 주의할 점은 python3로 하면 시간초과가 나고 pypy3로만 통과가 가능하다. 실제 A형 시험이었다면 pypy가 아니었어도 가능했을거라고 생각한다.

먼저 크게 이 문제의 조건은 아래와 같이 추릴 수 있다.

1. 한 이닝은 3아웃이 발생하면 종료
2. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않으면 이닝 종료하지않음
3. 이닝이 바뀌어도 타순은 고정, 예를 들어 1번 이닝에서 6번 타자가 마지막이면 2번 이닝은 7번 타자부터 시작
4. 경기가 시작하기 전에 타순을 정해줘야함, 단 4번타자는 고정 1번 선수

문제 해결을 위해서

1번 조건을 위해서 out을 변수로 횟수를 저장

2번 조건을 위해 while 문을 구성

3번 조건을 위해 각 이닝 시작할 때의 타순을 초기화하지 않고 유지

4번 조건을 위해 순열을 사용하면서도 중간에 4번 타자 자리에 1번 선수를 고정하기 위해 인덱스인 0을 삽입

위 형태로 작성을 하였다.

처음에 타순을 어떻게 정해주지 + 이걸 순열로 하면 경우의 수가 워낙 커져서 시간초과가 무조건 날것이란 생각에 다른 방법을 생각해보았으나, 마땅히 떠오르지 않아서 포기하고 그냥 순열을 사용했다.

야구룰을 구성하는 과정에서 처음에는 따로 3칸짜리 리스트를 만들어 pop, insert 형태로 구성을 했는데, 그 과정에서도 while문이 필요하고 이미 순열에서 엄청난 연산 수에 더 넣어버리니 시간초과를 벗어날 수 없었다. 다시 생각해보니 그냥 손쉽게 정렬할 때처럼 각 1~3루를 p1, p2, p3로 하고 숫자가 들어오면 p1, p2, p3를 밀어내는(자리를 바꾸는) 형태로 구현하면 참 쉽게 된다는걸 뒤늦게 깨달았다.

---

느낀 점

아직 구현 능력이 많이 부족하다는 걸 크게 느낀 문제였다. 사실 문제 자체는 크게 어려움이 없으나 제한된 시간안에, 심지어 더 줄어든 시간조건(실제 A형 시험에선 15초정도지만 백준은 1~2초)을 따지면서 해야하니 더 문제 해결에 어려움을 느꼈던거 같다.

또 연산 수를 충분히 줄일 수 있는 방법을 생각할 수 있는데 자꾸 연산이 늘어날만한 방법(리스트를 추가한다거나, pop, insert를 활용한다거나..)만 머리에서 떠오르는 점이 아쉽다. 다양한 코드를 접하고 타인의 코드를 보면서 더 쉽게 짤 수 있는 방법을 연습할 필요성을 느꼈고, 엄청 오랜 시간 잡아먹지 않으면서 구현 시도를 해볼 수 있는 좋은 문제였다고 생각한다.