백준 js 1406번

요새 졸업작품 개발과 교내 UMC 워크북 미션 해결, 그리고 Open API를 활용한 개인프로젝트를 병행하느라 코딩테스트 문제풀이를 많이 못한것 같다. 분발 해야겠다..

다시 감을 살릴 겸 알고리즘의 기본인 스택을 문제 주제로 정하였고 내가 해결한 문제는 다음과 같다.

 

<백준 문제>

https://www.acmicpc.net/problem/1406

 

 

-> 이 문제는 시간제한이 0.3초라는 점이 포인트

-> 즉 stack의 pop, push를 이용하여 O(1)의 시간복잡도로 구현해야 한다.

 

 

<문제 핵심>

✨ 다른 블로그의 내용들을 참고하였는데 두 개의 스택을 이용하는 건 생각도 못했다.

(코드의 가독성이 올라갔음)

 

1. 커서를 경계로 하는 두 개의 스택을 이용한다. (ex. lStack, rStack)

2. 입력된 글자에 따라서 rStack과 lStack의 pop, push을 이용한다.

-> stack 알고리즘 이기 때문에 shift와 unshift는 사용 금지!

 

<풀이방법 및 순서도>

 

1. 입력받은 값의 첫번째 요소를 가져오고 split("")을 통해 lStack 배열을 만든다.

2. 다음 요소를 가져오고 숫자 처리 해준다. (ex. Number(input.shift())  )

3. rStack 배열을 선언 및 초기화 해준다.

4. 2번에서 구한 숫자만큼 반복문을 돌리고 입력된 글자에 따른 조건문을 구현한다.

5. lStack을 문자열로 바꿔주고 answer에 대입한다. ( join("")을 통해 배열을 문자열로 바꿔주기 )

6. rStack의 배열을 역으로 바꿔주고 문자열로 바꿔준 다음 lStack에 더 해준다.

✅rStack에는 커서를 기준으로 lStack의 반대로 스택이 쌓이기 때문에 기존 순서대로 바꿔줘야한다.

ex.  [왼쪽 스택]  |  [오른쪽 스택]

                  dmi  |  h

                  dm   |  ih ❗커서가 오른쪽으로 한칸 이동

7. answer를 출력한다.

 

<최종 코드>

 

const input = require("fs").readFileSync(0, "utf-8").toString().split("\n");

let lStack = input.shift().split("");

let number = Number(input.shift());

let rStack = [];

for (let i = 0; i < number; i++) {

  const [cmd, value] = input[i].split(" ");

  if (cmd === "L" && lStack.length) rStack.push(lStack.pop());

  else if (cmd === "D" && rStack.length) lStack.push(rStack.pop());

  else if (cmd === "B" && lStack.length) lStack.pop();

  else if (cmd === "P") lStack.push(value);

}

let answer = lStack.join("");

answer += rStack.reverse().join("");

console.log(answer);