스택, 큐, 디큐

---

올바른 괄호

1. 스택배열 생성
2. 반복문을 돌며 "("이면 stack에 "(" push
3. 돌며 ")"이 나왔을 때 stack의 길이가 0이면 'NO'반환
4. stack.pop()
5. 만약 반복문을 다 돌았는데 stack에 남아있는 값이 있다면 'NO'반환
6. stack에 남아있는 것이 아무것도 없다면 'YES'반환

function solution(s) {
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") stack.push("(");
    else {
      if (stack.length === 0) return "NO";
      stack.pop();
    }
  }
  if (stack.length !== 0) return "NO";
  return "YES";
}

괄호 문자제거

1. 스택배열 생성
2. 반복문을 돌며 ")"를 제외한 모든 문자를 stack에 할당
3. 그러다 ")"을 만나면 "("를 만날 때까지 stack.pop()
4. stack.join('') 반환

function solution(s) {
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] === ")") {
      while (stack.pop() !== "(");
    } else {
      stack.push(s[i]);
    }
  }
  return stack.join("");
}

후위식 연산

전위순회의 순서
부모 -> 왼쪽자식 -> 오른쪽자식
1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7

중위순회의 순서
왼쪽자식 -> 부모 -> 오른쪽자식
4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7

후위순회의 순서
왼쪽자식 -> 오른쪽자식 -> 부모
4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1

1. 스택 배열 생성
2. 문자열을 돌며 숫자라면 stack에 현재 숫자를 push
3. 숫자가 아니라면(연산자) rt와 lt에 stack.pop()을 할당(순서중요)
4. 현재 연산자에 따라 맞는 값을 stack에 push
5. stack[0]을 answer에 할당
6. answer 반환

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;
}

연속된 문자 지우기

1. 스택 배열 생성
2. 반복문을 돌며 stack이 존재하고(0이 아니고) stack의 최상단이 현재 문자열이라면
3. stack.pop()
4. 아니라면 stack.push(현재문자열)
5. stack.join('') 반환

function solution(s) {
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    if (stack.length > 0 && stack[stack.length - 1] === s[i]) {
      stack.pop();
    } else stack.push(s[i]);
  }
  return stack.join("");
}

공주 구하기

1. 1부터 n까지 포함된 que배열 생성
2. que가 존재할때까지 반복
3. k까지 반복문을 돌며 que의 최하단값을 최상단으로 push
4. k만큼 돌았으면 que의 최하단값 deque
5. deque했을 때 큐에 남은값이 하나라면 answer에 que.shift()값 할당
6. answer 반환

function solution(n, k) {
  let que = Array.from({ length: n }, (v, i) => i + 1);
  let answer = 0;
  while (que.length) {
    for (let i = 1; i < k; i++) que.push(que.shift());
    que.shift();
    if (que.length === 1) answer = que.shift();
  }
  return answer;
}

교육과정 설계

1. 필수과정을 배열화한 que배열 생성
2. 현 계획만큼 반복문을 돌며 que에 현재 문자열이 있는지 확인
3. 있고 que.shift()한 값과 일치하지 않는다면 'NO'반환
4. 반복문이 끝난 후 que가 남아있다면 'NO'반환
5. 큐가 남아있지 않다면 'YES' 반환

function solution(need, plan) {
  let answer = "YES";
  let que = need.split("");
  for (let p of plan) {
    if (que.includes(p)) {
      if (p !== que.shift()) return "NO";
    }
  }
  if (que.length > 0) return "NO";
  return answer;
}

최소매출

1. deque 배열 생성
2. k만큼 반복문을 돌며 deque가 존재하고 deque의 마지막의 0번 인덱스값이 현재값보다 크다면
3. deque.pop()
4. deque에 현재값과 인덱스값을 담은 배열 push
5. nums배열길이만큼 반복문을 돌며 i에 k-1값을 할당
6. deque가 존재하고 deque의 마지막의 0번 인덱스값이 현재값보다 크다면
7. deque.pop()
8. deque에 현재값과 인덱스값을 담은 배열 push
9. answer에 deque[0][0]을 push
10. 만약 deque[0][1]이 i - k + 1과 같다면 deque.shift()

function solution(nums, k) {
  let answer = [];
  let deque = [];
  for (let i = 0; i < k - 1; i++) {
    while (deque.length > 0 && deque[deque.length - 1][0] > nums[i]) {
      deque.pop();
    }
    deque.push([nums[i], i]);
  }
  for (let i = k - 1; i < nums.length; i++) {
    while (deque.length > 0 && deque[deque.length - 1][0] > nums[i]) {
      deque.pop();
    }
    deque.push([nums[i], i]);
    answer.push(deque[0][0]);
    if (deque[0][1] === i - k + 1) deque.shift();
  }
  return answer;
}

최소값

1. 숫자값을 문자열화와 배열화를 시켜 할당
2. stack 배열 생성
3. stack에 아무것도 없다면 stack에 0번인덱스값 할당
4. 반복문을 돌며 stack의 최상단값이 현재값보다 크고 k가 0보다 크다면
5. stack.pop(), k--
6. stack에 현재값 push
7. stack배열 join
8. stack이 존재하지 않으면 0반환
9. stack을 숫자화하면 반환

function solution(num, k) {
  num = num.toString().split("");
  let stack = [];

  for (let i = 1; i < num.length; i++) {
    if (stack.length === 0) stack.push(num[i - 1]);
    while (0 < k && stack[stack.length - 1] > num[i]) {
      stack.pop();
      k--;
    }
    stack.push(num[i]);
  }

  stack = stack.join("");
  if (stack.length === 0) return 0;
  return Number(stack);
}