2021.8.13 TIL (stack, queue 를 이용한 알고리즘 3)

 

목차

1. Prefix 연산

2. 쇠 막대기 절단 개수

3. 공주 구하기

 

---

Postfix 연산 (stack)

해당 연산을 구현하는 함수 만들기. (3 * (5 + 2))- 9를 postfix로 표현하면 352+*9-다. 위의 예를 postfix 식으로 표현하는 과정은 다음과 같다.

• (3 * (5 + 2)) - 9
• (3 * (5 + 2)) 9 -
• 3 (5 + 2) * 9 -
• 3 5 2 + * 9 -

 

function postfix(str) {
  let answer;
  // code here;
  return answer;
}
let str = '352+*9-';
console.log(postfix(str)); //12

 

 

 

답) postfix 로 구현된 식을 stack을 이용해서 원래의 식(infix)로 표현해보자

• [] 3 5 2 + * 9 -
• [ 3 ] 5 2 + * 9 -
• [ 3, 5 ] 2 + * 9 -
• [ 3, 5, 2 ] + * 9 -
• [3, (5 + 2) ] * 9 -
• [3 * 7] 9 -
• [21 - 9]
• 12

 

function postfix(str) {
  let answer;
  let stack = [];
  
  for(let el of str) {
    if(!isNaN(el)) {
      stack.push(el)
    } else {
      let a = stack.pop();
      let b = stack.pop();
      let action = eval(b + el + a);
      stack.push(action)
    }
  }
  answer = stack[0]
  return Number(answer);
}

 

eval()은 자바스크립트 내장함수로 '3 + 2' 를 5로 리턴해준다.

 

 

쇠막대기 절단 (stack)

쇠막대기를 절단하려고 한다. ( )는 레이저를 말하며, (())는 가운데 레이저를 낀 쇠막대기다. 레이저가 쇠막대기를 절단하려고 할 때, 만들어지는 쇠막대기의 개수는 몇 개인가?

예시) '()(((()())(())()))(())'

 

function cutStick(str) {
  let answer;
  // code here;
  return answer;
}
let str = '()(((()())(())()))(())';
console.log(cutStick(str)); //17

 

 

답)

• '('일 때는 stack 에 담는다
• ')'일 때는 바로 직전의 문자열이 무엇인지 체크한다.
• '('가 전 문자일 경우 ()로 레이저다. stack에서 레이저 1개를 제외하고, stack에 담긴 문자열이 몇 개인지 더한다. 그림에서 파란색 박스인 부분
• ')'가 전 문자일 경우 쇠막대기다. stack에서 레이저 1개를 제외하고, 절단된 한 개의 쇠막대기를 더한다. 그림에서 초록색 박스인 부분

function cutStick(str) {
  let answer = 0;
  let stack = [];
  let open = '(', close = ')';
  
  for(let i = 0; i < str.length; i++) {
    if(str[i] === open) stack.push(str[i]);
    else {
      if(str[i - 1] === open) { // 레이저 일 때
        stack.pop();
        answer += stack.length;
      } else {  // 쇠막대기가 끝났을 때
        stack.pop();
        answer++;
      }
    }
  }
  
  return answer;
}

 

 

공주 구하기 (queue)

1 ~ n명의 왕자가 동그랗게 앉아 있을 때, k번 째 앉은 왕자는 자리에서 박탈된다. 계속 무한 반복하다가 남은 1명의 최종 왕자가 공주를 구한다.

 

function prince(n, k) {
  let anwser;
  // code here
  return answer;
}

console.log(prince(8, 3)) //7

 

• [ 1, 2, 3, 4, 5, 6, 7, 8 ]
• [ 2, 3, 4, 5, 6, 7, 8, 1 ]
• [ 3, 4, 5, 6, 7, 8, 1, 2 ]
• [ 4, 5, 6, 7, 8, 1, 2 ] // 3은 타겟 넘버로 삭제
• [ 5, 6, 7, 8, 1, 2, 4 ]
• [ 6, 7, 8, 1, 2, 4, 5 ]
• ... 생략
• [ 7 ]

 

 

답)

 

function prince(n, k) {
  let anwser;
  let queue = Array.from({length : n}, (v, i) => i + 1)
  // queue = [1, 2, ..., n]
  
  while(queue.length) {
    if(queue.length === 1) answer = queue[0];
    else {
      for(let i = 0; i < k; i ++) {
        if(i !== k - 1) {
          queue.push(queue.shift());
        } else {
          queue.shift();
        }
      }
    }
  }
  
  return answer;
}