문제 설명
라이캣과 자바독은 오랜 기다림 끝에 드디어 배에 올랐습니다. 다른 승객들도 마찬가지로 지친 모습이었죠. 긴 대기 시간으로 인해 모두의 몸과 마음이 지쳐있었습니다. 그런데 예상치 못한 문제가 발생했어요. 승객 수보다 자리가 부족했던 것입니다. 이로 인해 자리를 차지하려는 다툼이 일어나기 시작했고, 결국 아무도 편히 앉지 못하는 상황이 되고 말았습니다.

라이캣은 조용히 읊조렸어요.
"상황과 환경은 그 사람이 어떤 사람인지를 드러낸다냥. 본능에 따르기 보다는 우리답게 해결할 방법을 찾아야 한다냥."
그때 한 개구리가 나서며 말했어요.
"나는 개리라 한다! 개굴! 이대로 가다간 아무도 앉지 못할 것 같으니, 모두가 돌아가며 앉을 수 있는 가장 좋은 알고리즘을 제안하고 투표하자 개굴!"
라이캣은 눈을 반짝였습니다. 함께 협력해 뜻을 이룰 동료를 찾은 것 같았거든요. 아무도 의견을 내지 않자, 라이캣이 개리를 바라보며 손을 들었습니다.
"주목해주냥! 내게 좋은 아이디어가 있다냥!"
- 다리가 아픈 순서대로 의자에 앉는다.
- 동물의 종류는 다음과 같다. 무척추동물, 척추동물, 어류, 양서류, 파충류, 조류, 포유류이다.
- 같은 '종'일 경우 무릎에 앉을 수 있다. 이때는 1초로 계산한다.(hit)
- 자리가 꽉 찼을 때는 가장 오래 앉아있던 '종'이 아니라, 최근에 함께 앉은 적이 없던 '종'이 자리를 양보한다. 이때 자리를 정리하느라 1분이 걸린다.(miss)
- 처음 자리에 앉을 때도 정리 시간이 필요해서 1분이 걸린다.(miss)
- '종(페이지)'이 리스트의 순서대로 들어왔을 때, 모두 한 번씩 앉는 데 걸리는 시간을 모두 더해 구하라.
"LRU(Least Recently Used) 페이지 교체 알고리즘을 사용하겠다냥! 이 방법은 자리가 부족할 때 가장 오랫동안 함께 앉지 않은 종이 자리를 양보한다냥! 한마디로, 함께 앉을 수 있는 동물의 자리를 최대한 유지해주는 방법이다냥!"
제한 사항
- 입력으로 주어지는 리스트의 길이는 1 이상 1,000 이하입니다.
- 리스트의 각 요소는 '무척추동물', '척추동물', '어류', '양서류', '파충류', '조류', '포유류' 중 하나입니다.
- 의자의 수는 3개로 고정되어 있습니다.
- 걸린 시간을 모두 더한 뒤 'X분 Y초' 형식의 문자열로 반환해야 합니다. 초가 60초 이상이면 60초를 1분으로 올려, Y가 0 이상 59 이하가 되게 합니다(예: 1분이 2번, 1초가 61번이면 '3분 1초'). 초가 0이어도 '7분 0초'처럼 '0초'를 붙입니다.
입출력 예
| 입력 | 출력 |
|---|---|
| ['척추동물', '어류', '척추동물', '무척추동물', '파충류', '척추동물', '어류', '파충류'] | '5분 3초' |
| ['척추동물', '어류', '무척추동물', '척추동물', '어류', '무척추동물'] | '3분 3초' |
입출력 설명
첫 번째 예시

입력값: ['척추동물', '어류', '척추동물', '무척추동물', '파충류', '척추동물', '어류', '파충류']
- '척추동물' 입장: 빈 의자에 앉음 (miss, 1분)
- '어류' 입장: 빈 의자에 앉음 (miss, 2분)
- '척추동물' 입장: 이미 있는 척추동물과 겹쳐 앉음 (hit, 2분 1초)
- '무척추동물' 입장: 빈 의자에 앉음 (miss, 3분 1초)
- '파충류' 입장: 가장 오랫동안 참조가 안된 '어류'가 나가고 입장 (miss, 4분 1초)
- '척추동물' 입장: 이미 있는 척추동물과 겹쳐 앉음 (hit, 4분 2초)
- '어류' 입장: 가장 오랫동안 참조가 안된 '무척추동물'이 나가고 입장 (miss, 5분 2초)
- '파충류' 입장: 이미 있는 파충류와 겹쳐 앉음 (hit, 5분 3초)
따라서 총 소요 시간은 5분 3초입니다.
두 번째 예시
입력값: ['척추동물', '어류', '무척추동물', '척추동물', '어류', '무척추동물']
- '척추동물' 입장: 빈 의자에 앉음 (miss, 1분)
- '어류' 입장: 빈 의자에 앉음 (miss, 2분)
- '무척추동물' 입장: 빈 의자에 앉음 (miss, 3분)
- '척추동물' 입장: 이미 있는 척추동물과 겹쳐 앉음 (hit, 3분 1초)
- '어류' 입장: 이미 있는 어류와 겹쳐 앉음 (hit, 3분 2초)
- '무척추동물' 입장: 이미 있는 무척추동물과 겹쳐 앉음 (hit, 3분 3초)
따라서 총 소요 시간은 3분 3초입니다.
예시 테스트
| # | 입력 | 기대값 |
|---|---|---|
| 1 | ["척추동물", "어류", "척추동물", "무척추동물", "파충류", "척추동물", "어류", "파충류"] | "5분 3초" |
| 2 | ["척추동물", "어류", "무척추동물", "척추동물", "어류", "무척추동물"] | "3분 3초" |
| 3 | ["무척추동물", "척추동물", "어류", "양서류", "파충류", "조류", "포유류"] | "7분 0초" |
입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 8개도 함께 채점해요.