방 예약자 출력하기

문제

어떤 호텔의 방을 예약하려 한다. 최종적으로 방에 예약 된 사람의 번호를 출력하라. 단, 예약을 취소할 경우 대기열에서 제외되고, 취소한 사람이 다시 예약을 하는 경우 대기열의 맨 뒤에 추가된다.

호텔의 방의 개수는 K로 주어지고, 회원에 대한 상태가 입력으로 주어진다.

입력의 형태는 다음과 같다.

• [m, n] 형태의 고객 x 명 ( x는 1~10만 ), 방의 개수 K
• m : 고객 이름(1, 2, ,3, 4, 5, … 자연수)
• n : 0 또는 1 0은 예약 취소, 1은 예약
• K : 1~1000까지 자연수

다음은 테스트 케이스이다.

• 입력: {[1,1], [2,1], [3,1], [2,0], [2,1]}, 2
• 출력: {1, 3}

먼저 방의 개수는 2개이다.

1이라는 사람이 예약을 하였고 다음으로 2와 3이라는 사람이 예약을 하였다. 그리고 2가 예약을 취소하였으므로 방의 우선순위는 3에게 넘어간다. 2가 다시 예약을 하였지만 이미 3이 우선순위를 가지므로 최종적인 상태는 1과 3이 방에 예약된다.

단, 방을 예약한 사람이 다시 방을 예약하는 경우는 주어지지 않으며, 마찬가지로 예약을 취소한 사람이 다시 예약을 취소하는 경우 또한 주어지지 않는다.

풀이

테스트 케이스를 변경해보았다. 31번의 라인처럼 하나만 사용했을 경우 위 코드에서 나온 customer 벡터로는 에러가 발생한다.

따라서 30번 라인을 추가하여 최종적으로 남은 사람 수가 방의 개수보다 적은 경우도 코딩해준다.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> solution(vector<vector<int>> customer, int K)
{
  vector<int> answer;

  int                   i;
  vector<int>           wait;
  vector<int>::iterator it;

  for (i = 0; i < K; i++) wait.push_back(customer[i][0]);

  for (i; i < customer.size(); i++)
  {
    if (customer[i][1] == 0)
    {
      it = find(wait.begin(), wait.end(), customer[i][0]);
      wait.erase(it);
    }
    if (customer[i][1] == 1)
    {
      wait.push_back(customer[i][0]);
    }
  }

  if (wait.size() < K)
    for (int i = 0; i < wait.size(); i++) answer.push_back(wait[i]);
  else
    for (int i = 0; i < K; i++) answer.push_back(wait[i]);

  return answer;
}

int main()
{
  vector<vector<int>> customer{
    { 1, 1 }, { 2, 1 }, { 3, 1 }, { 2, 0 }, { 2, 1 }, { 3, 0 }, { 1, 0 }, { 4, 1 }, { 5, 1 }, { 6, 1 }, { 8, 1 }, { 5, 0 }, { 4, 0 }
  };
  int k = 2;

  vector<int> answer = solution(customer, k);

  for (int i = 0; i < answer.size(); i++)
  {
    cout << answer[i] << " ";
  }
  cout << endl;
}

출처

프로그래머스