프로그래머스 stack/queue

https://programmers.co.kr/learn/courses/30/parts/12081

프로그래머스

탑

import java.util.ArrayList;
import java.util.Stack;


class Solution {
 	public int[] solution(int[] heights) {
		
		Stack<int[]> st = new Stack<int[]>();
		int [] result  = new int[heights.length];
		for(int i=0; i<heights.length; i++) {
			while(!st.isEmpty()) {
				if(st.peek()[1] > heights[i] ) {
					result[i] = st.peek()[0]+1;
					break;
				}
				st.pop();
			}
			
			
			if(st.isEmpty()) {
				result[i] =0;
			}
			
			st.push(new int[] {i , heights[i]});
			
			
		}

		return result;
			
	}
}

풀이 : https://1-7171771.tistory.com/71

백준 2493 탑 java

---

 

주식가격

class Solution {
   public int[] solution(int[] prices) {
		int [] answer = new int[prices.length];
		
		for(int i=0; i<prices.length-1; i++) {
			int count = 0;
			for(int j=i+1; j<prices.length; j++) {
				if(prices[i] <= prices[j]) {
					count++;
				}else {
					count++;
					break;
				}
			}
			
			answer[i] = count;
		}
		answer[prices.length-1] = 0;
	
		return answer;
	}
}

풀이: 오히려 생각을 많이하면 잘 안풀리는 문제이다. 
prices[1, 2, 3, 2, 3]
return[4, 3, 1, 1, 0]

-1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
-2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
-3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
-4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
-5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

라고 설명되어 있는데,말 그대로 1초 시점에서는 1원, 즉 1원보다 더 가격이 떨어질 수는 없기 때문에 4초 동안
 가격이 떨어지지 않는다는 뜻이다.

따라서 prices배열의 값들을 하나씩 비교하면서 count를 증가시켜주고,  마지막 (예제에서는 5초)은 무조건 0이기때문에 따로 구현해준다.

 

 

다리를 지나는 트럭

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class Truck {
		int weight;
		int distance;

		public Truck(int weight, int distance) {
			this.weight = weight;
			this.distance = distance;
		}
	}
class Solution {


	public int solution(int bridge_length, int weight, int[] truck_weights) {
		int weigthLeft = weight;
		int time = 0;

		Queue<Truck> outList = new LinkedList<Truck>();
		List<Truck> inList = new ArrayList<Truck>();

		for (int value : truck_weights) {
			outList.add(new Truck(value, bridge_length));
		}

		while (!(outList.isEmpty() && inList.isEmpty())) {
			time++;


			if (!inList.isEmpty() && inList.get(0).distance == 0) {
				weigthLeft += inList.get(0).weight;
				inList.remove(0);
			}
            if (!outList.isEmpty() && outList.peek().weight <= weigthLeft) {
				weigthLeft -= outList.peek().weight;
				inList.add(outList.poll());
			}

			for (int i = 0; i < inList.size(); i++) {
				inList.get(i).distance--;
			}

		}

		return time;

	}

}

 

 

프린터

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

class printer{
	int documentNumber;
	int pri;
	
	printer(int documentNumber, int pri){
		this.documentNumber = documentNumber;
		this.pri = pri;
	}
}

class Solution {
public int solution(int[] priorities, int location) {
		
		Queue<printer> queue = new LinkedList<>();
		
		int result =1;
		
		
		for(int i=0; i<priorities.length; i++) {
			queue.add(new printer(i,priorities[i]));
		}
		
		while(!queue.isEmpty()) {
			printer curDocu = queue.poll();
			boolean ck = true;
			Iterator it = queue.iterator();
			while(it.hasNext()) {
				printer value =(printer) it.next();
				
				if(value.pri > curDocu.pri) {
					queue.add(curDocu);
					ck = false;
					break;
				}
			}
			
			if(ck) {
				if(curDocu.documentNumber == location) {
					break;
				}else {
					result++;
				}
			}
			
		}
			return result;
		
	}
}

 

쇠막대기

import java.util.Stack;
class Solution {
  public int solution(String arrangement) {

		int count = 0;

		Stack<Integer> st = new Stack<>();

		for (int i = 0; i < arrangement.length(); i++) {
			if (arrangement.charAt(i)  == '(') {
				st.push(i);
			} else {
				if (st.peek() == i - 1) {
					st.pop();
					count += st.size();
				} else {
					st.pop();
					count++;
				}
			}

		}

		return count;

	}
}

 

기능개발

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
		Queue<Integer> q = new LinkedList<Integer>();
		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 0; i < progresses.length; i++) {
			q.add((100 - progresses[i]) % speeds[i] == 0 ? (100 - progresses[i]) / speeds[i]
					: (100 - progresses[i]) / speeds[i] + 1);
		}
		
		int firstProgress = q.poll();
		int count = 1;
		
		while(!q.isEmpty()) {
			int nextProgress = q.poll();
			if(firstProgress >= nextProgress) {
				count++;
			}
			else {
				list.add(count);
				count =1;
				firstProgress = nextProgress;
			}
		}
		
		list.add(count);
		
		int [] result = new int[list.size()];
		for(int i=0; i<result.length; i++) {
			result[i] = list.get(i);
		}
		
		return result;
	}
}