괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력하는 프로그램.
(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.
스택을 활용한 문제.
👉 스택 : 들어가는 입구와 나가는 출구가 동일한 구조에 활용한다. (가장 나중에 들어간 것이 가장 먼저 나오는 로직 LIFO Last In First Out) push 와 pop을 활용한다.
//나의 풀이
function solution(s) {
let answer = "YES";
let sH = new Map();
for (let x of s) {
sH.has(x) ? sH.set(x, sH.get(x) + 1) : sH.set(x, 1);
}
if (sH.get("(") !== sH.get(")")) return "NO";
return answer;
}
선생님 풀이 (스택을 활용하여)
function solution(s) {
let answer = "YES";
let stack = [];
for (let x of s) {
if (x === "(") stack.push(x);
else {
//')'가 더 많은 상황
if (stack.length === 0) return "NO";
stack.pop();
}
}
// '('' 가 더 많은 상황
if (stack.length > 0) return "NO";
return answer;
}
let a = "(()(()))(()";
console.log(solution(a)); //"NO"
입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력하는 프로그램을 작성하기.
function solution(s) {
let answer;
let stack = [];
for (let x of s) {
if (x === ")") {
while (stack.pop() !== "(");
} else stack.push(x);
}
answer = stack.join("");
return answer;
}
let str = "(A(BC)D)EF(G(H)(IJ)K)LM(N)";
console.log(solution(str)); //EFLM
N x N 크기의 정사각 격자 안에 0~5까지의 다른 종류의 인형들이 있다.
인형을 뽑아 바구니에 아래에서 위로 하나씩 차곡차곡 쌓는다. 만약 바구니의 맨 위에 있는 인형과 뽑은 인형의 종류가 같을 시 두 인형은 사라진다.
게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위 치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성하라.
function solution(board, moves) {
let answer = 0;
let stack = [];
moves.forEach((pos) => {
for (let i = 0; i < board.length; i++) {
if (board[i][pos - 1] !== 0) {
let tmp = board[i][pos - 1]; // 꺼내기
board[i][pos - 1] = 0; // 꺼낸 부분 빈공간 만들기
if (tmp === stack[stack.length - 1]) {
stack.pop();
answer += 2;
} else stack.push(tmp);
break; // break를 안해주면 한 줄에 있는 모든 인형을 다 꺼내버림, 하나만 꺼낸 뒤 break 걸어주고 다음 postion으로 옮기기
}
}
});
return answer;
}
let a = [
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 3],
[0, 2, 5, 0, 1],
[4, 2, 4, 4, 2],
[3, 5, 1, 3, 1],
];
let b = [1, 5, 3, 5, 1, 2, 1, 4];
console.log(solution(a, b)); //4
후위연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하기
만약 3(5+2)-9 을 후위연산식으로 표현하면 352+9- 로 표현되며 그 결과는 12이다.
function solution(s) {
let answer;
let stack = [];
for (let x of s) {
if (!isNaN(x)) stack.push(Number(x));
// 숫자화 시켜서 넣어줄 것!
else {
let rt = stack.pop(); // 먼저 나오는 것
let lt = stack.pop();
if (x === "+") stack.push(lt + rt);
else if (x === "-") stack.push(lt - rt);
else if (x === "*") stack.push(lt * rt);
else if (x === "/") stack.push(lt / rt);
}
}
answer = stack[0];
return answer;
}
let str = "352+*9-";
console.log(solution(str)); //12
1 . 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반 드시 레이저를 표현한다.
2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.
쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하기.
⭐️ 괄호문제는 대부분 스택문제라고 보면 된다.
function solution(s) {
let answer = 0;
let stack = [];
for (let i = 0; i < s.length; i++) {
if (s[i] === "(") stack.push(s[i]);
else {
stack.pop();
// 레이저인 경우
if (s[i - 1] === "(") answer += stack.length;
else {
// 막대기가 끝나는 경우
answer += 1;
}
}
}
return answer;
}
let a = "()(((()())(())()))(())";
console.log(solution(a)); //17
⭐️ 막대기를 계속 넣다가 레이저가 나오면 레이저 빼주고 answer에 막대기 갯수만큼 더해주고 막대기가 끝나면 answer에 하나 더해주는 로직
1번 왕자부터 N 번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다.
마지막에 남은 왕자의 번호를 구하는 프로그램 만들기.
👉 큐 : 먼저 들어간게 먼저 나온다. 들어가는 입구와 나오는 출구가 다르다. 배열을 사용한다. First In First Out(FIFO)
function solution(n, k) {
let answer = 0;
let queue = Array.from({ length: n }, (v, i) => i + 1);
while (queue.length) {
for (let i = 1; i < k; i++) queue.push(queue.shift());
queue.shift();
if (queue.length === 1) answer = queue.shift();
}
return answer;
}
console.log(solution(8, 3)); //7
필수과목순서가 주어지면 N개의 수업설계가 잘된 것이면 “YES", 잘못된 것이면 ”NO“를 출력하는 프로그램을 작성하기.
필수과목의 순서와 수업설계에 들어있는 필수과목의 순서가 일치해야한다.
function solution(need, plan) {
let answer = "YES";
let queue = need.split("");
for (let x of plan) {
if (queue.includes(x)) {
if (queue.shift() !== x) return "NO";
}
}
if (queue.length > 0) return "NO";
return answer;
}
let a = "CBA";
let b = "CBDAGE";
console.log(solution(a, b)); //YES