스택, 큐

유일하게 자료구조 알고리즘 파트에서 내가 익숙한 구간이어서 최대한 스스로 문제를 풀어보려고 노력했다

(1) 올바른 괄호

• 괄호가 입력되어서 올바른 괄호면 "YES" 그렇지 않으면 "NO"

function solution(s){

  let answer = 'YES';
  let stack = [];

  for(let x of s ){

    if(x !== ')'){ // ')' 가 아니라면  스택에 넣어준다
      stack.push(x);
    }
    else{
      stack.pop(); // ')' 라면 stack 마지막 인덱스를 빼준다 
    }
  }

  if(stack.length){ // '(' 와 ')' 의 수가 똑같다면 올바른 괄호들 
    // 올바른 괄호면 같은 수 만큼 push, pop을 진행했기 때문에 stack이 비어있다 
    return 'NO';
  }

  return answer;

}


console.log(solution("(())()")); // YES
console.log(solution("(()(()))(()"));//NO 

(2) 괄호문자 제거

• 입력된 문자열에 () 사이에 존재하는 애들 빼고 남는 애들만 출력해라

function solution(str){

  let answer = "";

  let stack = [];

  for( let s of str){
    if(s !==')'){
      stack.push(s); // ')' 가 아니라면 스택에 넣어준다 
    }
    else{
      while(stack.pop() !== '('); // stack 에서 '(' 만날 때 까지 빼준다 '( ' 포함되어서 빠진다 ! 
    }
  }

  answer = stack.join(''); //스택에 남아있는 애들 문자열로 만든다 
  return answer;
}


console.log(solution("(A(BC)D)EF(G(H)(IJ)K)LM(N)"));

(3) 후위식 연산

• 후위 연산식이 주어지면 연산한 결과를 출력
• 후위 연산은 왼-> 오 -> 부 의 기준으로 트리가 형성된다

-left 가 연산 당하는 변수

function solution2(s){

  let answer = 0;

  let stack = [];

  for(let x of s){

    if(isNaN(x)){ //후위식은 왼-> 오 -> 부 의  준으로 트리가 정렬됨
      let right = stack.pop(); // 그래서 lefe 값을 기준으로 산술 연산을 한다 
      let left = stack.pop();

      if(x === '+'){
        stack.push(left+right);
      }
      else if(x === '-'){
        stack.push(left-right);
      }
      else if(x === '*'){
        stack.push(left*right);
      }
      else if(x === '/'){
        stack.push(left/right);
      }
    }
    else{
      stack.push(Number(x)); // 연산을 위해 push 시에 Number()로 형변환을 해줘야한다 
    }
  }
  answer = stack[0];
  return answer;
}

console.log(solution2("352+*9-"));

(4) 연속된 문자 지우기

• 연속되어있는 문자를 제거하여서 최종적으로 남는 문자만으로 이루어진 문자열을 출력하라

function solution(s){
  let answer ="";

  let stack = [];

  for(let x of s){
    if(stack.length > 0 && stack[stack.length-1] === x) // stack에 값이 있고 , pop 으로 가져오면 계속 스택이 비어가는 형태가 되기 때문에 인덱스 값으로 조회하여 비교 
    stack.pop(); // 연속된 문자라면 pop () 제거한다 
    else stack.push(x); // 마지막에 stack 에 있는 값이랑 같지 않으면 stack에 추가!
  }

  answer = stack.join("");
  return answer;
}
console.log(solution("acbbcaa")); //a

console.log(solution("bacccaba"));//bacaba

(5) 공주 구하기

• 한 왕자가 특정 숫자를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게된다 이렇게 마지막까지 남은 왕자의 번호를 출력하라

function solution(n,k){

  let answer = 0;

  let stack = Array(n).fill(1).map((v,i)=> i+1); // n 만큼의 왕자 배열 생성 후 번호 배정

  while(stack.length){ // n 만큼 돌면서 순서대로 번호를 외친다 
    for(let i = 0 ; i<k-1 ; i++){ 
      stack.push(stack.shift()); // 1 번째 ~ k - 1 번째 까지 해당하는 번호이므로 제외 대상이 아니기에 스택의 제일 뒤로 보내준다 
    }
    stack.shift(); // 특정 숫자 k에 해당하는 왕자이므로 제외 
  
  if(stack.length === 1) answer = stack.shift(); // 마지막까지 남은 왕자의 번호를 리턴 
  }
  return answer;
}   


console.log(solution(8,3));

(6) 교육과정 설계

• 이수해야하는 필수과목이 있고 그 순서도 정해져있다 현수가 짠 수업 계획이 이 필수과목들이 모두 포함되어있고 순서도 맞는지를 YES/NO 로 출력하라

function solution(n,k){

  let answer = 0;

  let stack = Array(n).fill(1).map((v,i)=> i+1); // n 만큼의 왕자 배열 생성 후 번호 배정

  while(stack.length){ // n 만큼 돌면서 순서대로 번호를 외친다 
    for(let i = 0 ; i<k-1 ; i++){ 
      stack.push(stack.shift()); // 1 번째 ~ k - 1 번째 까지 해당하는 번호이므로 제외 대상이 아니기에 스택의 제일 뒤로 보내준다 
    }
    stack.shift(); // 특정 숫자 k에 해당하는 왕자이므로 제외 
  
  if(stack.length === 1) answer = stack.shift(); // 마지막까지 남은 왕자의 번호를 리턴 
  }
  return answer;
}   


console.log(solution(8,3));