도키도키 간식드리미

문제

언어

  • JavaScript

순서도

  1. 간단한 스택 구현 또는 배열 사용
  2. 대기열에서 모든 학생이 빠질 때까지 반복
    • 우선, 가운데 1 열(스택) 모두 비우기
    • 대기열에서 순서에 맞는 학생이 있다면 간식 주고,
    • 반대로 순서에 맞지 않는 학생이 있다면 가운데 1 열(스택)에 넣기
  3. 가운데 1 열(스택)에서 모든 학생이 빠질 때까지 반복
    • 가장 최근에 들어간 학생부터 순서에 맞다면 간식 주고 가운데 1 열(스택)에서 빼고,
    • 반대로 순서에 맞지 않는 학생이 있다면 반복 종료
  4. 최종적으로 가운데 1열(스택)이 비어있다면 “Nice”, 그게 아니라면 “Sad”

문제 풀이 step 1

  • 인하대학교 학생회에서는 간식 드리미 행사를 실시합니다.
  • 승환이도 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했습니다.
  • 그런데 그 곳에는 이미 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었습니다.
  • 설상가상으로 몇몇 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되었습니다.
  • 이로 인해, 학우들의 불만이 터져나오자 학생회에서는 번호표 순서로만 간식을 줄 수 있다고 말했습니다.
  • 그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 협소해 마음대로 이동할 수 없었습니다.
  • 다행히도 대기열의 왼쪽에는 1 열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모르겠습니다.
  • 이 상황에서 승환이를 도와 모든 사람들이 순서대로 간식을 받을 수 있는 알고리즘을 작성하는 문제입니다.
    • 사람들은 현재 1 열로 줄을 서 있고, 맨 앞의 사람만 이동이 가능합니다.
    • 학생회는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었습니다.
    • 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1 열이 들어갈 수 있는 공간이 있습니다.
    • 현재 대기열의 사람들은 이 공간으로 올 수 있지만, 반대는 불가능합니다.
  • 문제 관련 사진은 다음과 같습니다. 백준 12789번 도키도키 간식드리미 문제 사진 1 백준 12789번 도키도키 간식드리미 문제 사진 2

문제 풀이 step 2

  • 문제에는 총 3 개의 공간이 있습니다.
    • 순서대로 들어갈 수 있는 라인 (라인)
    • 현재 줄 서 있는 곳 (대기열)
    • 한 명씩만 설 수 있는 공간 (가운데 1 열)
  • 대기열에서 모든 학생이 빌 때까지 아래의 과정을 반복합니다.
    • 우선, 가운데 1 열에서 순서대로 학생들을 라인으로 보낼 수 있는 지 검사합니다.
      • 검사해서 순서가 맞는 학생들은 모두 라인으로 보냅니다.
    • 그리고 대기열에서 가장 앞에 있는 학생이 현재 순서와 맞는지 검사합니다.
      • 순서와 맞다면 라인으로 보냅니다.
      • 순서가 맞지 않다면, 가운데 1 열로 보냅니다.
  • 위의 반복이 끝났으면, 가운데 1 열에서 학생들이 남아있다면, 가운데 1 열에서 순서대로 학생들을 라인으로 보낼 수 있는 지 검사합니다.
    • 검사해서 순서가 맞는 학생들은 모두 라인으로 보냅니다.
  • 위의 과정이 모두 끝난 후에 가운데 1 열이 비어있다면 “Nice” 를 출력하고, 비어있지 않다면 “Sad” 를 출력합니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 꼭 다시 풀어볼 문제입니다.
  • 오히려 이런 유형의 문제가 조건 분기를 명쾌하게 하지 않으면, 이상하게 꼬이고 말리게 되는 문제인 것 같습니다.
  • 오히려 조금이라도 더 빠른 로직을 작성하기 보다는 정직한 로직을 작성하는 것이 잘 풀리는 경우가 많았던 것 같습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

class Stack {
	constructor() {
		this.bucket = [];
		this.top = -1;
	}

	push(item) {
		this.bucket[++this.top] = item;
	}

	pop() {
		return this.bucket[this.top--];
	}

	peek() {
		return this.bucket[this.top];
	}

	isEmpty() {
		return this.top === -1;
	}
}

const solution = (input) => {
	const n = Number(input[0]);
	const arr = input[1].split(" ").map(Number);

	const stack = new Stack();

	let order = 1;

	// 대기열에서 한 사람씩 검사
	for (let i = 0; i < n; i++) {
		// 가운데 1 열에서 순서가 맞는 학생들 모두 라인으로 보내기
		while (!stack.isEmpty()) {
			if (stack.peek() !== order) break;

			stack.pop();
			order += 1;
		}

		// 대기열에서 가장 앞에 있는 학생의 순서를 검사
		if (arr[i] === order) {
			order += 1;
		} else {
			stack.push(arr[i]);
		}
	}

	// 가운데 1 열에서 학생들이 남아있다면, 순서가 맞는 학생들 모두 라인으로 보내기
	while (!stack.isEmpty()) {
		if (stack.peek() !== order) break;

		stack.pop();
		order += 1;
	}

	// 가운데 1 열이 비어있는지, 비어있지 않은지
	if (stack.isEmpty()) return "Nice";
	return "Sad";
};

console.log(solution(input));