코딩테스트 고득점 kit / 스택&큐 / 기능개발 / JAVA

 

풀이방법 1

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] answer = {};
        Deque<Integer> q = new ArrayDeque<Integer>();
        List<Integer> l = new ArrayList<Integer>();

        for(int i=0; i<speeds.length; i++) {
        	q.offer(i);
        }
        
        int count = 0;
        while(!q.isEmpty()) {

        	int size = q.size();
        	
        	for(int i=0; i<size; i++) {
        		int j= q.pop();
        		progresses[j] += speeds[j];
        		q.offer(j);
        	}
        	
        	int cnt = 0;
	    	 for(int i=0; i<size; i++) {
	    		 if(progresses[q.peek()] >= 100) {
	    			 cnt++;
	    			 q.poll();
	    		 } else break;
	    	 }
        	
	    	 if(cnt != 0) {
	    		 l.add(cnt);
	    	 }
        	
        }
        
        answer = new int[l.size()];
        for(int i=0; i<l.size(); i++) {
        	answer[i] = l.get(i);
        }
        return answer;
    }
}

Queue안에 인덱스값을 넣어서 progresses값에 speeds값을 더해주는 방식입니다.

이 문제는 반복문과 배열만 가지고 푼다고 했을때 조금 생각해봐야 하는 문제입니다. 예를들어 100이 넘어가는 프로세스들을 큐에서 제거하면 큐 사이즈 만큼만 돌리면 되기 때문에 배열처럼 전체길이만큼 검사할 필요가 없습니다.

 

하지만, 큐의 경우도 반복문에서 사용할때는 조심해야됩니다.

무턱대고 i < q.size()를 반복분에서 사용되는데 내부적으로 q.pop()이나 q.offer()를 해버리는 경우 size에 변화가 생기게 됩니다.

따라서 이 문제는 size()를 미리 변수에 저장해두는게 키 포인트입니다.

 

전체 루프는 하루마다 돌아가게끔 짜고 내부적으로 for문을 하나 더 만들어서 하루주기로 돌아가는 프로세스들을 한번씩 반복시킵니다. 이 때도 성급하게 내부적으로 if문을 쓰기보다는 일단은 한번씩 더 더해주는것이 좋습니다. 나중에 100넘는 프로세스들만 한꺼번에 제거하고 카운트 해야되기 때문입니다.

 

 

풀이방법 2

import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] answer = {};
        
        List<Integer> list = new ArrayList<Integer>();
        Deque<Integer> q = new ArrayDeque<Integer>();
        
        for(int i=0; i<progresses.length; i++){
            int date = (int) Math.ceil( (double) (100 - progresses[i]) / speeds[i]);
            while(!q.isEmpty() && q.peek() < date){
                list.add(q.size());
                q.clear();
            }
            
            q.offer(date);
        }
        
        list.add(q.size());
        
        answer = new int[list.size()];
        for(int i=0; i<list.size(); i++){
            answer[i] = list.get(i);
        }
        
        return answer;
    }
}

며칠 뒤에 일이 끝나는지 미리 계산하는 방법입니다.

100이 되면 작업이 끝나므로 100까지 가기 위해 며칠이 소요되는지 100에서 현재 progress를 빼주고 speed로 나눠주면 됩니다.

 

이 때 주의할점은 나눗셈이 무조건 딱 맞아 떨어진다는 보장이 없으므로 Math.ceil()을 이용하여 올림을 해줘야 합니다.

또한 Math.ceil()은 return값이 double 이기 때문에 int로 강제 형변환을 해줘야 합니다.

 

그리고 큐에 날짜값을 넣어줍니다.

날짜값을 넣어주기전에 미리 큐에 첫번째로 들어온 날짜보다 큰지 작은지 비교해줍니다.

( peek() : stack의 peek()이랑 헷갈리시면 안됩니다)

만약 첫번째로 들어온 날짜보다 크다면 list에 큐의 사이즈를 추가해주고 큐를 비워줍니다.

그리고 새로 들어온 큰 값을 큐에 집어넣습니다.

 

이 때도 주의할점이 있습니다.

for문이 다 돌았는데도 for문의 마지막에 q.offer()를 하기 때문에 큐에 데이터가 남아있는 상황이 발생합니다.

그 경우를 대비해 for문이 다 돌면 마지막에 list에 남은 큐 사이즈를 입력해줍니다.

 

코드는 대략 이런 구조로 되어있습니다.

프로그래머스의 HamYoungChan이라는 분이 푸신 방법인데

굉장히 큐에 대한 이해도가 높은 코드인것 같습니다.

 

큐 대신 count를 사용해서 가능할지 시간이 나면 한번 도전해보면 좋을것 같습니다.

 

 

풀이방법3

import java.lang.System;
import java.lang.Math;
import java.util.ArrayList;

class Solution {

    int progressesCount;
    int[] needDays; 

    ArrayList<Integer> workCountStorage;

    public int[] solution(int[] progresses, int[] speeds) {

        //Init
        progressesCount = progresses.length;
        needDays = new int[progressesCount];
        workCountStorage = new ArrayList<>();


        //필요한 작업일 계산
        this.calcNeedDays(progresses, speeds);

        //this.viewAll(needDays, 0);


        //동시에 진행된 프로세스 계산
        for(int step=0; step<progressesCount;)
        {
            int stepNeedDay = needDays[step];

            //날짜 동시에 경과
            for(int remainStep=step; remainStep<progressesCount; remainStep++)
            {
                needDays[remainStep] -= stepNeedDay;
            }

            //this.viewAll(needDays, step);

            //완료한 작업까지의 갯수
            int workCount = 1;
            for(;step+workCount<progressesCount; workCount++)
            {
                if(needDays[step+workCount] > 0)
                {
                    break;
                }
            }

            System.out.println("workCount:"+workCount);

            //완료한 작업 갯수 저장
            workCountStorage.add(workCount);

            //작업 갯수만큼 step 증가
            step += workCount;    

        }

        //int[] answer = {};
        int[] answer = Solution.convertIntegers(workCountStorage);
        return answer;
    }

    private void calcNeedDays(int[] progresses, int[] speeds)
    {
        for(int i=0; i<progressesCount; i++)
        {
            double remainProgress = 100 - progresses[i];
            double fNeedDay = remainProgress / speeds[i];

            needDays[i] = (int)Math.ceil(fNeedDay);
        }
    }

    public static int[] convertIntegers(ArrayList<Integer> integers)
    {
        int size = integers.size();
        int[] ret = new int[size];
        for (int i=0; i<size; i++)
        {
            ret[i] = integers.get(i).intValue();
        }
        return ret;
    }

    private void viewAll(int[] array, int startIdx)
    {
        System.out.print("viewAll:");

        int arrayCount = array.length;
        for(int i=startIdx; i<arrayCount; i++)
        {
            System.out.print(array[i]+",");
        }

        System.out.println();
    }
}

 

 

히스토리

 

chucoding/algorithm