기능개발 #스택/큐 #level2

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

 

 

💡 실행

import java.util.Arrays;

public class Run {
	public static void main(String[] args) {
		int[] inputs = { 93, 30, 55 };
		int[] speed = { 1, 30, 5 };

		// result: [2, 1]
		System.out.println(Arrays.toString(new FuncDevelopment().solution(inputs, speed)));
	}

}

 

💡 풀이

import java.util.ArrayList;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

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

		// Queue에 각 기능개발에 걸리는 일수를 삽입한다.
		// progresses[i]가 speeds[i]에 나눠 떨어지면 몫을, 그렇지 않다면 몫 + 1을 삽입해준다.
		Queue<Integer> queue = new ConcurrentLinkedQueue<>();
		for (int i = 0; i < progresses.length; i++) {
			queue.add(
				(100 - progresses[i]) % speeds[i] == 0 ? 
				(100 - progresses[i]) / speeds[i] : 
				(100 - progresses[i]) / speeds[i] + 1);
		}

		// queue: [7, 3, 9]
		System.out.println("queue: " + queue);
		
		// whlie문이 시작하기 전에 queue에서 첫번째요소를 poll()해준다.(가장 처음 개발되기 시작한 기능)
		ArrayList<Integer> list = new ArrayList<>();
		int prevFunc = queue.poll();
		int numOfFuncs = 1;

		// 첫번째의 기능을 개발하는 데에 걸리는 일수가 다음 기능을 개발하는 데 걸리는 일수보다 오래걸리거나 같다면
		// 첫번째의 기능을 배포할 때 다음 기능도 같이 배포해야한다. 그렇기 때문에 numOfFuncs의 값을 1증가 시킨다.
		
		// 만약 그렇지 않다면 (앞선 기능보다 다음 기능을 개발하는 데 더 오래 걸린다면)
		// 앞선 기능을 배포할때는 해당 기능만 배포하기 떄문에 numOfFuncs는 1이 된다.
		while (!queue.isEmpty()) {
			int curFunc = queue.poll();
			
			// prevFunc: 7, curFunc: 3
			// prevFunc: 7, curFunc: 9
			System.out.println("prevFunc: " + prevFunc + ", curFunc: " + curFunc);

			if (prevFunc >= curFunc) {
				numOfFuncs++;
			} else {
				list.add(numOfFuncs);
				numOfFuncs = 1;
				prevFunc = curFunc;
			}
		}
		
		list.add(numOfFuncs);
		int[] answer = new int[list.size()];
		for (int i = 0; i < list.size(); i++) {
			answer[i] = list.get(i);
		}
		return answer;
	}
}

 

 

P.S. ConcurrentLinkedQueue

자바의 java.util 에서 제공하는 Queue 클래스는 멀티 스레드 환경에서 임계영역(critical section)에 대한 동기화가 적용되어 있지 않다.

 

무슨 말이냐, 

여러 개의 쓰레드에서 하나의 Queue 객체에 들어있는 데이터를 꺼내기 위해 queue.poll() 메서드를 호출할 경우, 동일한 실행 결과가 나타날 수 있다. 예를 들어, Queue에 [1, 2, 3]과 같은 데이터가 들어있을 경우, 스레드 3개가 critical section에서 poll() 메서드를 호출하면 각 스레드들은 모두 1이라는 데이터를 가져오고 Queue에는 [2, 3]만 남게 된다. 큐가 비어있을 경우 null을 리턴하게 된다.

 

이에 우리는 멀티 스레드 환경에서 자바는 멀티 스레드 환경에서 컬렉션의 요소를 동시에 처리할 수 있는 Queue를 사용해야하는데 여기에서는 ConcurrentLinkedQueue를 사용했다.

 

ConcurrentLinkedQueue는 생산자-소비자 producer-consumer 모델에서 소비자가 많고 생산자가 하나인 경우에 주로 사용된다.

import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

Queue<Object> queue = new ConcurrentLinkedQueue<Object>();
queue.offer(data);  // put
queue.poll();       // get