[BOJ] 17281 ⚾ 파이썬

50.283% 문제 ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다. 두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다. 타순은 이닝이 변경되어도 순서를 유지해야 한다. 예를 들어, 2이닝에 6번 타자가 마지막 타자였다면, 3이닝은 7번 타자부터 타석에 선다. 공격은 투수가 던진 공을 타석에 있는 타자가 치는 것이다. 공격 팀의 선수가 1루, 2루, 3루를 거쳐서 홈에 도착하면 1점을 득점한다. 타자가 홈에 도착하지 못하고 1루, 2루, 3루 중 하나에 머물러있을 수 있다. 루에 있는 선수를 주자라고 한다. 이닝이 시작될 때는 주자는 없다. 타자가 공을 쳐서 얻을 수 있는 결과는 안타, 2루타, 3루타, 홈런, 아웃 중 하나이다. 각각이 발생했을 때, 벌어지는 일은 다음과 같다. 안타: 타자와 모든 주자가 한 루씩 진루한다. 2루타: 타자와 모든 주자가 두 루씩 진루한다. 3루타: 타자와 모든 주자가 세 루씩 진루한다. 홈런: 타자와 모든 주자가 홈까지 진루한다. 아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가한다. 한 야구팀의 감독 아인타는 타순을 정하려고 한다. 아인타 팀의 선수는 총 9명이 있고, 1번부터 9번까지 번호가 매겨져 있다. 아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다. 이제 다른 선수의 타순을 모두 결정해야 한다. 아인타는 각 선수가 각 이닝에서 어떤 결과를 얻는지 미리 알고 있다. 가장 많은 득점을 하는 타순을 찾고, 그 때의 득점을 구해보자. 입력 첫째 줄에 이닝 수 N(2 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에는 각 선수가 각 이닝에서 얻는 결과가 1번 이닝부터 N번 이닝까지 순서대로 주어진다. 이닝에서 얻는 결과는 9개의 정수가 공백으로 구분되어져 있다. 각 결과가 의미하는 정수는 다음과 같다. 안타: 1 2루타: 2 3루타: 3 홈런: 4 아웃: 0 각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다. 출력 아인타팀이 얻을 수 있는 최대 점수를 출력한다.

 

규칙만 이해하고 구현만하면 되는 코드이다.

그런데 python3으로 푼사람이 0명?

그말은... C/C++ 같은 로우레벨언어로는 간단히 풀 수 있지만, 파이썬으로는 극한의 시간최적화가 필요하다는 말이된다.

그나마 pypy3으로 제출해야 맞을 수 있다는 문제였다.

물론 나도 내가 할 수 있는 한 최대로 최적화를 해서 제출했으나 어림도 없었다.

결국엔 어떤 풀이를 올린 고수분의 코드에서 아이디어를 얻어서 풀었다.

 

시간초과코드

import sys
from itertools import permutations
input = sys.stdin.readline
ining_num = int(input().rstrip())

ining_res = []
for _ in range(ining_num):
    ining_res.append(list(map(int, input().rstrip().split(" "))))


def getScore(ining, i, tmp_ans, curr_pos):
    out_count = 0
    while(out_count < 3):  # 아웃 3번채울때까지 해당이닝 무한반복
        curr_player = order[i]
        if(ining[curr_player] == 0):  # 아웃이면 체크하고
            out_count += 1
        else:  # 아웃아니면 그에 맞은 액션취함
            curr_pos.append(1)  # 현재주자 추가
            tmp_ans += sum(curr_pos[0:ining[curr_player]])

            curr_pos = curr_pos[ining[curr_player]:]
            curr_pos.extend([0]*(ining[curr_player]-1))

        i = (i+1) % len(ining)  # 다음 플레이어
    return i, tmp_ans, curr_pos


answer = 0
for order in permutations(range(1-1, 10-1), 9):  # 1~9까지 순열
    if(order[4-1] != 1-1):  # 1번선수가 4번자리에 없으면 다시
        continue
    tmp_ans = 0

    i = 0
    for ining in ining_res:
        curr_pos = [0, 0, 0]  # 1,2,3루
        i, tmp_ans, curr_pos = getScore(ining, i, tmp_ans, curr_pos)

    answer = max(answer, tmp_ans)


print(answer)
# print(ans_l)

 

위 코드를 보면, 논리적으로는 맞는 문제이다. 하지만 코드의 성능을 떨어뜨리는 요소가 2개 있었으니

1. 아웃이 아닐때 액션이 list값을 pop하고 append하는 슬라이싱이다.

2. 처음에 permutation으로 모든 순열을 구하고, 4번째 값이 첫번째 타자인지 검증한다.

 

이다. 2 두가지를 개선하니 바로 통과할 수 있었다.

 

 

개선코드

import sys
from itertools import permutations
input = sys.stdin.readline
ining_num = int(input().rstrip())

ining_res = []
for _ in range(ining_num):
    ining_res.append(list(map(int, input().rstrip().split(" "))))


def getScore(ining, i, tmp_ans):
    out_count = 0
    base3, base2, base1 = 0, 0, 0  # list슬라이싱말고 변수 3개로 대입하는 방식으로 표현
    while(out_count < 3):  # 아웃 3번채울때까지 해당이닝 무한반복
        if(ining[order[i]] == 0):  # 아웃이면 체크하고
            out_count += 1
        elif(ining[order[i]] == 1):
            tmp_ans += base3
            base3, base2, base1 = base2, base1, 1
        elif(ining[order[i]] == 2):
            tmp_ans += (base3+base2)
            base3, base2, base1 = base1, 1, 0
        elif(ining[order[i]] == 3):
            tmp_ans += (base3+base2+base1)
            base3, base2, base1 = 1, 0, 0
        elif(ining[order[i]] == 4):
            tmp_ans += (base1+base2+base3 + 1)
            base1, base2, base3 = 0, 0, 0

        i = (i+1) % 9  # 다음 플레이어
    return i, tmp_ans


answer = 0
for order in permutations(range(1, 9), 8):  # 1~8까지 순열
    # if(order[4-1] != 1-1):  # 1번선수가 4번자리에 없으면 다시
    #     continue

    # 모든 순열을 구한뒤 4번째자리가 첫번째 투수인지 체크하는 방법 보다는
    # 1~8까지 배치후에 4번쨰자리에 첫번쨰 투수를 삽입하는 방법 사용
    order = (*order[:3], 0, *order[3:])

    tmp_ans = 0

    i = 0
    for ining in ining_res:
        i, tmp_ans = getScore(ining, i, tmp_ans)

    answer = max(answer, tmp_ans)


print(answer)
# print(ans_l)

1. list슬라이싱하지 않고, 1,2,3루를 3개의 변수로 표현하여, 옮겨줬으며

2. 1~8까지의 플레이어를 배치하고 4번째에 0번째 선수를 넣어주는 방식으로 모든 순열의 조합을 구할 필요가 없어졌다.

 

이런 최적화되는 지식을 많이 알아둬야겠다. 이건 알고리즘을 알아도 코드의 특성을 이해하지 못하면 파이썬으로 풀 수 없었던 문제였다.