(JAVA) 백준 17612번 : 쇼핑몰 -- [우선순위 큐]

https://www.acmicpc.net/problem/17612

17612번: 쇼핑몰

 

안녕하세요.

 

이 문제는 로직이 바로 생각났지만, 예외 처리 하나가 걸려서 애먹었습니다.

 

 

 

바로 여기인데요.

같은 시간에 끝나는 계산대가 여러 개 있다면, 가장 번호가 작은 계산대부터 손님을 안내해야했습니다.

 

이를 고려하지 않았었기 때문에

같은 시간에 끝나는 계산대가 여러개였지만, 높은 번호의 계산대를 우선순위 큐에서 먼저 poll하기 때문에, 거기에 다음 고객을 넣고.. 그렇게 되다보니 결과 값 순서가 달라지게 되었습니다.

 

 

제가 별도로 문제풀이 방법을 메모장에 기록하면서 해결하는데, 모르고 메모장에 다른 내용을 붙여넣기하고 저장해버려서..

 

다행히 소스코드 내부에 주석으로 간단하게 설명을 적어놓았으니까, 이해가 잘 안되시는 분들은 소스코드 및 주석을 참고하셔서 해결하셨으면 좋겠습니다.

 

 

알고리즘

---

우선, 이 문제를 해결하기위해 저는 2개의 우선순위큐와 1개의 큐, 1개의 ArrayList를 사용했습니다.

 

 

  -  우선순위 큐 1: 현재 카운터상태 우선순위큐 (계산중인 고객의 정보 담음)

  -  우선순위 큐 2: 현재 비어있는 카운터 인덱스 값 큐 (즉, 비어있는 계산대 번호가 담겨있음)

  -  큐 1: 현재 대기중인 고객의 큐 (대기중인 고객의 정보 담음. 줄서있으니까 FIFO인 큐 사용)

  -  ArrayList: 계산하고 빠져나온 순서대로 담은 고객 id 리스트

 

 

다음,

계산하는 시간 및 끝나는 시간을 파악하기 위해 별도 전역변수로 개장 후 지난 시간(time)을 선언하고, 계산대에서 계산을 마친 고객이 걸리는 시간과 Math.max() 비교를 통해 값을 갱신했습니다.

 

왜 이렇게 하냐면, 다음 고객이 계산대에서 계산한 시간을 파악하기 위해서인데요. 

 

저는 공식을 개장 후 지난 시간(time) * W(계산하는시간) 인 값을 담아서 우선순위 큐1에 넣습니다.

만약, W만 넣는다면 이전에 넣었던 고객보다 지금 들어간 고객이 먼저 나올 수 있기 때문입니다.

 

ex) 1번고객 50분 걸림. 2번고객 30분 뒤 계산대 진입 / 30분 걸림

-> 1번 고객 먼저 나오고, 2번 고객이 나와야하지만 W(계산하는시간) 으로만 파악하면 2번이 먼저 나오는 일이 발생하기 때문.

 

 

이를 활용해서

 

  1) 큐 1에 고객 정보 순차저장

  2) 처음에, 앞에서 K만큼 (회원번호, 걸리는시간 = (개점 후 지난 시간 + 계산시간(w))) 계산대 큐(우선순위 큐) 삽입

  3-1) 비어있는 계산대 우선순위 큐를 만들어서 계산대 큐에서 꺼내는 순간 계산대 번호 넣기 
  4) 계산대 큐에서 가장 걸리는시간이 짧은거 꺼내기

  5) 시간 지났으니까 개장 후 시간 갱신

  6) 새로운 고객 시간 계산해서 계산대에 넣기

 

의 순서대로 얼추 로직짜서 구현했습니다.

 

 

좀 더 이해가 필요하다면, 하단 소스코드를 참고해주시길 바랍니다.

 

감사합니다.

 

 

소스코드

---