[ SWEA 8189 ] 우편함 (C++)

SWExpertAcademy의 우편함(8189 / D4) 문제이다.

[ 문제풀이 ]

편지가 오는 시간을 통해서, 선표가 편지를 확인하는 시간을 구해야 하는 문제이다.

우편함을 비우는 것에 대해서는 3가지 조건이 존재한다.
1. 우편함에 쌓인 편지의 갯수가 A개 이상일 때, 우편함을 비운다.

2. 가장 오래 기다린 편지가 정확히 B시간 전에 온 편지일 때, 우편함을 비운다.

3. 우편함을 비울 때는, 우편함에 들어있는 편지의 갯수의 절반만 비운다.

위와 같은 3가지 조건이 있다.

본인은 이 문제를 해결하기 위해서 자료구조 큐(Queue)를 이용해서 접근하였다.

왜냐하면 위의 조건들을 큐를 이용해서 표현한다면 아래와 같이 쉽게 계산할 수 있을 거라 생각했기 때문이다.

( Queue에는 각 편지가 도착한 시간을 저장해 주었다. )

1. 우편함에 쌓인 편지의 갯수가 A개 이상일 때 = "Queue의 Size가 A이상이다." 로 접근 가능.

2. 가장 오래 기다린 편지가 정확히 B시간 전에 온 편지이다. = "Queue의 Front값 + B = 현재시간" 으로 접근가능.

- 예를 들어서 가장 처음에 온 편지가 1시간에 왔고, B = 5 라면, 가장 처음에 온 편지는 6시간 째에 확인하게 된다.

   즉, Queue의 Front 값 + B  = 현재시간 이면 우편함을 비운다.

3. 우편함을 비울 때는, 우편함에 들어있는 편지의 갯수의 절반만 비운다. = "Queue의 Size / 2 한 값 만큼 pop() 연산" 으로 접근

    가능.

위의 부분들을 코드로 알아보자. 가장 먼저, Queue에 값을 삽입하는 과정을 보자.

Queue에는 "현재 시간에 편지가 들어온다면, 해당 편지가 들어온 현재 시간을 Queue에 저장" 해주었다.

if (Time < MAX && Mail[Time] == true) Q.push(Time);

Mail[a]  =  true 의 의미는 "a시간은 편지가 들어오는 시간입니다" 를 의미한다.

Time 은 현재 시간을 나타내는 본인이 선언한 변수이고, MAX = 1010 의 값을 의미한다.

MAX의 값은 "편지가 들어올 수 있는 최대 시간"을 의미하며, 문제에 나와있는 tx의 값의 최대값을 의미한다.

즉, Mail[x] = true 에서 x에 올 수 있는 최댓값은 1000이고, 그 이상이 된다면 올바른 Index에 대한 접근이 아닐 수 있기 때문에

위와 같은 조건을 걸어주었다.

중요한건, "Queue에는 편지가 들어온 시간을 저장" 한다는 것이다.

두 번째로는, "우편함에 들어있는 편지의 갯수를 확인하고, 우편함을 비워야 할 타이밍인지 판단하는 부분"을 보자.

int Mail_Cnt = Q.size();
if (Mail_Cnt == 0)
{
        Time++;
        continue;
}
if (Mail_Cnt == A || Q.front() + B == Time)
{
    int Read_Cnt = (Q.size() / 2) + (Q.size() % 2);
    for (int i = 0; i < Read_Cnt; i++)
    {
        Q.pop();
        Answer[Idx++] = Time;
        Finish++;
    }
}

"우편함에 들어있는 편지의 갯수" = Queue의 Size를 통해서 알아낼 수 있다.

line7) 에서 보면 위에서 말한 2가지 조건에 부합하는지 확인하는 부분이다.

"현재 우편함에 들어있는 편지의 갯수가 A개 이거나, 가장 오래 기다린 편지가 B시간 전에 도착한 편지이거나" !

그런데 이 부분을 위해서 line2)에 있는 조건문이 필요하다. 왜냐하면 line2 ~ 6)에 대한 조건이 없다면, line7)에서 호출되는

'Q.front()' 부분에서 Error가 발생할 수 있기 때문이다. 그래서 line2~6)과 같이, "아직 우편함에 편지가 하나도 없다면 ~" 이라는

조건문을 걸어주었다.

line9) 는 읽어야 할 편지의 갯수를 구하는 부분이다. 절반에서 반올림한 값만큼을 읽기 때문에, 위와 같은 식으로 해결할 수 있다.

line10 ~ 15)는 "우편함에서 편지를 구한 갯수만큼 비워내는 과정" 이다. Queue의 pop() 연산을 통해서 쉽게 구할 수 있으며,

