분명 알고리즘 문제가 메인이 아니었는데 왜 이거만 올리고 있지..
문제
⚾는 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
각 이닝에는 아웃을 기록하는 타자가 적어도 한 명 존재한다.
출력
아인타팀이 얻을 수 있는 최대 점수를 출력한다.
처음 생각했던 점수 산정 방법
풀이1 - 시간 초과
점수산정 방식
=> base라는 deque를 만들어서 진루타를 칠 때마다 앞에 추가해주고 뒤에서 pop한 값을 더해줬다.
import sys
from itertools import permutations
from collections import deque
input = sys.stdin.readline
inning = int(input())
hitting = [list(map(int, input().split())) for _ in range(inning)]
max_score = 0
def game(line_ups):
idx = 0
score = 0
for each_inning in hitting:
out = 0
base = deque([0, 0, 0])
while True:
if out == 3:
break
if each_inning[line_ups[idx]] == 0:
out += 1
elif each_inning[line_ups[idx]] == 1:
base.appendleft(1)
score += base.pop()
elif each_inning[line_ups[idx]] == 2:
base.appendleft(1)
base.appendleft(0)
score += base.pop()
score += base.pop()
elif each_inning[line_ups[idx]] == 3:
base.appendleft(1)
base.appendleft(0)
base.appendleft(0)
score += base.pop()
score += base.pop()
score += base.pop()
elif each_inning[line_ups[idx]] == 4:
base.appendleft(1)
base.appendleft(0)
base.appendleft(0)
base.appendleft(0)
score += base.pop()
score += base.pop()
score += base.pop()
score += base.pop()
idx = (idx + 1) % 9
return score
for line_ups in permutations(range(1, 9), 8):
line_ups = list(line_ups[:3]) + [0] + list(line_ups[3:])
max_score = max(max_score, game(line_ups))
print(max_score)오늘도 가차없이 시간초과를 때려주는 냉정한 백준
풀이2 - deque말고 값으로 대체
import sys
from itertools import permutations
from collections import deque
input = sys.stdin.readline
inning = int(input())
hitting = [list(map(int, input().split())) for _ in range(inning)]
max_score = 0
def game(line_ups):
idx = 0
score = 0
for each_inning in hitting:
out = 0
# base = deque([0, 0, 0])
b1, b2, b3 = 0, 0, 0
while True:
if out == 3:
break
if each_inning[line_ups[idx]] == 0:
out += 1
elif each_inning[line_ups[idx]] == 1:
# base.appendleft(1)
# score += base.pop()
score += b3
b1, b2, b3 = 1, b1, b2
elif each_inning[line_ups[idx]] == 2:
# base.appendleft(1)
# base.appendleft(0)
# score += base.pop()
# score += base.pop()
score += (b2 + b3)
b1, b2, b3 = 0, 1, b1
elif each_inning[line_ups[idx]] == 3:
# base.appendleft(1)
# base.appendleft(0)
# base.appendleft(0)
# score += base.pop()
# score += base.pop()
# score += base.pop()
score += (b1 + b2 + b3)
b1, b2, b3 = 0, 0, 1
elif each_inning[line_ups[idx]] == 4:
# base.appendleft(1)
# base.appendleft(0)
# base.appendleft(0)
# base.appendleft(0)
# score += base.pop()
# score += base.pop()
# score += base.pop()
# score += base.pop()
score += (1 + b1 + b2 + b3)
b1, b2, b3 = 0, 0, 0
idx = (idx + 1) % 9
return score
for line_ups in permutations(range(1, 9), 8):
line_ups = list(line_ups[:3]) + [0] + list(line_ups[3:])
max_score = max(max_score, game(line_ups))
print(max_score)기존의 코드를 그대로 두고 base를 deque로 했던 것을 그냥 값(?)으로 바꿔줬다.
deque가 O(1)의 시간복잡도를 가지고 있기 때문에 별차이 없을 것이라 생각했는데 그렇지 않았다.
itertools 사용하기
itertools란?
효율적인 루핑을 위한 이터레이터를 만드는 함수라고 써져있다.
itertools에는 수많은 이터레이터가 존재하지만 그 중에서 자주 쓰이는 것 같은 combination과 permutations에 대해 짚고 넘어가보자!
이게 느리다는 것으로 알고 있어서 그냥 무시하고 지나갔었는데 알고 있으면 확실히 이런 문제에 도움이 될 것이라는 생각이 든다!!
처음에 이 문제를 접했을 때 순열로 풀어야겠다는 생각은 했는데 막상 순열을 구현하기가 어려울 때 파이썬의 장점을 가장 극대화할 수 있는 무기가 아닐까? (이래서 코테는 파이썬으로 하라고 하나보다)
combination 즉, 조합이다!
순열과 조합을 배웠다면 뭔지 들어보기는 했을 것이다.
조합은 A,B와 B,A를 같은 것으로 본다. 즉, 중복을 허용하지 않는다고 생각하면 된다.
순서가 중요하면 아래 permutation, 순열을 사용하면 된다!
가령 1,2,3과 1,3,2의 경우 내용물은 똑같지만 순서가 다르다.
permutation의 경우 3가지 원소에서 순서를 정하기 위해
1,2,3 / 1,3,2 / 2,1,3 / 2,3,1 / 3,1,2 / 3,2,1/
이런식으로 모두 같은 원소지만 순서가 다른 것들도 다 나오게 한다.
반대로 조합의 경우 3가지 원소 중에 3가지를 모두를 뽑는 방법은
1,2,3 /
단 하나만 존재하는 것이다! 이게 순열과 조합의 차이이.
각설하고, 사용법은 이렇다.
itertools 활용 -> combination
from itertools import combinations
example = ['a', 'b', 'c']
cb = list(combinations(example, 2))
print(cb)
[('a', 'b'), ('a', 'c'), ('b', 'c')]example 내에 있는 3개의 원소 중에 2개를 고르는 조합이다.
3C1이니까 3개가 나오는 것은..설명하지 않겠다.
itertools 활용 -> permutation
from itertools import permutations
example = [1, 2, 3]
perm = list(permutations(example, 2))
print(perm)
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]순열의 경우 모든 줄세우기가 가능한 경우가 다 나온다.
3개의 원소 중 2개를 뽑아 줄을 세우는 경우이기 때문에
1,2를 뽑더라도 1,2만 나오는 것이 아닌 2,1도 포함 된다.
결론
itertools 사용법을 익히면 분명 도움이 될 것이다!! (코테 한정)
- 꼭 queue를 사용하는 것을 고집하지 말고 변수로 대체 가능한지 생각해보자.
- 유연한 사고
