📌 스택(Stack)이란?
컴퓨터 공학에서 가장 기본이 되는 자료구조 2가지를 뽑으라고 한다면,
스택(Stack)과 큐(Queue) 라고 말할 수 있습니다.
이는 말 그대로 자료를 표현하고 처리하는 방법에 관한 것입니다.
스택은 쉽게 설명해서 비어있는 유리병과 같다고 표현할 수 있습니다.
입구와 출구가 하나밖에 없는 상태로 표현할 수 있기 때문에,
맨 처음에 스택이 비어있는 상태에서 A, B, C가 순서대로 들어가게 되면 가장 먼저 나오는 것은 C가 됩니다.
이렇듯, 스택은 LIFO(last in first out) 후입선출의 특징을 보이고 있습니다.
다시말해, 가장 최근에 들어온 데이터가 가장 먼저 나간다는 의미입니다.
이는 선입선출의 특징을 가지고 있는 큐와 가장 큰 차이점이라고 볼 수 있습니다.
자료구조에서 가장 많이 쓰이는 스택, 큐, 리스트의 간단한 차이점에 대해 살펴보자면 아래의 표와 같이 정리할 수 있습니다.
| 자료구조 | 공통점 | 차이점 |
|---|---|---|
| 리스트(List) | 선형 자료구조이며, 순서가 있다. | 읽기, 삽입(insert)과 삭제(delete)를 리스트의 어느 곳에서나 행함 |
| 스택(Stack) | - | 삽입과 삭제를 리스트의 한쪽(top)에서 행함 |
| 큐(Queue) | - | 삽입은 리스트의 한쪽(rear)에서 하고, 삭제는 삽입의 반대쪽(front)에서 행함 |
📌 스택 예제 문제풀이
스택 자체에 대해 깊게 구현해보진 않더라도, 스택이 가진 이러한 원리 자체를 파악하여 다양한 문제를 해결할 수 있습니다.
스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어질 때, 아주 유용하게 사용되는 자료구조입니다.
- 스택에 쌓여 있는 숫자와 쌓아서 제일 위에 있는 숫자를 고려해야 한다.
- 쌓을 때, 항상 최댓값을 갱신시켜줘서 갱신된 숫자 위로만 쌓는 것이 중요하다.
위 문제를 풀이해보면, 첫번 째 줄에 스택에 들어올 숫자의 개수가 주어지고 2번째 줄부턴 1부터 해당 줄의 숫자가 될 때까지 스택에 수를 쌓는 식입니다.
만약 스택에 들어올 수의 입력값이 4, 3, 6, 8, 7, 5, 2, 1 순으로 주어진다면
먼저 스택에 들어오는 숫자는 +로 해서 총 4개의 +가 먼저 쌓이게됩니다.
그리고 마지막에 4가 되었기 때문에 -를 추가해줍니다.
여기까지가 처음 입력되는 4에 대한 처리가 끝난 것이죠.
그 다음 입력값 3이 들어왔다면, 현재 스택에는 3이 있기 때문에 바로 -를 해줍니다.
현재 스택에는 1,2 까지 밖에 없는 상태에서 다음 입력값인 6을 처리해줘야 하는데, 예제 출력을 확인해보면 +가 4번이 추가된 것이 아니라 +, +, -가 쌓인 것을 볼 수 있습니다.
이 문제는 스택에 있는 숫자 뿐만 아니라 스택에 넣었던 최대 숫자도 코드에서 관리를 해주어야 한다는 것을 확인할 수 있습니다.
즉, 6이 들어오는 시점의 최대 숫자는 4가 됩니다.
따라서 스택에 넣는 수는 4 이후의 값인 5와 6을 넣어 + 두 번이 쌓이게 되고, 6을 만났기 때문에 -를 추가하게 되는 구조입니다.
정리해보자면, 맨 처음 4가 들어왔을땐 스택 최댓값이 4로 유지가 됩니다.
3이 들어왔을때, 3은 기존 스택 최댓값 보다 작기 때문에 갱신이 이루어지지 않습니다.
반대로 6이 들어왔을땐, 6은 기존 스택 최댓값은 4보다 크기 때문에 최댓값이 6으로 바뀌게 됩니다.
const input = require("fs")
.readFileSync("/dev/stdin")
.toString()
.split("\n")
.map(Number);
const [num, ...numbers] = input; // num은 수의 개수, numbers는 스택에 들어갈 숫자들
function getResult() {
const stack = [];
let answer = "";
let count = 1; // 1부터 시작
for (let i = 0; i < num; i++) {
const currNum = numbers.shift(); // 입력받은 숫자를 for문으로 하나씩 꺼낸다.
while (count <= currNum) {
stack.push(count++); // 입력된 수와 같아질 때까지 수를 채워준다.
answer += "+";
}
const maxNum = stack.pop(); // 같아졌으므로 배열에서 빼주고 빼준 수를 maxNum으로 잡는다.
if (maxNum !== currNum) {
// 만약 pop한 숫자와 입력된 숫자가 다르다면 수열을 만들 수 없으므로 NO를 리턴한다.
return "NO";
}
answer += "-"; // 위의 경우가 아니라면 정상적으로 표시를 추가해준다.
}
return answer.split("").join("\n"); // 반복을 돌며 완성된 문자를 쪼갠뒤, 줄바꿈을 추가해서 다시 합쳐준다.
}
console.log(getResult());참고 자료
