TIL (2022.02.21)

➕ 오늘 푼 문제

프로그래머스 - 기능개발

➕ 아이디어

• 각 기능별로 소요일을 큐에 담는다.
• 큐에서 소요일을 하나씩 빼면서
  • 이전 소요일(before)이 현재 소요일(now)보다 크거나 같다면, 이전 기능이 아직 끝나지 않았으므로 기다렸다가 같이 배포
    • 같이 배포하는 기능(count) 개수 증가
  • 적다면 따로 새로운 날짜에 배포
    • 이전까지 모인 기능들을 배포하고 (answer에 count 추가), 개수 초기화
    • 이전 소요일(before)은 현재 소요일(now)로 갱신

➕ Java 코드

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        ArrayList<Integer> answer = new ArrayList<>();
        int n = progresses.length;
        Queue<Integer> days = new LinkedList<>();
        
        for(int i=0; i<n; i++){
         	int day =  (int) Math.ceil((100 - progresses[i]) / (double) speeds[i]);
            days.add(day);
        }
        
        int before = 0, now = 0;
        int count = 1;
        
        before = days.poll();
        while(!days.isEmpty()){
            now = days.poll();
            
            if(now <= before){
                count += 1;
            }else{
                answer.add(count);
                count = 1;
                before = now;
            }
        }
        
        answer.add(count);
        
        return answer.stream().mapToInt(i->i).toArray();
    }
}

➕ Python 코드

from collections import deque
import math

def solution(progresses, speeds):
    n = len(progresses)
    answer = []
    days = deque([])
    
    for i in range(n):
        day = math.ceil((100 - progresses[i]) / speeds[i])
        days.append(day)
        
    before = days.popleft()
    count = 1
    
    while days:
        now = days.popleft()
        if now <= before:
            count += 1
        else:
            answer.append(count)
            count = 1
            before = now
            
    answer.append(count)
        
    return answer

➕ 궁금한 내용 및 소감

• 스택/큐를 이용하는 문제라는 것을 몰랐으면 이렇게 빠르게 아이디어를 낼 수 있었을까 의문이 들긴 한다. 하지만 이번 문제도 혼자 힘으로 풀었다는 데 의의를 두기로 했다!
• 자바의 큐에서 사용하는 용어는 아직 익숙하지가 않다. 아래 내용들을 기억하면 좋을 것 같다.
  • 자바에서 Queue는 인터페이스로 실제 구현은 주로 LinkedList로 한다
  • offer : add와 동일하게 큐에 데이터를 삽입한다. 차이점은 add는 크기가 꽉 찼을 경우 예외를 발생시키지만 offer는 false를 반환한다.
  • poll : 큐에서 맨 앞(왼쪽)에 있는 원소를 반환한 뒤 삭제한다.
  • peek : 큐에서 맨 앞(왼쪽)에 있는 원소를 반환한다.

➕ 참고 문헌

• Java - Queue 사용법
  • 참고 링크: 알고리즘을 위한 자바 문법 정리