읽기 전에 알아두면 좋아요
아래 개념이 익숙하면 본문을 바로 읽으세요. 낯선 개념만 링크에서 복습하면 됩니다.
- 단방향 연결 리스트: head·tail 삽입과 삭제연결 리스트는 값이 든 노드가 다음 노드를 가리킵니다. 연결을 바꾸는 순서를 확인합니다. head·tail과 마지막 노드 제거 시 불변식을 재생 대기 목록에 적용합니다.
- 큐와 FIFO: head 인덱스로 JavaScript 대기열 만들기큐는 먼저 넣은 값을 먼저 꺼냅니다. 대기열에 넣고 꺼낼 때의 순서를 확인합니다. 먼저 들어온 값을 먼저 꺼내는 큐의 동작을 확인합니다.
개념과 예제는 실행하지 않아도 읽을 수 있습니다. 내 컴퓨터·터미널에서 직접 실행하는 과정은 선택 실습입니다.
과정 위치와 선택 복습 안내
과정 위치: 자료구조 개념과 문제 · 문제
과정 위치는 이 글이 속한 묶음입니다. 이 단계의 모든 개념을 먼저 읽을 필요는 없습니다. 위에 연결한 개념 중 낯선 내용만 복습하세요. 문제의 조건·상태·갱신 순서는 익숙한 언어로 설명하면 됩니다.
JavaScript로 문법·실행 복습하기 (선택)
개념 글의 코드는 JavaScript 예시입니다. 문제 화면에서는 JavaScript·Python·Java·C++·C# 중 익숙한 언어의 함수를 작성하세요. 본문의 Node.js 입출력 예시는 로컬 실행을 위한 별도 안내입니다.
재생 대기 목록 관리 문제는 목록에 대한 어떤 명령들을 처리하나요?
재생 대기 목록의 추가·제거·조회 명령을 처리하는 문제입니다. 노드·연결 리스트·명령 처리의 기본을 준비하고, 아래 입력·반환 계약을 확인해 직접 풀어보세요.
적용 조건·범위: append와 removeFirst는 노드 연산 기준 최악 O(1)이고 LIST는 현재 K개 노드를 방문한 뒤 제목을 결합합니다. 입력 문자 수 S, 출력 문자 수 R, 명령 수 Q로 쓰면 전체 시간은 O(S+Q+R)입니다. 반복 LIST의 출력 때문에 R이 Q에 비해 크게 늘 수 있어 단순 O(Q)라고 할 수 없습니다. 구조만 보면 O(K) 노드지만 입력 문자열·줄 배열·출력 누적과 반환 문자열을 포함한 전체 공간은 O(S+Q+R+K), K≤Q이므로 O(S+Q+R)입니다. 제목 복사·연결 비용도 문자 수에 포함했습니다.
공식 문서 참고: 관련 개념: 버지니아공대 OpenDSA의 단방향 연결 리스트
독립 창작 문제: 재생 대기 목록
곡을 뒤에 추가하고 앞에서 재생하며 현재 목록을 출력합니다. 비었다가 다시 추가하는 상황에서도 head와 tail을 일관되게 관리해야 합니다.
이 문제는 BlogFlow 학습용으로 독립 창작했습니다. 외부 문제의 지문·예시·테스트를 복제하지 않았습니다.
개념 연결: 단방향 연결 리스트 가이드
문제
ADD 제목은 재생 목록 끝에 곡을 추가합니다. PLAY는 첫 곡 제목을 출력한 뒤 제거하고, 목록이 비어 있으면 EMPTY를 출력합니다. LIST는 현재 곡 제목을 앞에서부터 쉼표로 이어 출력하고 비어 있으면 EMPTY를 출력합니다. 같은 제목의 곡은 별도 노드로 저장합니다.
입력·출력·제약
첫 줄은 정수 Q(0~50,000), 이후 Q줄은 정의된 명령입니다. 제목은 공백·쉼표 없는 1~40 코드포인트 문자열입니다. 명령과 제목 사이에는 공백 하나를 사용합니다. PLAY와 LIST 결과를 한 줄씩 출력하고 결과가 없으면 아무것도 출력하지 않습니다. 출력이 지나치게 커지지 않도록 전체 출력 길이는 줄바꿈 포함 1,000,000 UTF-16 코드 유닛 이하로 주어집니다.
예시 1
입력:
8
ADD 봄
ADD 여름
LIST
PLAY
ADD 여름
PLAY
PLAY
PLAY출력:
봄,여름
봄
여름
여름
EMPTY예시 2: 빈 상태
입력:
1
PLAY출력:
EMPTY힌트
처음 곡을 추가하면 head와 tail은 같은 노드입니다. 마지막 곡을 재생한 뒤에는 둘 다 null이어야 다음 추가가 정상적으로 연결됩니다.
직접 풀어보기
먼저 선택한 언어의 입력·반환 계약에 맞춰 작성해 보세요. 힌트 받기와 정답과 비교하기는 코드를 실행하지 않는 AI 분석입니다. 해답·해설은 아래에서 필요할 때 펼칠 수 있습니다.
AI 힌트
코드를 실행한 채점 결과가 아닌 AI의 코드 분석입니다.
해답·해설 보기
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
append(value) {
const node = {
value, next : null
};
if (this.tail) {
this.tail.next = node;
} else {
this.head = node;
}
this.tail = node;
this.length += 1;
}
removeFirst() {
if (! this.head) {
return {
done : true
};
}
const node = this.head;
this.head = node.next;
node.next = null;
this.length -= 1;
if (this.length === 0) {
this.tail = null;
}
return {
done : false, value : node.value
};
}
find(value) {
for (let node = this.head; node; node = node.next) {
if (node.value === value) {
return node;
}
}
return null;
}
remove(value) {
let previous = null;
let current = this.head;
while (current && current.value !== value) {
previous = current;
current = current.next;
}
if (! current) {
return false;
}
if (previous) {
previous.next = current.next;
} else {
this.head = current.next;
}
if (current === this.tail) {
this.tail = previous;
}
current.next = null;
this.length -= 1;
return true;
}
toArray() {
const values = [];
for (let node = this.head; node; node = node.next) {
values.push(node.value);
}
return values;
}
}
function solve(input) {
const text = input.trim();
if (! text) {
return '';
}
const lines = text.split(/\r?\n/);
const count = Number(lines[0]);
const list = new SinglyLinkedList();
const output = [];
for (let i = 1; i <= count; i++) {
const[command, title] = lines[i].split(' ');
if (command === 'ADD') {
list.append(title);
} else if (command === 'PLAY') {
const result = list.removeFirst();
output.push(result.done ? 'EMPTY' : result.value);
} else if (command === 'LIST') {
output.push(list.toArray().join(',') || 'EMPTY');
}
}
return output.join('\n');
}
입력 예시 전체를 문자열로 전달하고 출력 문자열을 반환합니다. solve(input)를 호출합니다. 표준 입력·출력 코드는 추가하지 않습니다. 입력 공백과 LF/CRLF 줄바꿈을 처리합니다.
class Node:
def __init__(self,value): self.value,self.next=value,None
def solve(input):
lines=input.splitlines()
head=tail=None
output=[]
for line in lines[1:1+int(lines[0])]:
parts=line.split(' ',1)
command=parts[0]
if command=='ADD':
node=Node(parts[1])
if tail is None: head=node
else: tail.next=node
tail=node
elif command=='PLAY':
output.append('EMPTY' if head is None else head.value)
if head is not None:
head=head.next
if head is None: tail=None
else:
values=[]
node=head
while node is not None:
values.append(node.value)
node=node.next
output.append(','.join(values) if values else 'EMPTY')
return '\n'.join(output)
입력 예시 전체를 문자열로 전달하고 출력 문자열을 반환합니다. solve(input)를 호출합니다. 표준 입력·출력 코드는 추가하지 않습니다. 입력 공백과 LF/CRLF 줄바꿈을 처리합니다.
import java.util.*;
class Solution {
static class Node {
String value;
Node next;
Node(String v) {
value = v;
}
}
public String solve(String input) {
String[] lines = input.split("\r?\n");
int q = Integer.parseInt(lines[0]);
Node head = null, tail = null;
List < String > out = new ArrayList < >();
for (int i = 1; i <= q; i++) {
String[] p = lines[i].split(" ", 2);
if (p[0].equals("ADD")) {
Node n = new Node(p[1]);
if (tail == null) head = n;
else tail.next = n;
tail = n;
} else if (p[0].equals("PLAY")) {
out.add(head == null ? "EMPTY" : head.value);
if (head != null) {
head = head.next;
if (head == null) tail = null;
}
} else {
StringJoiner row = new StringJoiner(",");
for (Node n = head; n != null; n = n.next) row.add(n.value);
out.add(head == null ? "EMPTY" : row.toString());
}
}
return String.join("\n", out);
}
}
입력 예시 전체를 문자열로 전달하고 출력 문자열을 반환합니다. new Solution().solve(input)를 호출합니다. 표준 입력·출력 코드는 추가하지 않습니다. 입력 공백과 LF/CRLF 줄바꿈을 처리합니다.
#include <memory>
#include <sstream>
#include <string>
#include <vector>
struct Node {
std::string value;
Node * next = nullptr;
explicit Node(std::string v) : value(v) {
}
};
std::string solve(const std::string & input) {
std::istringstream in(input);
int q;
in >> q;
std::string command, title, out;
Node * head = nullptr;
Node * tail = nullptr;
std::vector < std::unique_ptr < Node >> owned;
bool first = true;
for (int i = 0; i < q; i++) {
in >> command;
if (command == "ADD") {
in >> title;
owned.emplace_back(new Node(title));
Node * n = owned.back().get();
if (tail) tail->next = n;
else head = n;
tail = n;
} else {
std::string row;
if (command == "PLAY") {
row = head ? head->value : "EMPTY";
if (head) {
head = head->next;
if (! head) tail = nullptr;
}
} else {
for (Node * n = head; n; n = n->next) {
if (n != head) row += ",";
row += n->value;
}
if (! head) row = "EMPTY";
}
if (! first) out += "\n";
first = false;
out += row;
}
}
return out;
}
입력 예시 전체를 문자열로 전달하고 출력 문자열을 반환합니다. solve(input)를 호출합니다. 표준 입력·출력 코드는 추가하지 않습니다. 입력 공백과 LF/CRLF 줄바꿈을 처리합니다.
using System;
using System.Collections.Generic;
public class Solution {
class Node {
public string value;
public Node next;
public Node(string v) {
value = v;
}
}
public string Solve(string input) {
string[] lines = input.Replace("\r\n", "\n").Split('\n');
int q = int.Parse(lines[0]);
Node head = null, tail = null;
var output = new List < string >();
for (int i = 1; i <= q; i++) {
string[] p = lines[i].Split(new char[] {
' '
}, 2);
if (p[0] == "ADD") {
var n = new Node(p[1]);
if (tail == null) head = n;
else tail.next = n;
tail = n;
} else if (p[0] == "PLAY") {
output.Add(head == null ? "EMPTY" : head.value);
if (head != null) {
head = head.next;
if (head == null) tail = null;
}
} else {
var row = new List < string >();
for (Node n = head; n != null; n = n.next) row.Add(n.value);
output.Add(head == null ? "EMPTY" : string.Join(",", row));
}
}
return string.Join("\n", output);
}
}
입력 예시 전체를 문자열로 전달하고 출력 문자열을 반환합니다. new Solution().Solve(input)를 호출합니다. 표준 입력·출력 코드는 추가하지 않습니다. 입력 공백과 LF/CRLF 줄바꿈을 처리합니다.
Node.js 24 CommonJS용 코드입니다. 전체를 linked-list-playlist-problem.cjs로 저장하고 예시 입력을 input.txt에 UTF-8로 저장합니다. 아래 명령은 셸에 맞게 하나를 골라 사용하세요.
PowerShell 7 (UTF-8 파이프):
Get-Content -Raw -Encoding UTF8 .\input.txt | node .\linked-list-playlist-problem.cjsmacOS / Linux Bash:
node linked-list-playlist-problem.cjs < input.txtclass SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
append(value) {
const node = { value, next: null };
if (this.tail) {
this.tail.next = node;
} else {
this.head = node;
}
this.tail = node;
this.length += 1;
}
removeFirst() {
if (!this.head) {
return { done: true };
}
const node = this.head;
this.head = node.next;
node.next = null;
this.length -= 1;
if (this.length === 0) {
this.tail = null;
}
return { done: false, value: node.value };
}
find(value) {
for (let node = this.head; node; node = node.next) {
if (node.value === value) {
return node;
}
}
return null;
}
remove(value) {
let previous = null;
let current = this.head;
while (current && current.value !== value) {
previous = current;
current = current.next;
}
if (!current) {
return false;
}
if (previous) {
previous.next = current.next;
} else {
this.head = current.next;
}
if (current === this.tail) {
this.tail = previous;
}
current.next = null;
this.length -= 1;
return true;
}
toArray() {
const values = [];
for (let node = this.head; node; node = node.next) {
values.push(node.value);
}
return values;
}
}
function solve(input) {
const text = input.trim();
if (!text) {
return '';
}
const lines = text.split(/\r?\n/);
const count = Number(lines[0]);
const list = new SinglyLinkedList();
const output = [];
for (let i = 1; i <= count; i++) {
const [command, title] = lines[i].split(' ');
if (command === 'ADD') {
list.append(title);
} else if (command === 'PLAY') {
const result = list.removeFirst();
output.push(result.done ? 'EMPTY' : result.value);
} else if (command === 'LIST') {
output.push(list.toArray().join(',') || 'EMPTY');
}
}
return output.join('\n');
}
module.exports = { solve };
if (require.main === module) {
const input = require('node:fs').readFileSync(0, 'utf8');
process.stdout.write(solve(input));
}명령과 상태 변화
| 명령 | 처리 뒤 목록 | 출력 |
|---|---|---|
| ADD 봄 | 봄 | 출력 없음 |
| ADD 여름 | 봄 → 여름 | 출력 없음 |
| LIST | 봄 → 여름 유지 | 봄,여름 |
| PLAY | 여름 | 봄 |
| ADD 여름 | 여름 → 여름 | 출력 없음 |
| PLAY 두 번 | 빈 목록 | 여름, 여름 |
| PLAY | 빈 목록 유지 | EMPTY |
왜 이 구현으로 맞는가
전체 정답에 SinglyLinkedList를 포함했습니다. append는 tail을 이미 알고 있어 바로 연결하고, removeFirst는 head를 다음 노드로 옮깁니다. 이 두 연산에 임의 인덱스 조회가 필요하지 않으므로 단방향 연결 리스트로 충분합니다. LIST가 필요할 때만 모든 노드를 순서대로 따라갑니다.
목록이 빈 상태의 불변식은 head===null, tail===null, length===0입니다. 한 노드를 추가하면 head와 tail이 같은 노드를 가리키며 tail.next는 null입니다. removeFirst로 마지막 노드를 없앨 때 tail을 그대로 두면 다음 append가 이미 제거한 노드 뒤에 연결되므로 tail도 초기화해야 합니다.
solve는 ADD에 대해서는 출력하지 않고 PLAY의 결과와 LIST의 스냅샷만 output에 넣습니다. LIST는 관찰일 뿐 목록을 제거하지 않습니다. 따라서 다음 PLAY는 LIST에 표시된 첫 곡을 그대로 반환해야 합니다. 중복 제목도 별개 노드라 하나를 재생해도 다음 같은 제목이 남을 수 있습니다.
가이드와 같은 클래스에는 find와 remove도 들어 있지만 이 문제의 solve는 append, removeFirst, toArray만 사용합니다. 노드 참조와 head·tail이 공개되어 있으므로 외부에서 next를 수정하지 않는 계약을 지킵니다. 노드를 직접 건드리지 않고 메서드로만 목록을 바꾸면 상태 추적이 단순해집니다.
시간·공간과 문자열 비용
append와 removeFirst는 노드 연산 기준 최악 O(1)이고 LIST는 현재 K개 노드를 방문한 뒤 제목을 결합합니다. 입력 문자 수 S, 출력 문자 수 R, 명령 수 Q로 쓰면 전체 시간은 O(S+Q+R)입니다. 반복 LIST의 출력 때문에 R이 Q에 비해 크게 늘 수 있어 단순 O(Q)라고 할 수 없습니다. 구조만 보면 O(K) 노드지만 입력 문자열·줄 배열·출력 누적과 반환 문자열을 포함한 전체 공간은 O(S+Q+R+K), K≤Q이므로 O(S+Q+R)입니다. 제목 복사·연결 비용도 문자 수에 포함했습니다.
표본을 직접 확인하는 코드
다음 코드를 linked-list-playlist-check.cjs로 저장한 뒤 node linked-list-playlist-check.cjs로 실행하세요. assert가 일치하면 출력 없이 종료하고, 결과가 다르면 예외가 발생합니다. 같은 폴더의 정답 파일을 가져오는 이 블록은 풀이 본체가 아니라 표본 확인용입니다.
const assert = require('node:assert/strict');
const { solve } = require('./linked-list-playlist-problem.cjs');
const input = "8\nADD 봄\nADD 여름\nLIST\nPLAY\nADD 여름\nPLAY\nPLAY\nPLAY";
const expected = "봄,여름\n봄\n여름\n여름\nEMPTY";
assert.equal(solve(input), expected);
assert.equal(solve("1\nPLAY"), "EMPTY");
assert.equal(solve('0'), '');연결 학습
단방향 연결 리스트 가이드에서 메서드별 불변식을 확인하세요. 공식 문제 사이트의 백준 1406 에디터는 다른 계약을 가진 추가 연습입니다. 공식 링크 확인일: 2026년 9월 10일.
이 문제를 푼 뒤 확인하기
풀이 직접 실행
본문 풀이에 예제 입력을 넣고, 입력을 바꿔 계산 결과를 비교합니다.
예제 크게 보기 (새 탭)빈 목록의 삽입·삭제와 머리·꼬리 노드가 바뀌는 삭제를 그려 보세요.
본문의 예제와 이 반례를 직접 실행해 예상 출력과 비교하고, 결과가 다르면 입력 조건과 반복 범위를 다시 확인하세요.
이 글이 도움이 되었나요?
이어서 공부하기
체크포인트: 해설을 가리고 다시 풀고, 경계 입력을 하나 바꾸어 예상 결과와 실제 결과를 비교하세요. 삽입·제거 전후의 상태를 그리고, 내장 도구를 쓰는 풀이와 직접 구현의 목적을 구분하세요.
다음 추천 · 자료구조 개념: JavaScript 원형 덱 구현: 양끝 삽입·삭제와 고정 용량 버퍼
권장 순서는 학습 가이드와 같습니다. 다른 순서는 접힌 참고 목록에서 확인할 수 있습니다. 읽음 표시는 숙달이나 채점 결과가 아닙니다.
원래 과정 목록 순서 (선택)
읽음 기록
읽음 — / 전체 58개 · 필수 58개
새 글 받아보기
RSS 리더에서 BlogFlow의 새 글을 확인할 수 있습니다.
