백준알고리즘 12789번 도키도키 간식드리미 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 12789
• 문제명: 도키도키 간식드리미
• 언어: C#
• 분류: 자료 구조, 스택
• 비고: 

 

문제

인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다. 

그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.

사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.

 

입력

입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.

다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.

 

출력

승환이가 무사히 간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다.

 

풀이

대기열은 큐로, 임시 공간은 스택으로 구현하면 된다.

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
// 현재 대기열
Queue<int> queue = new Queue<int>();
// 한 명씩 설 수 있는 임시 공간
Stack<int> stack = new Stack<int>();

// 대기자 수
int n = Convert.ToInt32(sr.ReadLine());
// 대기자의 번호
int[] line = sr.ReadLine().Split().Select(int.Parse).ToArray();
// 1번부터 시작
int i = 1;
// 간식을 받을 수 있는 지의 여부
bool niceOrSad = true;

// 입력한 대기자의 번호에 따라 줄을 선다.
foreach(int j in line)
    queue.Enqueue(j);

while (true)
{
    // 모두가 간식을 받아 대기열에 아무도 없으면 종료
    if(queue.Count == 0) break;
    // 간식을 받은 경우
    else if(queue.Peek() == i)
    {
        // 대기열에서 나간다.
        queue.Dequeue();
        // 번호가 상승한다.
        i++;
    }
    // 임시 공간에 사람이 있고 현재 번호와 일치할 때
    else if(stack.Count > 0 && stack.Peek() == i)
    {
        // 임시 공간에서 나온다.
        stack.Pop();
        // 번호가 상승한다.
        i++;
    }
    // 대기열 맨 앞의 번호가 현재 번호보다 큰 경우
    else if(queue.Peek() > i)
    {
        // 임시 공간에 아무도 없다면 대기열에서 나와 임시 공간으로 들어간다 
        if(stack.Count == 0) stack.Push(queue.Dequeue());
        // 임시 공간에 1명 이상 있고 대기열 맨 앞 번호보다 임시 공간 맨 뒤 번호가 더 클 때
        else if(stack.Count > 0 && queue.Peek() < stack.Peek()) stack.Push(queue.Dequeue());
        // 임시 공간에 1명 이상 있고 대기열 맨 앞 번호가 임시 공간 맨 뒤 번호보다 더 클 때
        else if(stack.Count > 0 && queue.Peek() > stack.Peek())
        {
            niceOrSad = false;
            break;
        }
    }
    
}
// 최종 결과 출력
sw.WriteLine(niceOrSad ? "Nice" : "Sad");

sr.Close();
sw.Close();

 

후기

이 문제를 풀 때 큐를 사용한 정답이 있으리라고는 생각도 못 했다. 사실 자력으로 풀어낸 소스코드가 있어서 그것을 첨부하겠다.

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

Stack<int> stackLineA = new Stack<int>();
Stack<int> stackLineB = new Stack<int>();
Stack<int> stackLineC = new Stack<int>();

int n = Convert.ToInt32(sr.ReadLine());

int[] student = new int[n];

int temp;

student = sr.ReadLine().Split().Select(int.Parse).ToArray();

for (int i = student.Length - 1; i >= 0; i--)
    stackLineA.Push(student[i]);

while (stackLineA.Count > 0)
{
    int i = 0;

    if (i + 1== stackLineA.Peek())
    {
        temp = stackLineA.Pop();
        stackLineC.Push(temp);
        i++;
    }
    else if (i + 1 != stackLineA.Peek())
    {
        temp = stackLineA.Pop();
        stackLineB.Push(temp);
    }
        

    else if (i + 1 == stackLineB.Peek())
    { 
        temp = stackLineB.Pop();
        stackLineC.Push(temp);
        i++;
    }
}

while(stackLineB.Count > 0)
{
    temp = stackLineB.Pop();
    stackLineC.Push(temp);
}

while(stackLineC.Count > 0)
{
    int i = stackLineC.Count;

    if (i == stackLineC.Peek())
    {
        stackLineC.Pop();
        continue;
    }

    if (i != stackLineC.Peek())
    {
        sw.WriteLine("Sad");
        break;
    }
}

if(stackLineC.Count == 0)
    sw.WriteLine("Nice");

sr.Close();
sw.Close();

 

보다시피 스택을 3개 사용해서 풀었으며, stackLineC가 최종적으로 정리된 줄이다. 다만 스택이 LIFO 방식이기 때문에 int i의 변수값을 stackLineC.Count의 값을 대입해서 풀도록 설계했다. 이렇게 되면 스택 내용물이 하나 줄어든 후 줄어든 값으로 다시 초기화된다. 이런 점을 이용해서 Nice와 Sad 중 하나가 나오도록 설계했는데 채점 결과는 틀린 것으로 나왔다. 분류에서 큐를 사용한다는 언급이 없어서 Stack으로만 풀었는데 어쩌면 분류는 대강 써놓은 것이 아닐까 싶다.