프로그래머스 JS 스택/큐 [6/6]

기능개발 Level 2 문제보기 (20)

요구사항에서 말해주는 그대로 따라서 차근차근 구현하면 됩니다.

그래서 그런지 다른 사람과 풀이가 99% 똑같았다.

 

풀이 순서

1. for문을 이용하여 프로세스 각각에 speeds 만큼 더해줍니다.

  progresses[i] += speeds[i]

 

2. 연달아 배포한 갯수를 카운트합니다. 

  let completedCount = 0

  - while을 이용하여 progresses[0]이 100이상이 아닐 때까지 배열에서 shift()로 제외하고 completedCount+1 하는 과정을 반복합니다.

  - 배포한 프로세스의 수를 결과 배열에 추가합니다.

 

function solution(progresses, speeds) {
  const result = [];

  // 개발진행 사항이 남아있다면
  while (progresses.length) {
    // 개발을 진행시킵니다.
    for (let i = 0; i < speeds.length; i++) {
      progresses[i] += speeds[i];
    }

    let completedCount = 0; // 배포 횟수
    
    // 개발 진행 후에 개발이 완료된 것이 있다면
    while (progresses[0] >= 100) {
    // 배포 횟수를 증가하고 플랜에서 제외합니다.
      completedCount++;
      progresses.shift();
      speeds.shift();
    }

    // 배포한 프로세스가 존재한다면
    if (completedCount !== 0) {
      result.push(completedCount); // 결과에 배포한 숫자를 추가합니다.
    }
  }

  return result;
}

---

올바른 괄호 Level 2 문제보기 (10)

풀이 포인트

괄호 모양이 ()가 되면 스택서 제외하고, 그렇지 않으면 추가합니다.

at(-1)과 arr[arr.length-1] 속도 비교 =>   arr[arr.length-1] 이 빠르다. 

array.at(-1) 일 때의 속도

array[array.length-1] 일 때의 속도

function solution(s) {
  const stack = [];

  for (let i = 0; i < s.length; i++) {
    if (stack.at(-1) === "(" && s[i] === ")") { // 괄호가 "()" 모양이라면 stack에서 제외하고
      stack.pop();
    } else { // 아니라면 stack에 추가합니다.
      stack.push(s[i]); 
    }
  }
  return stack.length === 0;
}

---

프로세스 Level 2 문제 보기 (40)

풀이 포인트

- 우선순위가 가장 높은 숫자를 프로세스를 실행할 때마다 max를 Math.max() 메서드를 이용해서 찾아야 합니다.

- 해당 프로세스의 location을 위치가 변경될 때마다 추적해야 합니다.

 

풀이 순서

1. 제일 앞의 프로세스를 shift()로 꺼내고, max보다 작다면 다시 큐에 push() 합니다.

  - 제일 앞의 프로세스가 맨 뒤로 갔기 때문에 location을 -1 해주어야 합니다.

  - location이 0 이라면 추적중인 프로세스이기 때문에 location의 위치를 맨 뒤로 (Array.length - 1) 바꿉니다.

 

2. 우선순위가 높은 프로세스라면 실행합니다.

  - 실행횟수 +1

  - location이 0 이라면 추적중인 프로세스가 실행된 것이기 때문에 count를 반환하고 종료합니다.

  - 추적중인 프로세스가 아니라면 location을 -1 해주고 그 다음으로 우선순위가 높은 프로세스를 Math.max로 찾습니다.

 

const solution = (priorities, location) => {
  let max = Math.max(...priorities);
  let count = 0;

  while (priorities.length) {
    // 1. 큐에서 대기중인 프로세스 하나를 꺼냅니다.
    const check = priorities.shift(); // 프로세스 꺼내기

    // 2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
    if (check < max) {
      priorities.push(check); // 프로세스 다시 넣기
      location === 0 ? (location = priorities.length - 1) : location--; // 바뀐 위치 설정

      // 3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
    } else {
      count++; // 실행 횟수 증가

      // Return. 실행된 프로세스가 location의 프로세스라면 결과를 반환합니다.
      if (!location) return count;

      // 4. 그 다음으로 우선순위가 높은 프로세스를 찾습니다.
      location--; // 바뀐 위치 설정
      max = Math.max(...priorities); // 다음 우선순위 찾기
    }
  }
};

