3655번 먼저 가세요
문제
설계
쉬워보였는데 생각할게 좀 많다.
양보를 하게되면 그룹의 첫 사람과 마지막 사람의 순서차이 * 5초만큼 이득이다.
공식 잘 만들면 되려나 싶어서 계산해봤는데 너무 복잡하다.
고려할게 너무 많다.
그렇다면 그리디는 어떨까?
큐를 만들어서 넣고 만지작거리는데 너무 오래걸릴 것 같은 예감
그리디도 결국 시뮬레이션인데 넣다 뺐다 하다보니 이게 맞나 싶다.
복잡한 두번째 예제를 보며 다시 정리를 해보자.
Ab9AAb2bC2
양보받은 경우를 가정하고 그룹별로 정리한다면?
그룹의 가장 마지막 사람이 앞으로 당겨오는 느낌으로 정리해야한다.
양보를 하면서 손해가 발생하면 절대 안된다.
9AAAbbbC22
이렇게 하고 각 그룹의 이득을 계산해보면(처음 줄의 마지막 인덱스와 정리 후 마지막 인덱스의 차)
A - 1
b - 1
9 - 2
2 - 0
C - 1
여기에 시간 5초와 각 그룹원의 수를 곱해주면
1 * 5 * 3 + 1 * 5 * 3 + 2 * 5 * 1 + 0 * 5 * 2 + 1 * 5 * 1 = 45
정답이 나왔다.
결국 정렬이 관건으로 보인다.
구현
1. 정렬
각 그룹의 전체 인원 수와 최초 상태에서의 마지막 인덱스를 찾아서 리스트로 만든 후 정렬한다.
분명 sort 함수를 쓰면 될건데…
Java나 C는 정렬함수를 커스텀해봤는데 Python은 해본 적이 없다.
일단 그냥 선택정렬을 직접 구현하고 풀고 난 다음에 공부하자.
n = int(input())
people = list(input().strip())
count = {}
last_index = {}
# 각 그룹 별 인원 수 카운팅
for i in range(n):
if people[i] not in count:
count[people[i]] = 1
else:
count[people[i]] += 1
# 그룹의 마지막 인덱스
last_index[people[i]] = i
groups = list(last_index.items())
# 그룹의 마지막 인덱스 기준으로 선택 정렬
for i in range(len(groups)):
idx = i
for j in range(i + 1, len(groups)):
if groups[idx][1] > groups[j][1]:
idx = j
groups[i], groups[idx] = groups[idx], groups[i]
2. 절약시간 구하기
위에서 예제로 확인했듯이 실제 절약된 시간은 (저장해둔 마지막 인덱스 - 현재 마지막 인덱스) * 5 * 인원 수 이다.
정렬한 리스트와 미리 찾아둔 값을 비교하여 계산한다.
result = 0
idx = 0
# 실제 절약된 시간 = (저장해둔 마지막 인덱스 - 현재 마지막 인덱스) * 5 * 인원 수
for group, index in groups:
group_count = count[group]
last_group_idx = idx + group_count - 1
time = (index - last_group_idx) * 5 * group_count
result += time
idx += group_count
print(result)
채점
반성
파이썬 sort 함수를 쓰면 어떻게 되는지 확인한다.
람다식을 쓰면 이렇게 된다.
groups = sorted(last_index.items(), key=lambda x: x[1])
이걸 def로 풀어쓰면 아래와 같다.
def get_last_index(item):
return item[1]
groups = sorted(last_index.items(), key=get_last_index)
풀어쓰니 모양이 익숙한게 자바랑 비슷해보인다.
다음에 정렬할 일 있으면 활용할 수 있겠다.
쉬운문제인줄 알고 대충 풀다가 어? 어? 하면서 갈아엎느라 유독 변수명이 개판된거 같다.
원래 변수명 신경쓰는 편은 아니지만 맘에 걸린다.
코드 확인