오랜만에 프로그래머스 알고리즘 문제 풀기!
날짜보니 ✨JS 코테 첫 입문한 날✨로부터 2달쯤 지난 것 같다.
초반에 2주 정도 열심히 풀다가 어느순간 놓아버린 알고리즘 ㅋㅋㅋ
C++로는 백준 가끔가다 한번씩 풀었었는데 자바스크립트 코테 문제 풀이는 어느덧 2달이나 지나다니..
2달 내내 코테 연습했으면 금방 풀었으려나.
아무튼 여기서 감 더 잃기 전에 한번씩 풀어야 될 것 같아서
새로 생긴지 얼마 안되어 보이는햄버거 만들기문제를 풀어보기로 했다.
오늘도 여전한 시간초과
처음 문제를 봤을 때 stack으로 풀려고 했는데 예외처리가 제대로 안 되었는지 몇 개의 TC에서 실패하거나 시간초과 뜨길래 바로 우회해서 정규 표현식으로 다시 작성했다.
근데 정규 표현식으로 하니 시간 초과가 난다.
하나씩 찾아서 없애고 replace 시키는 방법을 선택했는데 시간 초과가 떠서 물거품이 됐다. ㅋㅋㅋ
정규 표현식이랑 친해지고 싶었는데 아무래도 힘들 것 같다.
/* 시간초과 코드 */
function solution(ingredient) {
let reg = /1231/;
let cnt = 0;
let stringIngredient = ingredient.join('');
let findIdx = stringIngredient.search(reg);
while(findIdx !== -1){
stringIngredient = stringIngredient.replace(reg, '');
findIdx = stringIngredient.search(reg);
cnt++;
}
return cnt;
}아 통과 시켜줘..........ㅜㅜㅜ
그래서 다른 방법으로 처음부터 모든 1231을 다 찾아서 없앤 후,
다시 또 찾는 것을 반복시켰는데 그렇게 하면 정확한 답이 도출되지 않았다.
왜 그럴까 TC를 찾아보니 문제에서 요구하는 것은 stack마냥 pop! pop! 하면서 앞에서부터 지워나가야 되는데 [1, 2, 1, 2, 3, 1, 3, 1, 2, 3, 1, 2, 3, 1] 와 같은 TC를 만났을 때 처음부터 [1, 2, 1, 2, 3, 1, 3, 1, 2, 3, 1, 2, 3, 1] 을 지워버리게 되는데 더 이상 1231이 만들어지지 않아서 답이 2가 되버린다.
실제로는 [1, 2, 1, 2, 3, 1, 3, 1, 2, 3, 1, 2, 3, 1] 을 먼저 지우고 [1, 2, 3, 1, 2, 3, 1, 2, 3, 1] 을 지운 후 [2, 3, 1, 2, 3, 1]이 지워져서 결과값 3이 되어야 하기 때문이다.
정규 표현식 좀 공부할겸 써보려고 했는데
정규 표현식으로 이렇게 하나씩 찾아서 지우면 시간초과가 나기 때문에
다시 처음에 시도했던 스택 풀이로 돌아가기로 했다.
/* 통과 코드 */
function solution(ingredient) {
const stk = [];
let cnt = 0;
ingredient.forEach((ing, idx)=>{
stk.push(ing);
if(stk.length >= 4){
const find = stk.slice(-4).join('');
if(find === '1231'){
stk.pop();
stk.pop();
stk.pop();
stk.pop();
cnt++;
}
}
})
return cnt;
}스택으로 어떻게 풀어야 할까,, 하면서 엄청나게 어렵게 고민했던 것 같다.
1 > 2 > 3 > 1 순서대로 나온걸 카운트 해야지~ 하다가 무한의 인피니트 굴레에 갇혔었다.
아니 이걸 어떻게 짜야하지? 하면서 최소 3시간은 저 로직만 고민한 것 같다.
정말 여러가지 코드 다 짜봤는데 TC를 전부 통과할 풀이가 안 나왔다.
결국 모조리 다 push 시켜버리고 배열의 길이가 4가 됐을 때
끝에서 4개 잘라서 1231이면 pop을 4번 시키면 되는 아주 단순한 풀이로 해결할 수 있었다.
처음에 굉장히 오래 고민하다가 복잡의 늪에 빠져서 아, 잠시만 이 문제가 뭘 요구했었지? 하고 머리가 초기화 됐었는데 ㅋㅋㅋ
극초반에는 splice로 푼다고 덤볐다가 또 시간초과 맞고 reg로 갈아탄거였는데 ㅋㅋㅋ
reg에서 또 시간초과 맞고 다시 스택으로.. 왔는데.. 아..........
왜 1레벨인지 알 것 같으면서도 이해 할 수 없었다.......
오늘의 교훈 : 일단 단순 무식하게 풀리는지 시도해보자.