---

다리를 지나는 트럭 Level 2 문제 보기 (100)

풀이 포인트

- 트럭이 얼마만큼의 시간이 경과해야 다리를 건널 수 있는지 기록합니다. [ 7(트럭무게), 2(남은시간) ]

 

[ [ 10, 100 ] ]
[ [ 10, 99 ], [ 10, 100 ] ]
[ [ 10, 98 ], [ 10, 99 ], [ 10, 100 ] ]
[ [ 10, 97 ], [ 10, 98 ], [ 10, 99 ], [ 10, 100 ] ]
[ [ 10, 96 ], [ 10, 97 ], [ 10, 98 ], [ 10, 99 ], [ 10, 100 ] ]

...

[ [ 10, 1 ], [ 10, 2 ], [ 10, 3 ], [ 10, 4 ], [ 10, 5 ], [ 10, 6 ] ]
[ [ 10, 1 ], [ 10, 2 ], [ 10, 3 ], [ 10, 4 ], [ 10, 5 ] ]
[ [ 10, 1 ], [ 10, 2 ], [ 10, 3 ], [ 10, 4 ] ]
[ [ 10, 1 ], [ 10, 2 ], [ 10, 3 ] ]
[ [ 10, 1 ], [ 10, 2 ] ]
[ [ 10, 1 ] ]

 

이와 같이 다리 위의 트럭들이 건너기까지 남은 시간을 계속해서 1초씩 감소시켜주고, 0이라면 제외하면 됩니다.

 

풀이 순서

1. [트럭무게, 남은시간]을 기록할 onBridge 배열을 생성합니다.

 

2. 건널 트럭이 남지 않을 때까지 while문을 실행합니다.

 

3. while문의 매 시행마다 다리 위에 있는 트럭의 시간을 -1 합니다.

    for (let i = 0; i < onBridge.length; i++) {
      onBridge[i][1]--;
    }

 

4. 제일 앞의 트럭의 남은 시간이 0이라면 다 건넌 것입니다.

- 다리에서 제외하고, 다리의 하중도 트럭 무게만큼 빼줍니다.

    if (onBridge.length && !onBridge[0][1]) {
      currentWeight -= onBridge.shift()[0];
    }

 

5. 다리 하중이 버텨줄 때까지 트럭을 올려줍시다.

    if (currentWeight + trucks[trucks.length - 1] <= weight) { // 다리 하중이 그 다음 트럭 무게를 합친 무게보다 크다면
      const truckWeight = trucks.pop();
      onBridge.push([truckWeight, length]); // 다리 배열에 트럭정보 [7, 2] 추가
      currentWeight += truckWeight; // 다리 하중에서 트럭 무게만큼 더하기
    }

function solution(length, weight, trucks) {
  trucks.reverse(); // pop()이 shift()보다 성능이 좋기 때문에 출발할 트럭 배열을 뒤집습니다.

  let onBridge = []; // [트럭무게, 다리 건너기까지 남은 시간][]

  let currentWeight = 0; // 다리 하중
  let time = 0; // 경과 시간

  // 모든 트럭이 건널 때까지 진행합니다.
  while (trucks.length || onBridge.length) {
    time++;

    // 다리 위의 트럭들의 "다리 건너기까지 남은 시간"을 -1 해줍니다.
    for (let i = 0; i < onBridge.length; i++) {
      onBridge[i][1]--;
    }

    // 다리의 제일 앞에 있는 트럭이 다 건넜다면 다리 하중에서 제일 앞의 트럭 무게만큼 빼줍니다.
    if (onBridge.length && !onBridge[0][1]) {
      currentWeight -= onBridge.shift()[0];
    }

    // 다리에 올라갈 수 있으면 트럭 올라갑니다.
    if (currentWeight + trucks[trucks.length - 1] <= weight) {
      const truckWeight = trucks.pop(); // 출발한 트럭 무게
      onBridge.push([truckWeight, length]); // 다리 배열에 트럭 [7, 2] 추가
      currentWeight += truckWeight; // 다리 하중에서 트럭 무게만큼 더하기
    }
  }

  return time;
}