동시에 처리되는 편지는 Answer[]이라는 배열에 저장해주는 과정이다.

이 부분에 대한 전체 소스코드는 다음과 같다.

void Solution()
{
    queue<int> Q;
    int Finish = 0;
    int Time = 0;
    int Idx = 0;
    while (1)
    {
        if (Finish == N) break;
        if (Time < MAX && Mail[Time] == true) Q.push(Time);
        
        int Mail_Cnt = Q.size();
        if (Mail_Cnt == 0)
        {
            Time++;
            continue;
        }
        if (Mail_Cnt == A || Q.front() + B == Time)
        {
            int Read_Cnt = (Q.size() / 2) + (Q.size() % 2);
            for (int i = 0; i < Read_Cnt; i++)
            {
                Q.pop();
                Answer[Idx++] = Time;
                Finish++;
            }
        }
        Time++;
    }
}

위와 같이 제출을 하면 되지만 ! 무슨 문제인지는 모르겠지만, 이 문제를 위의 코드처럼 구현해서 제출을 해보면 "허용되지 않는 라이브러리가 사용되었다" 라는 문구와 함께 채점이 되질 않는다.

입출력을 담당하는 라이브러리인 #include<iostream> 이외에 다른 라이브러리를 추가하면 위와 같은 문구가 뜨는 것 같았다.

그래서 그냥 Queue에 대한 부분을 직접 구현하였다.

위에서 설명한 코드는 쉽게 설명하기 위해서 라이브러리 Queue를 사용한 코드를 가져왔지만, 실제 구현할 때는 라이브러리 Queue를 사용하지 않고 직접 구현해서 제출하였다.

라이브러리가 익숙한 사람들을 위해서 라이브러리 Queue를 사용한 코드까지 해서 총 2개를 첨부해 놓겠습니다.

[ 라이브러리 사용하지 않은 직접 구현한 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 1010
#define MAIL_MAX 105
using namespace std;
 
int N, A, B;
int Answer[MAIL_MAX];
int Queue[MAIL_MAX];
bool Mail[MAX];
 
void Initialize()
{
    for (int i = 0; i < MAX; i++) Mail[i] = false;
}
 
void Input()
{
    cin >> N >> A >> B;
    for (int i = 0; i < N; i++)
    {
        int a; cin >> a;
        Mail[a] = true;
    }
}
 
void Solution()
{
    int Front, Rear, Finish, Time, Idx;
    Front = Rear = Finish = Time = Idx = 0;
 
    while (1)
    {
        if (Finish == N) break;
        if (Time < MAX && Mail[Time] == true) Queue[Rear++] = Time;
 
        int Mail_Cnt = Rear - Front;
        if (Mail_Cnt == 0)
        {
            Time++;
            continue;
        }
 
        if (Mail_Cnt == A || Queue[Front] + B == Time)
        {
            int Read_Cnt = (Mail_Cnt / 2) + (Mail_Cnt % 2);
            for (int i = 0; i < Read_Cnt; i++)
            {
                Answer[Idx++] = Time;
                Finish++;
                Front++;
            }
        }
        Time++;
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " ";
        for (int i = 0; i < N; i++) cout << Answer[i] << " ";
        cout << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

[ 라이브러리를 사용한 소스코드 ]

#include<iostream>
#include<queue>
#include<cstring>
 
#define endl "\n"
#define MAX 1010
#define MAIL_MAX 105
using namespace std;
 
int N, A, B;
int Answer[MAIL_MAX];
int Queue[MAIL_MAX];
bool Mail[MAX];
 
void Initialize()
{
    memset(Mail, false, sizeof(Mail));
}
 
void Input()
{
    cin >> N >> A >> B;
    for (int i = 0; i < N; i++)
    {
        int a; cin >> a;
        Mail[a] = true;
    }
}
 
void Solution()
{
    queue<int> Q;
    int Finish = 0;
    int Time = 0;
    int Idx = 0;
    while (1)
    {
        if (Finish == N) break;
        if (Time < MAX && Mail[Time] == true) Q.push(Time);
        
        int Mail_Cnt = Q.size();
        if (Mail_Cnt == 0)
        {
            Time++;
            continue;
        }
        if (Mail_Cnt == A || Q.front() + B == Time)
        {
            int Read_Cnt = (Q.size() / 2) + (Q.size() % 2);
            for (int i = 0; i < Read_Cnt; i++)
            {
                Q.pop();
                Answer[Idx++] = Time;
                Finish++;
            }
        }
        Time++;
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " ";
        for (int i = 0; i < N; i++) cout << Answer[i] << " ";
        cout << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}