스택
const fs = require('fs')
const getInput = (filePath) => {
return fs
.readFileSync(filePath)
.toString()
.split(/\n/)
.map((elem) => (elem.split(" ")));
}
const input = getInput('./src/examples.txt'); // 제출시 여기 '/dev/stdin' 으로 변경
let stack = [];
let answer = [];
input.forEach(elem => {
const command = elem[0];
const value = Number(elem[1]);
switch (command) {
case 'push':
stack.push(value);
break;
case 'pop':
stack.length ? answer.push(stack.pop()) : answer.push(-1);
break;
case 'size':
answer.push(stack.length);
break;
case 'empty':
(stack.length) ? answer.push(0) : answer.push(1);
break;
case 'top':
const lastIndex = stack.length - 1;
stack[lastIndex] ? answer.push(stack[lastIndex]) : answer.push(-1);
break;
default:
break;
}
}
)
console.log(answer.join("\n"));이거 구현은 엄청 쉬웠는데, 시간제한이 엄청 빡빡해서 그거 해결하느라 생각보다 시간을 엄청 잡아먹었다.
그래서인지 난이도에 비해 정답률도 37.255% 밖에 안되는데, 시간제한때문에 대충 구현한거 확인하고 넘어간 사람들이 많아서 그런듯.
아무튼 폭풍구글링과 시도 끝에 찾아낸건
console.log() 자체가 출력하는 데 시간이 오래걸려서, 가능하면 한번만 사용하는게 좋다고 한다.
그래서 정답을 모두 모아놓는 배열을 하나 만들고 (나는 answer 배열 선언함), 거기에다 정답을 모은 뒤에 한꺼번에 join('\n') 해서 출력하니까 바로 성공했다~!
그리고 처음에는 if문으로 쓰니까 너무 더러워가지고 조건이 여러개일 경우에는 switch 문이 나은 것 같아서 switch문으로 썼는데
코드가 가독성 있게 잘 읽혀서 기분이 좋다.
그리고 if문이랑 switch문이랑 차이점이 궁금해서 구글링해보니 컴퓨터 구조 관련해서 처리하는 로직이 다르다고 한다.
if문 같은 경우에는 브랜치로 판단하는데
switch문은 jump table로 처리한다고 한다. (어렴풋이 이해했는데ㅡ 내일 더 찾아보고 포스팅해봐야지)
사실 속도차이 관련해서는 신경 쓸 것이 아니라 의미 중심으로 선택해서 사용하면 된다고 한다.
조건이 3개 이상일 경우에는, switch 문을 쓰는게 더 나은 경우가 많다고 한다.
또 코드를 짤 때 실수한 것이 있는데, 선언한 case문 외의 경우의 수가 있다면 default 선언을 해줘야 오류가 안난다고 한다.
쇠막대기
const fs = require('fs');
const { type } = require('os');
const getInput = (filePath) => {
return fs
.readFileSync(filePath)
.toString()
.split(/\n/)
.map((elem) => (elem.split(" ")));
}
const input = getInput('/dev/stdin');
const str = input[0][0]; // ()(((()())(())()))(())
let stack = [];
const strToArray = [...str];
const answer = strToArray.reduce((acc, cur, curIndex) => {
const followingElem = strToArray[curIndex - 1];
if (cur === '(') {
stack.push(cur);
} else if (followingElem === '(' && cur === ')') {
stack.pop();
return acc + stack.length; // 스택의 길이만큼 acc에 저장
} else if (followingElem === ')' && cur === ')') {
stack.pop();
return acc + 1;
}
return acc;
}, 0);
console.log(answer);이게 스택 자료구조형이라는 걸 이해하는 것에 엄청난 시간이 걸렸다.
스택이 FILO로 그릇 쌓아두는 개념이지~ 완전 쉽네!로 막연히 이해하고 있었는데
실제로 뭔가를 구현할 때 스택이라는 자료구조를 활용해서 문제를 응용해서 풀이할 수 있다는 것 자체를
이제서야 깨달은 것 같다.
파이프 시작과 끝 보면 stack push pop 구조 FILO 구조!
(→ push)→ pop
a.(): stack 수 만큼 증가
b.)): +1 증가
그리고... 구현은 직접 내가 해냈는데 너무너무 기분이 좋았다! 내가 직접 짠 코드라니!! 말도 안돼
으하하 구현 쉬운거래두 이제 진짜 하나하나 의미 있게 다가와서 좋다.
예전엔 for문도 몰라서 빌빌거렸는데 ~ ~ 지금은 머 리듀스 하나정도는 쓱싹 ~ 아이고 많이도 컸다 ~
크게 만들기
const fs = require('fs');
const { type } = require('os');
const getInput = (filePath) => {
return fs
.readFileSync(filePath)
.toString()
.split(/\n/)
.map((elem) => (elem.split(" ")));
}
const input = getInput('/dev/stdin'); // 제출시 여기 '/dev/stdin' 으로 변경
let [n, k] = input[0]; // [4, 2]
const number = input[1][0]; // '1924'
const numberArray = [...number].map(x => Number(x));
let stack = [];
for (let i = 0; i < n; i++) {
while (stack[stack.length - 1] < numberArray[i] && stack.length > 0 && k > 0) {
stack.pop();
k--;
}
stack.push(numberArray[i]); // 1 9 2 4
}
const answer = stack.join('').substring(0, stack.length - k);
console.log(answer);
이건 전에 풀었던 문제라서 금방 풀렸다. 내 실력아님 대신 이번엔 솔루션안보고 풀긴함
대충.. push로 들어오는 숫자들이 스택 마지막에 있는 숫자와 비교했을 때 더 크다면
짜부시켜서 팝!하고 터뜨린다고 연상하면 된다.
주의해야할 것이 k= 4, 숫자 54321일 경우에 반례를 조심해야 하는데,
substring 으로 처리하면 된다.
에디터
아직 구상 중... 내생각엔 leftStack, rightStack으로 이리저리 왔다리갔다리 하면 될 것 같긴 한데
pop할때 undefined 값이 나오면 어떡하나 if 문으로 쇼부봐야하나 지금 좀 생각할 게 많다
어렵다~~ 집가서 마저 생각했다가 내일 풀 거임!
++ 다음날 아침에 풀었다!
const fs = require('fs');
const { type } = require('os');
const getInput = (filePath) => {
return fs
.readFileSync(filePath)
.toString()
.split(/\n/)
.map((elem) => (elem.split(" ")));
}
const input = getInput('./src/examples.txt'); // 제출시 여기 '/dev/stdin' 으로 변경
const commandLength = Number(input[1]);
const commands = input.slice(2, input.length);
const string = [...input[0][0]];
// 풀이
let leftStack = string.slice(0, string.length);
let rightStack = string.slice(string.length);
commands.forEach((elem) => {
switch(elem[0]) {
case 'P':
leftStack.push(elem[1]);
break;
case 'L':
const leftPop = leftStack.pop();
if (leftPop) {
rightStack.push(leftPop);
}
break;
case 'D':
const rightpop = rightStack.pop();
if (rightpop) {
leftStack.push(rightpop);
};
break; // break 문 안써서 오류남..
case 'B':
leftStack.pop();
break;
}
// console.log('leftStack', leftStack, 'rightStack', rightStack);
})
const reversedRightStack = rightStack.reverse();
const answer = leftStack.concat(reversedRightStack).join('');
console.log('answer', answer);처음에는 값은 잘 뜨는데 제출하니까 시간초과 떠서 뭐지 했는데
‘L’에서 splice를 매번 실행해서! O(n) 연산을 계속 반복해서임!
마지막에 reverse로 출력하니 통과!
한번만 연산해서 바꿔주면 됨
백준이 이런 부분 까다롭게 체크해줘서 오히려 좋아.
자료구조랑 알고리즘이랑 같이 병행하니까 너무 재밌다..
솔루션을 이미 한번 보고 다시 푼 것도 있고 혹은 접근법에 대해서 이해하는 것도 힘들었는데
이게 이해를 한다 자체가 뽕이 차서 흐어억!! 거리니까 옆에서 오빠야가 미친놈 보듯이 했다.
(근데 솔직히 자기도 혼자 문제 풀다가 그랬을듯ㅋ )
아무튼 너무너무 재밌다!!
이거 어떻게 풀지 내가 할 수 있을까가 아니라
몬가 근자감만 가득차서 이자식 내가 어떻게 조져주지? 하는 생각으로 가득차있다.
막 백준 처음에는 세팅도 어렵고, 브론즈...도 내가 풀 수 있을까 ㄷ ㄷ 했음
물론 !! 너무 어려워서 1시간 이상 접근법도 생각이 안나면 구글링하고 솔루션을 이해하는 것 조차 힘든 문제도 있지만
그 과정도 너무 재밌다.
<< 지금의 나 (이 녀석 죽이 되든 밥이되든 누가 이기나 보자)
처음 시작할 때 나 (할 수 잇을가..난 바본가바)
수학 문제 푸는 쾌감. 크아..
고뒹때 수학 좋아했었는데 딱 그 느낌이다. (잘하진 못해서 짝사랑임)
내일 공부는 큐 자료구조 관련해서 알고리즘 열심히 풀어야지!