---

주식가격 (*)

arr[arr.length-1] 속도 빠름

 

arr.at(-1) 속도 느림

 

풀이 포인트

• 끝까지 가격이 떨어진지 아닌지는 배열을 모두 확인하기 전까지 결정되지 않음
  => (stack에 가격을 결정이 필요한 index를 쌓음)
  
  
• 중간에 가격이 떨어진게 결정되는 시점은 stack의 topIndex에 해당하는 가격이 비교 가격보다 클 때
  => prices[topIndex] > 비교가격
      ㄴ while로 값이 떨어진게 아닌 index를 만날 때까지 시간을 기록
          => result[topIndex] = index - topIndex
  
  
• 끝까지 확인 뒤에도 stack에 남아있는 숫자들은 계속 증가했음
  => (size - 자기 자리의 index - 1)로 결정

 

풀이

function solution(prices) {
  const size = prices.length;

  const result = Array(size).fill(0);

  const stack = [];
  prices.forEach((price, index) => {
    // 가격이 떨어졌다면 가격을 유지한 시간을 결정함
    while (stack.length && prices[stack[stack.length - 1]] > price) {
      const topIndex = stack.pop();
      result[topIndex] = index - topIndex; // 가격 유지 시간
    }
    stack.push(index);
  });

  // 끝까지 확인해도 stack에 남아 있는 수들은 계속 증가했음
  while (stack.length) {
    const topIndex = stack.pop();
    result[topIndex] = size - topIndex - 1; // (전체 크기) - (자기 자신의 index) - (최소 1초는 유지함)
  }
  return result;
}
solution([2, 1, 2, 1, 2, 1]);

 

---

뒤에 있는 큰 수 찾기 (10)

풀이 포인트

"배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까운 수를 뒷 큰수라 함"

stack에는 result에 할당할 index를 쌓는다.

뒷 큰수를 만나면 stack에서 index를 위에서부터 꺼낸다.

number[topIndex]가 뒷 큰수보다 작다면 result[topIndex]의 값을 뒷 큰수로 바꾼다

 

풀이 순서

자신:    numbers[ topIndex ] 
뒷 큰수: numbers[i]

 

[1,2,9,9,...,1,2,9,9]을 예시로

stack에는 index를 쌓아두다가,

ex)

[0,1,2,3,...] 이런 식으로 index가 쌓임

 

stack의 topIndex에 해당하는 수보다 큰 수를 만났을 때,

ex)

topIndex는 1 

number[ topIndex ]은 2 ( 자신 )

numbers[i]는 9 ( 뒷 큰수 )

 

더 이상 큰 수가 아닐 때까지 result에 값을 할당한다.

ex)

result[ topIndex ] = numbers[i] 

function solution(numbers) {
  const result = Array(numbers.length).fill(-1);
  const stack = [];

  for (let i = 0; i < numbers.length; i++) {
    // 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까운 수일 때.
    while (stack.length && numbers[stack.at(-1)] < numbers[i]) {
      const topIndex = stack.pop();
      result[topIndex] = numbers[i]; // result의 해당 index를 뒷 큰수로 바꾼다.
    }

    // result에 할당되지 않은 index를 stack에 추가
    stack.push(i);
  }
  return result;
}

solution([9, 1, 5, 3, 6, 2]);