.programmers(기능개발)

https://programmers.co.kr/learn/courses/30/lessons/42586

 

1. 2022.04.07 시도

소요시간: 14분(5분 문제 해석 및 구상, 9분 풀이), 13분(13분 코딩, queue)

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> ret = new ArrayList<>();
        for (int i=0; i<progresses.length;) {
            int diff = 100 - progresses[i];
            int duration = diff/speeds[i] + (diff%speeds[i]==0 ? 0 : 1);
            
            boolean together = true;
            int count = 1;
            for (int j=i+1; j<progresses.length; j++) {
                progresses[j] += speeds[j]*duration;
                if (progresses[j] >= 100) {
                    if (together) {
                        count++;
                    }
                } else {
                    together=false;
                }
            }
            i+=count;
            ret.add(count);
        }
        
        int[] answer = new int[ret.size()];
        int counter=0;
        for(Integer each: ret) {
            answer[counter++] = each;
        }
        
        return answer;
    }
}

풀이 접근 과정

for문 돌면서 값을 체크해야하고 대상 값이 끝날 때까지의 duration을 구한다.

그리고 연속적인 날짜가 100을 넘은 경우까지만 체크해서 count하고 다음 순회가 진행되도록 넘긴다.

 

느낀점

• queue로 풀어보기도 했다.

import java.util.*;

class Work {
    public int progress;
    public int speed;
    
    Work(int progress, int speed) {
        this.progress = progress;
        this.speed = speed;
    }
}

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> ret = new ArrayList<>();        
        Queue<Work> queue = new LinkedList<>();
        
        for (int i=0; i<progresses.length;i++) {
            queue.offer(new Work(progresses[i], speeds[i]));
        }
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            int count= 0;
            boolean together = true;
            int duration = 0;
            for (int i=0; i<size; i++) {
                Work work = queue.poll();    
                if (i == 0) {
                    int diff = 100 - work.progress;
                    duration = diff/work.speed + (diff%work.speed==0 ? 0 : 1);
                }
                
                int nextProgress = work.progress + work.speed*duration;
                if (together && nextProgress >= 100) {
                    count++;
                } else {
                    together = false;
                    queue.offer(new Work(nextProgress, work.speed));
                }
            }
            ret.add(count);
        }

        int[] answer = new int[ret.size()];
        int counter=0;
        for(Integer each: ret) {
            answer[counter++] = each;
        }
        
        return answer;
    }
}

 

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

 

반응형