(참고) 자료구조 시각 자료 사이트
※ class (객체 지향) 문법
→ 비슷한 객체(object)를 많이 만들고 싶을 때 사용!
// class 키워드의 예
class Person { // 클래스 작명은 대문자로
constructor(name, age) {
this.name = name; // 새로 생성되는 객체에 {name : name}을 추가
this.age = age;
}
speak() {
return `저는 ${this.name}입니다.`}
}
const dd = new Person('최예슬', 30);
console.log(dd.speak()); // '저는 최예슬입니다.'
스택(Stack)
후입선출(LIFO). 배열의 pop() 메서드를 생각하면 된다.
예시 : 앞으로 가기, 뒤로 가기 구현
[Stack] 구현
class Stack { // 중요한 건 push, pop 메서드!
constructor() { // 생성자
this.storage = {};
this.top = -1; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화 합니다.
} // storage는 객체 형태의 스택. top은 마지막으로 들어간 값의 키값.
size() { //스택에 추가된 데이터의 크기 -> 개수를 의미.
return Object.keys(this.storage).length; // this.top + 1 이렇게 쓰는 게 더 간단할 듯
}
// 스택에 데이터를 추가 할 수 있어야 합니다.
push(element) {
this.top += 1;
this.storage[this.top] = element;
}
// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
pop() { //무조건 최상단 값을 뽑으므로 매개변수가 필요없다.
// 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다. 예외처리 중요!
if (Object.keys(this.storage).length === 0) {
// this.top === -1 방어적으로 짜려면 < 0 이렇게 짤수도 있다.
// 앞에 만든 메서드를 이용해도 좋을 듯. this.size <= 0
return; // 뭘 리턴?? -> 시스템 나가리되지만 않게 하는 것임. 스택이 비어있다는 알림을 보여주면 더 좋을 듯
}
const result = this.storage[this.top];
delete this.storage[this.top];
this.top -= 1;
return result;
}
}
// 배열로 구현
// const stack = new Array(); 미리 정의된 Array 객체를 사용할 수 있습니다.
const stack = [];
stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]
stack.push(4); // [1, 2, 3, 4]
stack.push(5); // [1, 2, 3, 4, 5]
console.log(stack); // [1, 2, 3, 4, 5]
//제일 마지막에 들어간 요소부터 빼내기 위해 pop() 메소드를 사용합니다.
stack.pop(); // [1, 2, 3, 4]
stack.pop(); // [1, 2, 3]
console.log(stack); // [1, 2, 3]
큐(Queue)
선입선출(FIFO). 배열의 shift() 메서드를 생각하면 된다.
예시 : 프린터 인쇄 순서
[Queue] 구현
class Queue {
constructor() {
this.storage = {};
this.front = 0; // 큐의 가장 앞을 가리키는 Number 타입의 포인터
this.rear = 0; // 큐의 가장 뒤를 가리키는 Number 타입의 포인터
}
size() {
return Object.keys(this.storage).length; // this.rear - this.front
}
// 데이터를 추가할 때는 뒤에 추가
enqueue(element) {
this.storage[this.rear] = element;
this.rear += 1;
}
// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다. 앞을 추출
dequeue() {
// 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
// 만약 size가 0이라면 아무 일도 일어나지 않습니다
if (Object.keys(this.storage).length === 0) {
return;
}
const result = this.storage[this.front];
delete this.storage[this.front];
this.front += 1;
return result;
}
}
// 배열로 구현
//const queue = new Array(); 미리 정의된 Array 객체를 사용할 수 있습니다.
const queue = [];
queue.push(1); // [1]
queue.push(2); // [1, 2]
queue.push(3); // [1, 2, 3]
queue.push(4); // [1, 2, 3, 4]
queue.push(5); // [1, 2, 3, 4, 5]
console.log(queue); // [1, 2, 3, 4, 5]
//제일 먼저 들어간 것부터 빼내기 위해 shift() 메소드를 사용합니다.
queue.shift(); // [2, 3, 4, 5]
queue.shift(); // [3, 4, 5]
console.log(queue); // [3, 4, 5]
▶ Stack - 유효한 괄호쌍 문제 << 현장 가면 많이 나오는 기출문제!
입력된 괄호 값들이 모두 쌍이 맞게 올바른지를 판단해 모두 쌍이 맞으면 true 그렇지 않으면 false를 출력
// 입출력 예시
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
// 나의 풀이
class Stack {
constructor() {
this.storage = {};
this.top = -1;
}
size() {
return this.top + 1;
}
push(element) {
this.top += 1;
this.storage[this.top] = element;
}
pop() {
if (this.size() <= 0) {
return;
}
const result = this.storage[this.top];
delete this.storage[this.top];
this.top -= 1;
return result;
}
}
const isValid = (str) => {
//문자열을 풀어 배열로 만들어서
//순회하며 열린 괄호인 경우 스택에 push
//닫힌 괄호인 경우 스택의 top 값을 확인해서 짝이 맞으면 스택에서 pop
//스택의 길이가 0이면 true
if (str === ''){
return false;
}
const stack = new Stack();
const arr = [...str];
for(let i = 0; i < arr.length; i++){
if(arr[i] === '(' || arr[i] === '[' || arr[i] === '{'){
stack.push(arr[i])
} else if(arr[i] === ')'){
if(stack.storage[stack.top] === '(') {
stack.pop()
continue;
} return false;
} else if(arr[i] === ']'){
if(stack.storage[stack.top] === '[') {
stack.pop()
continue;
} return false;
} else if(arr[i] === '}'){
if(stack.storage[stack.top] === '{') {
stack.pop()
continue;
} return false;
}
}
return stack.size() === 0;
}
스택을 사용해서 풀어보라고 해서 앞서 구현한 스택 클래스를 가지고 와 풀어보았다. 주석에 적어 놓은 대로 열린 괄호는 스택 안에 넣고, 닫힌 괄호는 스택 상단에 있는 열린 괄호와 비교해서 짝이 맞으면 해당 열린 괄호를 스택에서 빼주는 방식으로 구현하였다. 마지막에 스택에 남은 데이터가 있으면 짝이 안 맞는다는 뜻이니 이때 false가 리턴될 수 있도록 하였다. 하지만 이렇게만 하면 ']]'와 같이 닫힌 괄호만 있을 때에도 스택이 최종적으로 비게 되어 true가 리턴된다는 문제를 발견했다. 페어 분들과 같이 고민하여 닫힌 괄호의 경우 짝이 안 맞으면 바로 false가 리턴될 수 있도록 코드를 수정했고, 테스트를 통과하였다.
// 레퍼런스 풀이
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;
};
더 간단하게 쓸 수 있을 것 같아서 레퍼런스 코드를 보았는데, 역시 로직은 비슷한데 코드가 훨씬 깔끔한 것 같다. 여는 괄호, 닫는 괄호 매칭용 괄호맵을 생성해서 푸는 방법이 생각지 못한 부분이라 신박하게 느껴졌다. 다음에 써먹어봐야겠다.
▶ Queue - (마트) 박스 포장
들어온 순서대로 한 명씩 나가야 하는 상황. 뒷사람이 포장을 전부 끝냈어도 앞사람이 끝내지 못하면 기다려야 함.
최대 몇 명이 한꺼번에 나가는지 알 수 있도록 함수를 구현
// 입출력 예시
const boxes = [95, 90, 99, 99, 80, 99];
const output = paveBox(boxes);
console.log(output); // 4
// 레퍼런스 풀이를 참고한 풀이
function paveBox(boxes) {
//1번이 2번보다 크거나 같으면 둘이 같이 나감
//-> 1번보다 큰 수가 나오기 전까지 같이 나감
// for(let i = 0; i < boxes.length; i++){
// for(let j = 1; i < boxes.length; j++){
// if(boxes[i] < boxes[j]){
// return j-i;
// }
// }
// }
// 위 처럼 풀면 뒤에 더 많은 사람이 모였을 때를 못 걸러냄
let answer = []; //한꺼번에 나가는 사람들의 수 뭉치 모음
// boxes 배열이 0보다 클 때까지 반복
while(boxes.length > 0){
let finishIndex = boxes.findIndex(v => boxes[0] < v);
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);
}
처음엔 이중 반복문을 통해 문제를 풀어보려고 했는데, 코드가 쓸 데 없이 너무 많은 처리를 하게 되어 그런 지 테스트가 돌아가질 않았다. 콘솔 창에선 돌아가긴 하는데, 아무래도 다른 방법을 이용하는 게 좋을 것 같아 페어 분들 코드도 보고 좀 더 고민을 하다 레퍼런스 코드를 봤다. 한 줄씩 이해해 보는데, finishIndex를 찾지 못했을 때를 거르는 조건문이 이해가 잘 안됐다. 콘솔을 찍어보니 실제로 -1의 인덱스 값이 나오기는 하는데, 왜 undefined 같은 게 아닌지 모르겠다.
-> https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/findIndex
Array.prototype.findIndex() - JavaScript | MDN
The findIndex() method returns the index of the first element in an array that satisfies the provided testing function. If no elements satisfy the testing function, -1 is returned.
developer.mozilla.org
findIndex() 자체가 테스트를 통과하는 배열의 요소가 없을 때 -1을 반환해서 그런 것 같다.
오늘 배운 stack이나 queue는 개념 자체는 어렵지 않은데, 관련 알고리즘 문제를 풀어보니 생각보다 생각할 게 많았다. 익숙하지 않은 부분도 있고, 특히 자바스크립트 문법이 부족하다는 것을 많이 느꼈다. 앞으로 꾸준히 알고리즘 문제를 풀어보며 공부해야겠다.
'22.12.15 ~ 23.06.08 코드스테이츠' 카테고리의 다른 글
| [네트워크] 심화 (0) | 2023.03.06 |
|---|---|
| [사용자 친화 웹] 웹 접근성 (0) | 2023.03.03 |
| [사용자 친화 웹] 웹 표준 (0) | 2023.02.28 |
| [React] Custom Component(2) (0) | 2023.02.21 |
| [React] Custom Component(1) (0) | 2023.02.20 |
댓글