21-03-17 알고리즘 문제풀기 및 노트 정리

기능개발

해당 문제 링크

• 앞에 있는 기능이 배포될 때 함께 배포된다 는 뜻이 선입선출식 자료구조를 사용하라는 뜻이었음
• progresses와 speeds는 짝을 이루는 구조(같은 index값을 갖는 구조)

  1. 한 번의 루프마다 progresses[index] + speeds[index]를 한다
      1-1. 만약 이때 값이 100을 넘었다면 해당 원소들을 각각 shift()한다
      1-2. cnt++과 더불어 index값을 줄여준다(원소를 뺐으므로)
      1-3. cnt값이 0이 아니라면 정답 배열에 넣어준다
  2. 정답 배열을 리턴한다

  function solution(progresses, speeds) {
      let answer = [];
      let cnt = 0; // 한번에 배포되는 기능 수
  
      while(progresses.length > 0) {
          progresses = progresses.map((el, index) => el + speeds[index]); 
          for (let i = 0, len = progresses.length; i < len; i++) {
              if(progresses[i] >= 100) {
                  progresses.shift();
                  speeds.shift();
                  cnt++;
                  i--;
              } else break;
          }
  
          if (cnt > 0) {
              answer.push(cnt); // 한번에 배포될 기능 수를 넣어줌
              cnt = 0; // 0으로 초기화
          }
      }
      return answer;
  }

• 다른 방법

  1. 각 기능마다 걸리는 시간을 소수점자리 올림으로 계산하여 배열을 만듦
  2. 이 배열의 가장 처음값을 빼 변수로 저장하고 이 값을 기준으로 나머지 

  function solution(progresses, speeds) {
      let answer = [];
      let daysLeft = progresses.reduce((acc, cur, index) => {
          let day = Math.ceil((100-cur)/speeds[index]);
          acc.push(day);
          return acc;
      }, [])
  
      let func = daysLeft[0]
      let cnt = 1;
      for (let i = 1; i < daysLeft.length; i++) {
          if (func >= daysLeft[i]) 
              cnt++;
          else {
              answer.push(cnt);
              cnt = 1;
              func = daysLeft[i];
          }
          if (i === daysLeft.length-1)
              answer.push(cnt);
      }
      return answer;
  }

• 이 방법은 작업 완료에 걸리는 일 수를 기준으로 배열을 돌며 배포할 기능 수를 push하는 방법

가장 큰 수

해당 문제 링크

• 처음에는 탐욕법으로 풀어야 하나 했는데 sort함수 하나로 해결 가능한 문제였음
• 테스트 케이스 11번이 0으로만 된 배열이 들어오므로 정수화(parseInt)해서 0이라면 “0”을 리턴하도록 해야 했음

  function solution(numbers) {
      let answer = numbers.map(num => '' + num)
                              .sort((a,b) => (b+a) - (a+b))
                              .join('')
      return parseInt(answer,10) === 0 ? "0" : answer;
  }

  프린터

  해당 문제 링크

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

  function solution(priorities, location) {
      let answer = 0;
      let queue = [...priorities]; // 프린트 큐에 깊은 복사
      let myPrint = location; 
      
      while (queue.length){ 
          // 프린트 큐 맨 처음 있는 작업보다 우선도가 더 크다면
          if (queue.some(priority => priority > queue[0])){
              // 첫 작업을 shift한 후 맨 마지막으로 push한다
              queue.push(queue.shift());
              if (myPrint === 0){
                  myPrint += queue.length - 1;
              } else {
                  // 인덱스 값은 0에서부터 시작되므로 -1 해주어야 함
                  myPrint -= 1;
              }
          } else { 
          // 프린트 큐 맨 처음 작업이 제일 우선도가 높다면
              queue.shift(); // 해당 작업을 shift하고
              answer += 1; // 해답이 해당 작업임
              if (myPrint === 0){
                  break;
              } else {
                  myPrint -= 1;
              }
          }
      }
      return answer;
  }