스택/큐

주식가격

1차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
		int[] answer = new int[n];
        
        for(int i=0;i<n;i++) {
        	for(int j=i+1; j<n;j++) {
        		answer[i] += 1;
        		if(prices[i] > prices[j]) {
        			break;
        		}
        	}
        }
        return answer;
    }
}

Arrays.toString(배열 이름)
배열의 원소를 print하기 위해서는 java.utill.Arrays의 toString 메소드를 사용해야합니다.

System.out.println(Arrays.toString(arr));

기능개발

1차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.LinkedList;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int length = progresses.length;
		
		int[] days = new int[length];
		int max = 0;
	
		LinkedList<int[]> result = new LinkedList<>();
		
		for(int i=0; i<length; i++) {

			// 소요시간이 담긴 배열 days 생성
			days[i] = Math.ceil((100-progresses[i]) / speeds[i]);
			
			// 최대값 보다 크다면 다음 원소에 1 삽입
			if(days[i]>max) {
				max = days[i];
				result.add(new int[] {1});
			}
			// 최대값 보다 작다면 해당 원소에 +1
			else {
				result.getLast()[0]++;
			}
		}
		
		// 일반 배열로 복사 후 리턴
		int size = result.size();
		int[] answer = new int[size];
		for (int i = 0; i < size; i++) {
			answer[i] = result.pollFirst()[0];
		}

		return answer;
    }
}

테스트케이스 11통과 불가

Math.ceil(x)

올림

days[i] = (int)Math.ceil((100-progresses[i])/speeds[i]);

100-progresses[i] = 정수 / speeds[i] = 정수 이기 때문에

정수 나누기 정수 를 한다면 정수가 나옵니다. 따라서 올림효과가 일어나지 않습니다.

days[i] = (int)Math.ceil(((double)100-progresses[i])/speeds[i]);

혹은 days[i] = (int)Math.ceil((100-progresses[i])/(double)speeds[i]);

이렇게 해서 올림을 할 수 있도록 만들어주어야 합니다.

Array vs ArrayList vs LinkedList

리스트 설명 특징
Array 정적인 길이를 제공하는 배열 크기를 지정(고정)
Vector 동기화 기능이 제공되는 가변이 가능한 자료구조 저장순서 유지/중복허용
ArrayList 동기화가 제공되지 않음 가변이 가능한 자료구조. + 검색 -데이터의 추가, 삭제
LinkedList 연결리스트 라고도 불리며 노드 간에 연결을 통해서 리스트로 구현된 객체 + 데이터의 추가, 삭제 - 검색(인덱스르 가지고 있지 않음)

2차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.ArrayList;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int length = progresses.length;
		int max = 0;
        
		ArrayList<Integer> result = new ArrayList<>();

		for(int i=0; i<length; i++) {

			// 소요시간이 담긴 배열 days 생성
			int time = (int)Math.ceil(((double)100-progresses[i])/speeds[i]);
			
			// 최대값 보다 크다면 다음 원소에 1 삽입
			if(time>max) {
				max = time;
				result.add(1);
			}
			// 최대값 보다 작다면 해당 원소에 +1
			else {
				result.set(result.size() - 1, result.get(result.size() - 1) + 1);
			}
		}
		
		// 일반 배열로 복사 후 리턴
		int size = result.size();
		int[] answer = new int[size];
		for (int i = 0; i < size; i++) {
			answer[i] = result.get(i);
		}
		return answer;
    }
}

다리를 지나는 트럭

1차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> bridge = new LinkedList<>();
		int sec = 0;
    	int max = 0;

    	for(int w :truck_weights) {
        	while(true) {
        		if(bridge.isEmpty()){
        			bridge.offer(w);
        			max+= w;
        			sec++;
        			break;
        		}else if(bridge.size() == bridge_length){
        			max -= bridge.poll();
        		}else{
        			if(max+w > weight) {
        				bridge.offer(0);
        				sec++;
        			}else {
        				bridge.offer(w);
        				max += w;
        				sec++;
        				break;
        			}
        		}
        	}
    	}
    	return sec + bridge_length;
    }
}

Queue

메소드 설명
public void offer(Element data); 순차보관
public Element poll(); 가장 먼저 보관한 값 꺼내고 반환
public Element peek(); 가장 먼저 보관한 값 단순 참조, 꺼내지 않음
public boolean empty(); 비어있는지 판별

프린터

1차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;

        PriorityQueue<Integer> queue = new PriorityQueue(Collections.reverseOrder());
    	
		// 순서에 따라 요소 삽입
    	for(int priority:priorities) {
    		queue.offer(priority);
    	}
    	
    	while(!queue.isEmpty()) {
    		for(int i=0;i<priorities.length;i++) {
    			if(queue.peek() == priorities[i]) {
    				queue.poll();
    				answer++;
                    
                    if(location == i) {
                        queue.clear();
                        break;
                    }
    			}
    		}
    	}
    	return answer;
    }
}

PriorityQueue<Integer> queue
우선순위에 따라 뽑아야하는 문제 => 우선순위 큐

Collections.reverseOrder()
우선순위가 높을수록 숫자가 크기 때문에 해당 요소 삽입