728x90
코딩테스트 연습 / 스택/큐 / 주식가격
📈 주식가격
🏷️ 관련 주제 : Queue
💡 Solution with Queue & 반복문
import java.util.Queue;
import java.util.LinkedList;
class Solution {
public int[] solution(int[] prices) {
int prices_length = prices.length;
int[] answer = new int[prices_length];
Queue<Integer> price_indexes = new LinkedList<>();
price_indexes.add(0);
for (int i = 1; i < prices_length-1; i++) {
int price = prices[i];
int queue_size = price_indexes.size();
for (int j = 0; j < queue_size; j++) {
int check_index = price_indexes.poll();
if (check_index <= i) {
int check_price = prices[check_index];
if (price < check_price) {
answer[check_index] = i-check_index;
continue;
}
}
price_indexes.add(check_index);
}
price_indexes.add(i);
}
while(!price_indexes.isEmpty()) {
int index = price_indexes.poll();
answer[index] = prices_length-index-1;
}
return answer;
}
}
💡 Solution with Queue & Stream
import java.util.Queue;
import java.util.LinkedList;
import java.util.stream.IntStream;
class Solution {
public int[] solution(int[] prices) {
int prices_length=prices.length;
int[] answer=new int[prices_length];
Queue<Integer> price_indexes = new LinkedList<>();
price_indexes.add(0);
IntStream.range(1,prices_length-1)
.forEachOrdered(i->{
int price=prices[i];
int queue_size = price_indexes.size();
IntStream.range(0, queue_size)
.forEachOrdered(j -> {
int check_index=price_indexes.poll();
if (check_index<=i) {
int check_price=prices[check_index];
if (price<check_price) {
answer[check_index]=i-check_index;
return;
}
}
price_indexes.add(check_index);
});
price_indexes.add(i);
});
price_indexes.stream()
.forEachOrdered(i -> answer[i] = prices_length-i-1);
return answer;
}
}
📗 참고 자료
- [JAVA / 자바] Queue(큐) 클래스 사용법 및 함수(Method) 정리
- [Java] 자바 Queue 클래스 사용법 & 예제 총정리
- [Java/자바] IntStream을 List로 변환하는 방법
- StreamAPI 나도 한 번 써보자!
문제를 풀면서 특이했던 점이
첫번째 풀이는 처음에 이렇게 작성했었는데
import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;
class Solution {
public int[] solution(int[] prices) {
int prices_length = prices.length;
int[] answer = new int[prices_length];
Queue<Integer> price_indexes = new LinkedList<>();
for (int i = 0; i < prices_length - 1; i++) {
int price = prices[i];
int queue_size = price_indexes.size();
for (int j = 0; j < queue_size; j++) {
int check_index = price_indexes.poll();
if (check_index <= i) {
int check_price = prices[check_index];
if (price < check_price) {
answer[check_index] = i - check_index;
continue;
}
}
price_indexes.add(check_index);
}
price_indexes.add(i);
}
while(!price_indexes.isEmpty()) {
int index = price_indexes.poll();
answer[index] = prices_length - index - 1;
}
return answer;
}
}
실제 코드에 넣지 않아도되는
import java.util.Arrays;를 빼면 효율성 테스트에서 실패가 뜨고
Stream을 사용한 방법을 사용할 때, 처음에 아래 처럼 코드를 작성했었는데
import java.util.Queue;
import java.util.LinkedList;
import java.util.stream.IntStream;
class Solution {
public int[] solution(int[] prices) {
int prices_length = prices.length;
int[] answer = new int[prices_length];
Queue<Integer> price_indexes = new LinkedList<>();
IntStream.range(0, prices_length-1)
.forEachOrdered(i -> {
int price = prices[i];
int queue_size = price_indexes.size();
for (int j = 0; j < queue_size; j++) {
int check_index = price_indexes.poll();
if (check_index <= i) {
int check_price = prices[check_index];
if (price < check_price) {
answer[check_index] = i - check_index;
continue;
}
}
price_indexes.add(check_index);
}
price_indexes.add(i);
});
price_indexes.stream()
.forEachOrdered(i -> answer[i] = prices_length - i - 1);
return answer;
}
}
IntStream.range(0, prices_length-1)
를 연산자 사이에 띄어쓰기를 넣어서 아래처럼 수정하면
IntStream.range(0, prices_length - 1)
또 효율성 테스트에서 실패한다는 점이다.
효율성 테스트가 너무 통과가 안될 때는 띄어쓰기를 조금씩 바꿔봐도 괜찮은걸까?
혹시나 해서 지금 작성한 풀이처럼 연산자 앞뒤로 공백을 삭제했는데
효율성 테스트 시간이 엄청나게 줄어들었다.
효율성 테스트가 실패할 때는 되도록이면 띄어쓰기가 많지 않은게 좋은가보다.
사실 반복문을 쓰는 것이 더 간단한 느낌이긴 한데
효율성 테스트에서 Stream을 쓰면 조금 더 빨라지는지 궁금해서 문제를 Stream으로 한번 더 풀어 보았다.
결과는 아주 약간 더 빨라진 것 같다.
🖋️ 풀이 방법
1. 주식 가격 배열의 인덱스를 담을 큐 생성
Queue<Integer> price_indexes = new LinkedList<>();2. price_indexes에 주식 가격의 첫번째 원소 인덱스 0 추가
price_indexes.add(0);3. 1 ~ (주식 가격 배열 길이) - 1 범위로 반복문(IntStream) 돌기
// 풀이 1
for (int i = 1; i < prices_length - 1; i++) {
// 코드 생략
}
// 풀이 2
IntStream.range(1, prices_length-1)
4. 현재 인덱스의 주식 가격 price 초기화 및 큐 사이즈 queue_size 구하기
int price = prices[i];
int queue_size = price_indexes.size();
5 - 1. queue_size만큼 반복문(IntStream)을 돌면서 큐의 모든 원소(check_index) 꺼내기
int check_index = price_indexes.poll();5 - 2. check_index 인덱스의 주식 가격 check_price 초기화
int check_price = prices[check_index];5 - 3. check_price가 price보다 크면 answer의 check_index 원소를 (현재 인덱스) - check_index로 변경
이건 빼도 괜찮을 것 같은데 빼면 효율성 테스트에서 실패해서 못 뺐다.
if (price<check_price) {
answer[check_index]=i-check_index;
return;
}5 - 4. 그렇지 않으면 큐에 다시 check_index 추가
price_indexes.add(check_index);
6. 큐에 현재 인덱스 추가
price_indexes.add(i);
7. 큐의 남은 인덱스들의 가격이 떨어지지 않은 기간을 주식 가격 배열 길이 기준으로 구해서 answer에 할당
price_indexes.stream()
.forEachOrdered(i -> answer[i] = prices_length-i-1);
728x90
