Programmers_1. 스택/큐

기능개발

조건

각 배포 시점마다 몇 개의 기능이 배포 가능한지를 배열 형태로 리턴해야 한다.

• progresses: Array, 배포 순서별 작업의 진도
• speeds: Array, 각 작업의 개발 속도
• 뒤에 있는 기능은 먼저 완료되었더라도 앞에 있는 기능이 배포될 때 함께 배포
• 각 기능은 진도가 100%일 때 서비스에 반영

풀이

이 문제는 일단 두 케이스로 나누어 볼 수 있다.

1. 작업별 소요일을 담은 배열을 구성한다. (.map / Math.ceil())
2. 만든 배열을 이용해 배포 가능한 기능의 수를 구한다. (maxDay 변수)

• 첫 기능만 제일 먼저 완성되면 첫 기능만 배포한다.
• 첫 기능보다 일찍 완성된 다른 기능이 있다면 첫 기능의 배포와 함께 배포한다.
  이를 두 번째(혹은 세 번째) 기능에서 똑같이 반복하며 확인한다.

이를 그림으로 보면 다음과 같다.

첫 번째 기능(maxDay)만 완성되어 먼저 배포, 다음 기능은 새로운 maxDay가 된다.

첫 번째 기능(maxDay)보다 두 번째가 먼저 완성되어 첫 기능의 완성 시점에 두 기능은 함께 배포, 마지막 기능은 새로운 maxDay가 된다.

function solution(progresses, speeds) {
  let answer = [0];
  let days = progresses.map((progress, index) => Math.ceil((100 - progress) / speeds[index]));
  // 작업별 소요일을 담은 days 배열 구성
  let maxDay = days[0];
  // 첫 번째 작업 소요일 -> maxDay (최장 소요)

  for(let i = 0, j = 0; i < days.length; i++){
    if(days[i] <= maxDay) { // 만약 days의 i번째 작업이 maxDay와 같거나 작다면
      answer[j] += 1; // 정답의 0번째 인덱스 +1
    } else { // 만약 뒤의 작업이 첫 번째 작업보다 오래 걸리면
      maxDay = days[i]; // maxDay는 그 작업 일로 대체 !!
      answer[++j] = 1; // j에 1 추가, 그 인덱스 값은 1 (다음 배포 가능 작업 추가됨)
    }
  }

  return answer;
}

입출력 예시

• progresses: [93, 30, 55]
• speeds: [1, 30, 5]
• return: [2, 1]

프린터

조건

다음과 같이 중요도 순으로 작동하는 프린터가 있을 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 리턴해야 한다.

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

• priorities: Array, 현재 대기목록에 있는 문서, 중요도 순
• location: Number, 인쇄를 요청한 문서의 위치
• 인쇄 작업의 중요도는 1~9의 숫자, 클수록 중요

풀이

이 문제의 핵심은 '중요도 순으로 정렬된 배열 생성'이다. 이러한 정렬이 이루어진 후에도 인덱스의 보존을 위해 객체형태를 이용한 점이 특징으로, map을 이용해 먼저 필요한 형태를 만들어준다.

1. 인덱스와 중요도를 표시한 객체를 생성한다. (.map)
2. 이를 중요도 순으로 새로운 큐에 정렬한다. (.some / .push)

• 현재 인덱스보다 중요도가 높은 다른 인덱스가 있다면 현재 인덱스를 맨 뒤로 보낸다.
• 현재 인덱스의 중요도가 가장 높다면 큐로 보낸다.
  정렬 순서는 다음 그림과 같다.

3. 정렬된 큐에서 location과 일치하는 인덱스(+1)를 찾는다. (.findIndex)

function solution(priorities, location) {
  let arr = priorities.map((priority, index) => {
    return {
      index: index, priority: priority
    };
  });
  // map을 통해 인덱스와 중요도를 표시한 객체로 만든다
  // [ {"index": 0, "priority": 1}, {...} ]

  let queue = []; // 정렬된 객체를 담을 큐

  while(arr.length > 0) {
    let firstEle = arr.shift(); // arr의 첫 요소
    let hasHigherPriority = arr.some(ele => ele.priority > firstEle.priority); 
    // arr에 firstEle보다 중요도가 높은 요소가 있다면 true
    if (hasHigherPriority) { // true 라면
      arr.push(firstEle); // firstEle는 arr의 맨 뒤로 push
    } else { // false 라면 
      queue.push(firstEle); // firstEle를 큐에 넣는다
    }
  }
  // 중요도 순으로 정렬된 객체들의 배열 queue 완성

  return queue.findIndex(queueEle => queueEle.index === location) + 1; // location과 일치하는 큐의 인덱스 반환 (+1)
}

입출력 예시

• priorities: [2, 1, 3, 2]
• location: 2
• return: 1