[Stack/Queue] 자료구조/알고리즘 구현하기
01_[Stack] 구현
Implementation Stack
Stack 구현을 위한 기본적인 코드가 작성되어 있습니다. Stack 자료구조의 특성을 이해하고 FILL_ME_IN을 채워 테스트를 통과해 주세요.
멤버 변수
데이터를 저장할 Object 타입의 storage
마지막에 들어온 데이터를 가리키는 Number 타입의 포인터 top
메서드
size(): 스택에 추가된 데이터의 크기를 리턴해야 합니다.
push(): 스택에 데이터를 추가할 수 있어야 합니다.
pop(): 가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴해야 합니다.
주의 사항
내장 객체 Array.prototype에 정의된 메서드는 사용하면 안 됩니다.
포인터 변수 top의 초기값은 -1, 0, 1등 임의로 지정할 수 있지만,
여기서는 빈 스택을 나타내는 -1으로 초기화되며 이후 push, pop에 따라 1씩 증감해주어 데이터가 추가될 인덱스의 위치를 가리키도록 합니다.
사용예시
const stack = new Stack();
stack.size(); // 0
for(let i = 1; i < 10; i++) {
stack.push(i);
}
stack.pop(); // 9
stack.pop(); // 8
stack.size(); // 7
stack.push(8);
stack.size(); // 8
...
내 코드
class Stack {
constructor() {
this.storage = {};
this.top = -1; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화 합니다.
}
size() {
return Object.keys(this.storage).length;
}
// 스택에 데이터를 추가 할 수 있어야 합니다.
push(element) {
this.top += 1;
this.storage[this.top] = element;
}
// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
pop() {
// 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다
if ( Object.keys(this.storage).length===0) {
return;
}
const result = this.storage[this.top];
delete this.storage[this.top];
this.top -= 1;
return result;
}
}Reference 코드
class Stack {
// stack constructor를 생성합니다.
constructor() {
this.storage = {};
this.top = -1;
}
// stack의 사이즈를 구합니다.
// this.top은 스택이 쌓일 때마다 하나씩 증가하기 때문에 top으로부터 size를 구할 수 있습니다.
// this.top은 스택에 새롭게 추가될 요소의 인덱스를 나타냅니다. 빈 스택을 표현하는 -1부터 1씩 증감하며 표현하며 전체 요소의 개수를 추정할 수 있습니다
size() {
return this.top + 1;
}
// stack에 element를 추가합니다.
// 현재 추가하는 element의 인덱스인 this.top을 키로, 요소를 값으로 하여 storage에 할당합니다.
push(element) {
this.top += 1;
this.storage[this.top] = element;
}
// 만약 size가 0보다 작거나 같다면 이는 비어있는 스택을 의미하므로 아무 일도 일어나지 않습니다.
// stack에서 현재 stack의 최상단에 있는 element를 변수에 저장합니다.
// storage에서 해당 element를 제거합니다.
// 하나를 제거했으니 방금 제거한 element의 인덱스를 나타내는 top 또한 감소시켜 업데이트 해줍니다.
// 최상단에 있던 element가 저장된 변수 result를 반환합니다.
pop() {
if (this.size() <= 0) {
return;
}
const result = this.storage[this.top];
delete this.storage[this.top];
this.top -= 1;
return result;
}
}02_[Queue] 구현
Implementation Queue
Queue 구현을 위한 기본적인 코드가 작성되어 있습니다. Queue 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요.
멤버 변수
데이터를 저장할 Object 타입의 storage
큐의 가장 앞을 가리키는 Number 타입의 포인터 front
큐의 가장 뒤를 가리키는 Number 타입의 포인터 rear
메서드
size(): 큐에 추가된 데이터의 크기를 리턴해야 합니다.
enqueue(): 큐에 데이터를 추가할 수 있어야 합니다.
dequeue(): 가장 먼저 추가된 데이터를 큐에서 삭제하고 삭제한 데이터를 리턴해야 합니다.
주의사항
내장 객체 Array.prototype에 정의된 메서드는 사용하면 안 됩니다.
포인터 변수 front, rear의 초기값은 -1, 0, 1등 임의로 지정할 수 있지만 여기서는 0으로 합니다.
사용예시
const queue = new Queue();
queue.size(); // 0
for(let i = 1; i < 10; i++) {
queue.enqueue(i);
}
queue.dequeue(); // 1
queue.dequeue(); // 2
queue.size(); // 7
queue.enqueue(10);
queue.size(); // 8
queue.dequeue(); // 3
queue.dequeue(); // 4
queue.size(); // 6
...내 코드
class Queue {
constructor() {
this.storage = {};
this.front = 0; //가장 오래된 요소의 위치 = 제일 처음의 위치
this.rear = 0; //가장 마지막에 추가될 요소의 위치 = 제일 마지막 위치+1
}
size() {
return this.rear - this.front;
}//마지막 요소의 인덱스+1 - 제일 처음의 인덱스
//[1,2,3,4,5] this.rear=5, this.front=0
//storage 크기로 해도 통과는 된다.Object.keys(this.storage).length;
// 큐에 데이터를 추가 할 수 있어야 합니다.
enqueue(element) {
this.storage[this.rear] = element;
this.rear += 1;
}
// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다.
dequeue() {
// 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
if (this.size() === 0) {
return;
}
const result = this.storage[this.front];
delete this.storage[this.front];
this.front += 1;
return result;
}
}Reference 코드
class Queue {
//가장 앞에 있는 요소를 front,
//가장 뒤에 있는 요소를 rear 라고 했을 때
//queue constructor 생성
constructor() {
this.storage = {};
this.front = 0;
this.rear = 0;
}
// queue의 사이즈를 구합니다.
// queue는 추가될 때, rear의 값이 커지고 삭제 될 때, front가 변경이 때문에, 각 값을 알아야 size를 구할 수 있습니다.
size() {
return this.rear - this.front;
}
// queue에 element를 추가합니다.
// 새롭게 추가될 요소의 인덱스를 나타내는 this.rear를 키로, 요소를 값으로 하여 storage에 할당합니다. this.rear은 다음 인덱스를 가리키게 하여 새로운 요소에 대비합니다.
enqueue(element) {
this.storage[this.rear] = element;
this.rear += 1;
}
// queue에서 element를 제거 한 뒤 해당 element를 반환합니다.
// 만약 size가 0이라면 아무 일도 일어나지 않습니다.
// this.front+1로 가장 앞에 있는 요소를 다시 설정한 후 변수에 저장하고, 큐에서 삭제합니다.
dequeue() {
if (this.size() === 0) {
return;
}
const result = this.storage[this.front];
delete this.storage[this.front];
this.front += 1;
return result;
}
}03_[Stack] 유효한 괄호쌍 문제
문제
입력된 괄호 값들이 모두 쌍이 맞게 올바른지를 판단해 모두 쌍이 맞으면 true 그렇지 않으면 false를 출력하세요.
입력된 괄호 값들이 유효한 경우들은 다음에 해당합니다.
1. 열린 괄호는 같은 타입의 닫힌 괄호로 닫혀있어야 한다.
2. 열린 괄호는 올바른 순서대로 닫혀야만 한다.
3. 모든 닫힌 괄호는 그에 상응하는 같은 타입의 열린 괄호를 갖고 있다.
입력값을 통해 들어오는 괄호는 ()[]{}로만 이루어져 있습니다.
입력
인자 1 : str
string 타입으로 된 문장
출력
boolean 타입을 리턴해야 합니다.
주의 사항
입력값을 통해 들어오는 괄호는 ()[]{}로만 이루어져 있습니다.
입력값으로 들어오는 str의 길이는 0부터 10^4승 까지 입니다.
입출력 예시
const result1 = isValid('[]');
console.log(result1); // true
const result2 = isValid('[)');
console.log(result2); // false
const result3 = isValid('[]{}()');
console.log(result3); // true
const result4 = isValid('[]{)()');
console.log(result4); // false힌트
스택을 사용해 보세요.
열린 괄호인 경우 스택에 push합니다.
닫힌 괄호인 경우에는 스택의 top을 확인하고, 해당 닫힌 괄호와 짝이 맞는 열린 괄호인지를 확인합니다.
내 코드
const isValid = (str) => {
let storage = [];
let result = false; //기본값은 false로 지정
let obj = { //obj키값쌍을 괄호로 정함
'(': ')',
'[': ']',
'{': '}'
}
let arr = str.split("");
for(let i=0; i<arr.length; i++){
if(arr[i] === '[' || arr[i] === '{' || arr[i] === '('){ //열린괄호라면 stack에 push
storage.push(arr[i]);
}
else{
let top = storage.pop(); //바로 전 요소
if(arr[i] === obj[top]) result = true; //바로 전 요소의 키값과 현재 요소를 비교
else result = false;
}
}
return result;
}
//열린괄호 [, {, ( 인 경우 스택에 push
//닫힌괄호 ], }, ) 인 경우 스택에 top을 확인하고(=바로 전의 요소확인)
//해당 닫힌 괄호와 짝이 맞는 열린괄호인지 확인
//맞으면 true, 틀리면 falseReference 코드
const isValid = (str) => {
// 최초 입력값이 빈 값이라면 유효하지 않은 괄호쌍으로 간주합니다.
if (str.length === 0) return false;
// 각각의 여는 괄호에 알맞는 닫는 괄호를 매칭시키기 위한 괄호맵 생성.
const braketsMap = {
'(': ')',
'[': ']',
'{': '}'
};
const arr = str.split('');
const stack = [];
for (let i = 0; i < arr.length; ++i) {
// 1. 여는 괄호 -> stack에 push해야 하는 케이스
if (arr[i] === '(' || arr[i] === '[' || arr[i] === '{') {
stack.push(arr[i]);
} else {
// 2. 닫는 괄호 -> stack에서 pop해야 하는 케이스
// 먼저 현재 stack의 가장 위에 위치한 괄호를 확인하고
const lastElementOfStack = stack[stack.length - 1];
// 지금 처리해야하는 닫힌 괄호인 arr[i]의 짝과 맞는지를 확인 후 맞지 않다면 false를 리턴하고 로직 전체를 종료
if (braketsMap[lastElementOfStack] !== arr[i]) return false;
// 짝이 맞다면 현재 stack의 가장 위에 위치한 괄호를 pop시켜서 stack에서 제거해줌
stack.pop();
}
}
// arr 배열전체를 돌면서 해당 로직을 이행한 후 stack에 어떠한 열린괄호라도 남아있다면 쌍이 맞지 않는 괄호들이 인풋으로 들어왔기 때문에 false를 반환, 그렇지 않고 stack이 비어져 있다면 모든 괄호쌍이 문제없이 유효한 괄호쌍이므로 true를 반환
return stack.length ? false : true;
};04_[Queue] 박스 포장
문제
마트에서 장을 보고 박스를 포장하려고 합니다. 박스를 포장하는 데는 폭이 너무 좁습니다. 그렇기에 한 줄로 서 있어야 하고, 들어온 순서대로 한 명씩 나가야 합니다.
불행 중 다행은, 인원에 맞게 포장할 수 있는 기구들이 놓여 있어, 모두가 포장을 할 수 있다는 것입니다. 짐이 많은 사람은 짐이 적은 사람보다 포장하는 시간이 길 수밖에 없습니다.
뒷사람이 포장을 전부 끝냈어도 앞사람이 끝내지 못하면 기다려야 합니다. 앞사람이 포장을 끝내면, 포장을 마친 뒷사람들과 함께 한 번에 나가게 됩니다.
만약, 앞사람의 박스는 5 개고, 뒷사람 1의 박스는 4 개, 뒷사람 2의 박스는 8 개라고 가정했을 때, 뒷사람 1이 제일 먼저 박스 포장을 끝내게 되어도 앞사람 1의 포장이 마칠 때까지 기다렸다가 같이 나가게 됩니다.
이때, 통틀어 최대 몇 명이 한꺼번에 나가는지 알 수 있도록 함수를 구현해 주세요.
입력
인자 1 : boxes
Number 타입을 요소로 갖는, 포장해야 하는 박스가 담긴 배열
1 ≤ 사람 수 ≤ 10,000
1 ≤ 박스 ≤ 10,000
출력
Number 타입을 리턴해야 합니다.
주의 사항
먼저 포장을 전부 끝낸 사람이 있더라도, 앞사람이 포장을 끝내지 않았다면 나갈 수 없습니다.
예시
만약 5, 1, 4, 6이라는 배열이 왔을 때, 5개의 박스를 포장하는 동안 1, 4 개의 박스는 포장을 끝내고 기다리게 되고, 6 개의 박스는 포장이 진행 중이기 때문에, 5, 1, 4 세 개가 같이 나가고, 6이 따로 나가게 됩니다. 그렇기에 최대 3 명이 같이 나가게 됩니다.
const boxes = [5, 1, 4, 6];
const output = paveBox(boxes);
console.log(output); // 3
const boxes2 = [1, 5, 7, 9];
const output2 = paveBox(boxes2);
console.log(output2); // 1내 코드
function paveBox(boxes) {
// TODO: 여기에 코드를 작성합니다.
let front = 0; //queue의 0번 인덱스 값
let rear = 0; // queue에서 가장 최근에 나간 값
let num=0; // 한 번에 나가는 사람의 수
let max=0; //num에서 최대값
while(boxes.length>0){ //boxes요소는 계속 삭제되므로 요소가 0보다 클때까지만 반복
if(num===0){ //처음일때랑 front>rear에 걸려 num이 초기화되었을 때 거치고 간다.
rear = boxes.shift(); //첫 요소 삭제, 삭제된 요소가 rear로 고정
front = boxes[0]; //삭제된 후의 첫요소가 front
num++; //처음꺼 삭제했으므로 나가는 사람수+1
}
else if(front<=rear){ //현재 삭제된 요소보다 0번째 인덱스 요소가 작거나 같으면 내보내기 front=1;rear=5;
boxes.shift();
num++; //나가는 사람+1
front = boxes[0]; //원래 0번째인덱스에 있던게 나갔으므로 새롭게 0번째 인덱스값을 front로 지정
}
else if(front>rear){ //현재 삭제된 요소보다 0번째 인덱스 요소가 더 크다면 front=5;rear=1;
if(max < num) max = num; //num이 max보다 크다면 max에 num을 넘겨주고
num=0; //num은 다시 초기화
}
if(max < num) max = num; //max와 num이 다를때 num이 더 크면 큰 값으로 max 업데이트
}
return max;
}
//앞에서부터 차례대로 인덱스 i가 i+1의 값보다 더 크면 -> 같이 나가는 사람 수++
//boxes[0]>boxes[1] num++
//boxes[0]>boxes[2] num++Reference 코드
function paveBox(boxes) {
let answer = [];
// boxes 배열이 0보다 클 때까지 반복합니다.
while(boxes.length > 0){
let finishIndex = boxes.findIndex(fn => boxes[0] < fn);
if(finishIndex === -1){
// 만약 찾지 못했다면 answer에 boxes 배열의 길이를 넣은 후, boxes 내부의 요소를 전부 삭제합니다.
answer.push(boxes.length);
boxes.splice(0, boxes.length);
} else {
// 만약 찾았다면, 해당 인덱스를 answer에 넣고, boxes에서 그만큼 제외합니다.
answer.push(finishIndex);
boxes.splice(0, finishIndex);
}
}
// 결과물을 반환합니다.
return Math.max(...answer);
}