Softeer Level 3 교차로 Python

문제 링크

https://softeer.ai/practice/6256

Softeer - 현대자동차그룹 SW인재확보플랫폼

정답 코드

import sys
from collections import deque

input = sys.stdin.readline
N = int(input())

roDict = {
  "A": 0,
  "B": 1,
  "C": 2,
  "D": 3
}
rotaries = [deque() for _ in range(4)]
for idx in range(N):
  time, rotary = input().split()
  rotaries[roDict[rotary]].append([idx, int(time)])

result = [-1 for _ in range(N)]
# 4개의 로터리를 확인한다.
while rotaries[0] or rotaries[1] or rotaries[2] or rotaries[3]:
  nowTime = int(1e11)
  for i in range(4):
    if rotaries[i]:
      nowRTime = rotaries[i][0][1]
      if nowRTime <= nowTime:
        nowTime = nowRTime
        
  nowStack = [[] for _ in range(4)]
  cnt = 0
  for i in range(4):
    if rotaries[i]:
      nowRTime = rotaries[i][0][1]
      # 같은 시각에 로터리에 진입하는 차를 찾는다.
      # 찾아서 일단 분류한다.
      if nowRTime == nowTime:
        nowStack[i] = rotaries[i].popleft()
        cnt += 1
  # print(nowStack)
  if cnt == 4:
    break

  for idx in range(4):
    right = (idx + 3) % 4
    if nowStack[idx]:
      newTime = nowStack[idx][1] + 1
      tmpRotary = [nowStack[idx][0], newTime]
      if nowStack[right]:
        # 못가니까 다시 집어 넢어
        rotaries[idx].appendleft(tmpRotary)
      else:
        # 갈 수 있으니까
        result[nowStack[idx][0]] = nowStack[idx][1]
        # 갈 수 있지만 뒤차랑 지금 차 시간이 같다면?
        if rotaries[idx]:
          if rotaries[idx][0][1] <= newTime:
            rotaries[idx][0][1] = newTime

for res in result:
  print(res)

반례

6
1 A
1 B
1 C
2 D
3 D
4 D

3
1000000000 A
1000000000 B
1000000000 C

풀이 방법

1. A, B, C, D를 각각의 deque으로 만들고 입력된 값을 넣어준다.

2. 로터리 4개에서 같은 시간(nowTime)에 교차로에 진입하는 자동차들을 구한다.

    2-1. 동시에 진입하는 자동차가 4대인 경우 고착상태에 빠지게 되므로 break를 통해 while문을 종료시킨다.

3. 해당 자동차를 또 비교해서 오른쪽에 차가 없는 경우만 출발 시킨다.

    3-1. 오른쪽에 차가 있는 경우에 현재 자동차는 출발할 수 없다.

        3-1-1. 출발할 수 없는 자동차는 현재 시간에 + 1을 해준뒤 appendleft를 통해 다시 넣어준다.

    3-2. 차가 없다면 출발을 한다. 하지만 현재 교차로에 차가 또 있는지 확인한다.

        3-2-1. 차가 하나 더 존재하고 현재 시간 보다 작거나 같은 경우 다음 차의 시간은 현재 시간 + 1을 해준다.

    3-3. 출발한 자동차는 result라는 리스트의 idx번 째 값에 현재 시간을 넣는다.

4. result값을 출력해준다.

느낀점

- 문제점이 세 가지가 존재했다.

    1. nowTime을 1e9로 설정했다.

        - 10**9 이상의 값이 오면 10**9+1 의 값이 줄지어서 나오기 때문에 while문을 벗어날 수 없어서 시간초과가 난다.

    2. result를 빈 리스트로 만들었다.

        - N이 200,000인 경우 append를 20만번 진행해야 하므로 시간초과가 발생한다.

    3. 현재 자동차가 출발했다고 다음 자동차의 시간을 고려하지 않았다.

        - 그 결과 위의 반례를 도출할 수 있었다.

        - 맨 위 반례의 정답은 0 1 2 3 4 5이다.

- 자동차를 직접 움직였으므로 시뮬레이션이라고 봐야한다.

- 완전탐색은 정말 모두 다 탐색해야 하고 그리디는 최적해를 찾는 방식이다. 그러므로 그리디는 아니다.