[알고리즘/프로그래머스/고득점Kit] 스택/큐(JS)(같은 숫자는 싫어, 기능개발, 올바른 괄호, 프로세스, 다리를 지나는 트럭, 주식가격)

문제: 같은 숫자는 싫어

---

https://school.programmers.co.kr/learn/courses/30/lessons/12906?language=javascript 

프로그래머스

 

풀이

---

function solution(arr) {
    // 이전 숫자랑 같으면 continue, 아니면 answer에 push
    const answer = [arr[0]]
    for (let i=1;i<arr.length;i++) {
        if (arr[i] === arr[i-1]) continue
        answer.push(arr[i])
    }
    return answer
}

 

---

문제: 기능개발

---

https://school.programmers.co.kr/learn/courses/30/lessons/42586?language=javascript 

프로그래머스

 

풀이

---

function solution(progresses, speeds) {
   const leftDays = progresses.map((p, i) => Math.ceil((100 - p) / speeds[i]))
   const answer = []
   let maxVal = leftDays[0]
   let cnt = 0
   
   for (let day of leftDays) {
       if (maxVal < day) {
           maxVal = day
           answer.push(cnt)
           cnt = 1 // 현재 값 세기
       } else {
           // maxVal보다 작거나 같으면 같이 배포 가능
           cnt += 1
       }
   }
    answer.push(cnt)
    
    return answer
}

 

---

 

문제: 올바른 괄호

---

https://school.programmers.co.kr/learn/courses/30/lessons/12909#

프로그래머스

 

풀이

---

function solution(s){
    let sum = 0
    for (let ch of s) {
        sum += ch === '(' ? 1 : -1
        if (sum < 0) return false
    }
    
    return sum === 0
}

이 문제는 이상하게 같은 코드도 효율성이 통과했다 안 했다 했다. 처음에는 s[0] === ')'이면 return false하는 코드를 추가했더니 통과가 됐지만 같은 코드를 다시 제출했더니 또 한 테케가 실패가 떴다. 우선 위의 코드로 통과가 됐었긴 하다. 

 

 

---

문제: 프로세스 

---

https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=javascript 

프로그래머스

 

풀이

---

function solution(priorities, location) {
  const arr = priorities.map((p, idx) => [idx, p]) // [인덱스, 우선순위]
  let cnt = 0
  
  while (true) {
      const max = Math.max(...arr.map(([idx, p]) => p)) // 우선순위 최댓값
      const [idx, p] = arr.shift()
      
      if (p < max) arr.push([idx, p]) 
      else {
      	// 우선순위가 가장 높은 경우
        cnt += 1
        if (location === idx) return cnt
      }
  }
}

 

---

 

문제: 다리를 지나는 트럭 

---

https://school.programmers.co.kr/learn/courses/30/lessons/42583?language=javascript 

프로그래머스

 

풀이

---

function solution(bridge_length, weight, truck_weights) {
    /** 
    * bridge_length길이의 배열 bridge 만들기 
    * 시간이 흐를때마다 
        - shift() -> 값이 0이 아니면 passed에 push -> 만약 passed.length === truck_weights.length와 같으면 return time 
        - 만약 truck이 있고, sum + 다음 트럭 무게 <= weight : 다음 트럭 push, 아니면 0 push 
        - 빼고 넣고 할 때 weightSum에 무게 빼고 더하기 
    */
    const bridge = Array(bridge_length).fill(0)
    const passed = []
    const trucksLen = truck_weights.length
    let time = 0
    let weightSum = 0 
    
    while (true) {
        // 앞을 빼고 
        time += 1
        const passedTruck = bridge.shift()
        weightSum -= passedTruck
        if (passedTruck > 0) passed.push(passedTruck)
        if (passed.length === trucksLen) return time
        
        // 뒤에 넣기 
        if (truck_weights.length && weightSum + truck_weights[0] <= weight) {
            weightSum += truck_weights[0]
            bridge.push(truck_weights.shift())
        } else bridge.push(0)        
    }
    

}

이런 문제는 시간을 증가시키는 위치가 헷갈린다. 이럴 때는 시간을 return하는 시점을 보면 판단할 수 있다.

먼저 코드 상단을 살펴보면, bridge의 맨 앞 요소가 0이 아니면 지나간 트럭 배열인 passed에 push 해준다.

그 후 passed 길이가 원래 트럭 개수와 같으면 트럭이 모두 도착했다는 의미이므로 시간을 return 한다.

 

마지막 트럭이 도착할 때 위의 과정을 거쳐서 passed의 길이를 확인한다. 이때 마지막 트럭은 뒤에 넣는 작업을 하기 전에 끝나버리므로(return) 미리 time을 더해줘야 한다. 만약 time을 while문의 끝에서 더해주는 로직이라면  마지막 트럭이 도착했을 때 시간이 흐르지 않게 된다..!

 

문제: 주식가격

---

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

 

풀이

---

function solution(prices) {
    const len = prices.length
    const answer = []
    // 가격이 떨어지기 전까지 개수를 구하는 것. 
    // 2중 for문 돌면서 뒤에 크거나 같은 값 개수를 세다가 크면 break 
    // 1초가 흐르고 같은지를 확인
    for (let i=0;i<len;i++) {
        let cnt = 0
        for (let j=i+1;j<len;j++) {
            cnt += 1
            if (prices[i] <= prices[j]) continue
            else break
        }
        answer.push(cnt)
    }
    return answer
}

처음에는 그냥 2중 for문을 돌면서 현재 값(prices[i])보다 크거나 같으면 cnt를 증가시키면서 개수를 셌다.

하지만 문제를 다시 보니 가격이 떨어지지 않은 기간은 몇 초인지를 묻고 있어서 다시 생각해봤다. 

특히 예제 [1, 2, 3, 2, 3]의 경우, 3초 시점의 ₩3이 1초 뒤에 가격이 떨어진다는 점에서 단순히 현재 값 이후와 비교한 개수를 세면 안 된다는 것을 알 수 있었다. 

시간은 항상 1초씩 흐르고, 그 이후에 크거나 같으면 계속 세고, 아니면 break를 걸어 멈춘다. 이렇게 하면 시간이 항상 1초씩 흐르고 판단할 수 있다.