스택/큐
(Lv. 1) 같은 숫자는 싫어
https://school.programmers.co.kr/learn/courses/30/lessons/12906
간단한 문제인데 약간의 트릭이 존재하였다.
그것은 바로 중간에 다른 애가 나온 후에는 중복된 애가 들어가도 된다는 것
그렇기에 반복문에서 다음 애를 넣어주고 처음에는 우리가 주어진 배열의 0번째 인덱스를 넣어서 값을 설정하는 것이 좋다.
그리고 역시나 문제를 잘 읽어야할 것 같은 게, 배열의 크기가 0이 될 수 있다는 것을 잊고 있어서 테스트 한 가지를 통과하지 못했었다.
에전 나의 풀이
function solution(arr)
{
let stack = [];
for (i=0; i<arr.length; i++) {
if (arr[i] === arr[i+1]) {
stack.push(arr[i])
stack.pop()
} else {
stack.push(arr[i])
}
}
return stack
}stack/queue를 정확하게 적용하여서 같을 땐 넣어줬다가 바로 뺴주고
다를 땐 그냥 넣어주는 식으로해서 stack을 구성하였다
한창 대학교 4학년 일 때에 내가 더 잘하는듯..
(Lv. 2) 기능 개발
https://school.programmers.co.kr/learn/courses/30/lessons/42586
오랜만에 본토 Queue와 Stack에 대한 개념을 다시 한번 일꺠어 주는 문제
문제를 이해하는데도 시간이 걸리지만 문제에 대한 자료구조와 로직을 선택하는데도 까다롭게 걸련던 문제인 거 같다
많이 헷갈렸던 부분은, 앞에서부터 빼니까 Queue를 사용하는 것 맞음 하지만 어떻게 비교를 하느냐 였음 -> 여기에서 나왔던 괴리가.. 반복문에서는 배열의 조작을 최대한 지양하려했던 문제
function solution(progresses, speeds) {
// 각 인덱스별로 100이 될 때까지 더해주다가 100이 되면 둘다 뺴기 (shift)
const ans = new Array(progresses.length).fill(0);
let plusCnt = 0;
progresses.map( (v, i) => {
while (progresses[i] < 100) {
progresses[i] += speeds[i]
plusCnt += 1
}
ans[i] = plusCnt;
plusCnt = 0;
})
const answer = [];
// 작업 일수들을 순회함
while (ans.length > 0) {
const current = ans.shift(); // 첫번째 작업이 걸리는 시간
let count = 1;
// 두번째 작업 (ans[0])이 첫번째 작업보다 빨리 끝난다면
// 두번째 작업도 큐에서 제거 후 count ++
while (ans.length > 0 && ans[0] <= current) {
ans.shift(); // 큐에서 제거
count++;
}
// 비교대상보다 더 큰 작업이 나왔을 땐 while 타지 않고 count 삽입
answer.push(count);
}
return answer
}
다른사람의 풀이
function solution(progresses, speeds) {
var answer = [];
while(speeds.length > 0) {
// 개발
for(let i in speeds) {
if(progresses[i] < 100) {
progresses[i] += speeds[i];
}
}
// 배포
let deploy_count = 0;
while(progresses[0] >= 100) {
progresses.shift();
speeds.shift();
deploy_count++;
}
if(deploy_count > 0) {
answer.push(deploy_count);
}
}
return answer;
}
(Lv. 2) 프로세스
https://school.programmers.co.kr/learn/courses/30/lessons/42587
진심 푸는데 하루는 걸린 문제.. 오랜만에 해서 그런지 반복문과 메서드 자체에 모순이 존재했던 것 같다
느낀점으로는 우선 '프로세스의 실행순서'를 구하는 것이 목표라는 것
나는 이 프로세스의 실행순서 없이 오로지 배열의 변화에만 집중해서 문제였던 것 같다.
간단히 생각할수록 간단한 문제
-
for보다는 while을 써서 나머지 콜백큐에 쌓인 작업들이 0이 될 떄까지 한다는 발상이 중요한 것 같음 (문제 내에서도 프로세스라고 주어졌으니까)
-
shilt를 하게 되면 배열이 변경되고 프로세스가 실행시엔 배열에 push를 하지 않으므로 배열이 변경되게 내비두는 것
-
우리는 결론적으로 해당 location에 존재하는 애의 실행 순서가 알고 싶었던 것이기 때문에 count란 변수를 설정해야한다는 것
function solution(priorities, location) {
// 실행 순서를 추적하는 변수
let count = 0;
// 큐가 빌 때까지 반복
while (priorities.length > 0) {
// 현재 큐의 첫 번째 프로세스를 꺼냄
const current = priorities.shift();
// 현재 프로세스보다 높은 우선순위가 큐에 존재하는지 확인
if (priorities.some(priority => priority > current)) {
// 우선순위가 더 높은 프로세스가 있으면 현재 프로세스를 뒤로 보냄
priorities.push(current);
// location 값도 뒤로 이동
location = location === 0 ? priorities.length - 1 : location - 1;
} else {
// 작거나 같아 실행 가능한 경우
count++;
// location이 0일 때고 자기보다 작거나 같은 애라면 그떄의 count를 반환
if (location === 0) {
// 목표 프로세스가 실행되었으면 실행 순서를 반환
return count;
}
location--; // 다음 프로세스를 추적하기 위해 감소
}
}
}다른 사람의 풀이
약간 신기하게도 인덱스와 priority를 활용하여 location을 깔끔하게 푸셨다
게다가 shift를 통하여 가장 처음 인덱스를 비워놓고
some을 활용하여 나머지 배열과의 값을 비교한 뒤에
존재한다면 arr에 추가하여 뒤로 보내는 작업을 하고
그렇지 않으면 정답 배열인 queue에 값을 넣어서 값을 유추
가장 핵심인 마지막으로 만들어진 정답배열인 queue의 인덱스와 location의 비교를 한 후에 +1을 하여 최종적인 실행순서를 return함
function solution(priorities, location) {
var arr = priorities.map((priority, index) => {
return {
index: index, priority: priority
};
});
var queue = [];
while(arr.length > 0) {
var firstEle = arr.shift();
var hasHighPriority = arr.some(ele => ele.priority > firstEle.priority);
if (hasHighPriority) {
arr.push(firstEle);
} else {
queue.push(firstEle);
}
}
return queue.findIndex(queueEle => queueEle.index === location) + 1;
}
(Lv. 2) 올바른 괄호
https://school.programmers.co.kr/learn/courses/30/lessons/12909
아직까지는 23년도에 푼 기억이 남아있던 문제였다.
하지만 처음에 보자마자 든 생각은 바보 같이, 그냥 처음과 끝만 맞으면 정답인 거 아닌가? 라는 멍청이 같은 생각을 했던 것 같다
'(((( )))'
이런식이라면 올바른 괄호열기닫기가 아니기 때문에
예전에 풀었던 대로 스택에 첫값이 올바를 때를 넣어두고 그 다음부터 순회하면서 스택 안에 들어있는 값들이 짝을 맞춰 지워지는지를 확인했어야 하는 문제..
그렇기에 옛날 답을 떠올리면서 한번 풀어보았다.
function solution(s){
// 배열로 변경
s = s.split('');
if (s[0] == ')' || s[s.length-1] == '(') return false
let stack = [s[0]];
for(let i=1; i<s.length; i++) {
if (s[i] == ')' ) {
stack.pop()
} else {
stack.push(s[i])
}
}
return stack.length ? false : true
}다른 사람들의 풀이
다른 분들은 문자를 비교할 자체에 관심을 둔 게 아니라 더하기로 바꿔서 하는 것이 인상 깊었다.
function solution(s){
let cum = 0
for (let paren of s) {
cum += paren === '('? 1: -1
if(cum < 0) {
return false
}
}
return cum === 0? true: false;
}
function is_pair(s){
var result = 0;
if(s[0] === ')') return false;
for(var i = 0; i < s.length; i++){
if(result < 0) return false;
if(s[i] === '(') result++;
if(s[i] === ')') result--;
}
return !result;
}(Lv. 2) 다리를 지나는 트럭
https://school.programmers.co.kr/learn/courses/30/lessons/42583
자그마치 고민하고 푸는데 이틀이나 걸린 문제.. 심지어 그마저도 내가 온전히 풀지 못했다고 해도 과언이 아닐 정도로 조금은 부끄러운 문제이다.
내가 생각하기에 내가 이 풀지 못했던 이유는 다리를 건너는데 남은 시간에만 너무 집중을 해서 더이상 생각이 뻗어나가지 못했던 것 같다
그리고 일차원 배열만을 고집하는 특성 때문에 이차원 배열이라는 큰 장점을 두고도 생각하지 못했다
조금 더 프로세스적으로 다가가자면 여러 함수를 구현한다고 생각하면 편했을 것 같은 문제
- 상태를 보고
- 트럭을 제거하던가
- 트럭을 추가하던가
하면 되고 그리고 무엇보다 현재 무게를 재는데 있어서 일차원 배열에 꽂혀선 reduce만 반복하다가 정수로서 활용하면 되는 이점을 크게 잊고 있었던 것 같음
count는 매 순회마다 반복되어야만 하고, count가 증가함과 동시에 다리를 건넌 트럭을 제거해줘서 count의 값을 온전히 유지하는 게 가장 중요한 것 같음
조금 더 컴퓨터적으로 생각하는 게 필요할 것 같음.
function solution(bridge_length, weight, truck_weights) {
let count = 0; // 총 경과 시간
let currentWeight = 0; // 현재 다리 위의 총 무게
let passingTruck = []; // 다리 위 트럭의 [무게, 남은 이동 시간] 저장
while (passingTruck.length > 0 || truck_weights.length > 0) {
count++;
// 1. 다리를 건넌 트럭 제거
// 다리를 건너는 트럭이 존재하고, 트럭이 건너는 때가 count와 같을 때을 때 제거
if (passingTruck.length > 0 && passingTruck[0][1] === count) {
const finishedTruck = passingTruck.shift(); // 다리에서 트럭 제거
currentWeight -= finishedTruck[0]; // 다리 위 무게 갱신
}
// 2. 새로운 트럭 추가 가능 여부 확인
// 대기하는 트럭이 존재하고, 현재 무게 + 트럭의 값이 weight보다 작을 때
if (truck_weights.length > 0 && currentWeight + truck_weights[0] <= weight) {
const nextTruck = truck_weights.shift(); // 대기 트럭에서 하나 꺼냄
// ★ 여기에서 가장 중요, 현재 카운트 + 다리의 길이를 더해 이 트럭이 내릴 때를 지정함 ★
passingTruck.push([nextTruck, count + bridge_length]); // 트럭 추가 및 완료 시간 저장
currentWeight += nextTruck; // 다리 위 총 무게 갱신
}
}
return count; // 모든 트럭이 다리를 건넌 시간 반환
}
다른 사람의 풀이
참고할 만한 게 없음
위에 복습!
(Lv.2) 주식가격
이해가 되지 않아 결국 손코딩까지 풀게한 문제..
stack을 활용해서 떨어지지 않은 값들을 저장하고 떨어졌다면 stack의 pop을 통해 떨어진 시간을 계산하면 되는 것으로 이해헀다.
하지만 잘 그려지지 않았기에 더 헷갈렸음
이제보면, stack / queue는 약간 함수를 만들어서 넣을지 뺄지를 고르면 되는 문제들이 많은 것 같다 복습하면서 더 챙겨봐야할 것 같음
function solution(prices) {
// 주식이 열린 기간
const days = prices.length;
// 떨어지기까지 걸린 시간을 저장
const answer = Array(days).fill(0);
// 현재까지 떨어지지 않은 인덱스를 추적
const stack = [];
for (let i = 0; i < days; i++) {
// 스택에 저장된 인덱스를 통해 다음 prices값과 비교하여 다음날 "하락"했다면
while (stack.length > 0 && prices[stack[stack.length - 1]] > prices[i]) {
// 스택에 저장된 인덱스를 꺼내와
const temp = stack.pop();
// answer (0으로 가득찬 배열)의 값을 바꾸어줌
// -> 떨어지기까지 며칠이 걸렸는지
// ex. i=3 / temp=2 -> answer[2] = 3 - 2 = 1
answer[temp] = i - temp; // 떨어지기까지 걸린 시간 계산
}
// stack에는 반복문의 인덱스를 저장
stack.push(i);
}
// 최종적으로 스택에 남아있는 인덱스들을 통해
while (stack.length > 0) {
// answer배열의 값을 바꾸어줌
const temp = stack.pop();
// answer[4] = 5 - 4 - 1 = 0
answer[temp] = days - temp - 1; // 끝까지 남은 시간 계산
}
return answer;
}