[AlphaGo Study] [Programmers] [JAVA] 주식가격

문제 설명

 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한 사항

☞ prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.

☞ prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

입출력 예 설명

#예제 1

 ① 1초 시점의 ￦1은 끝까지 가격이 떨어지지 않았습니다.

 ② 2초 시점의 ￦2는 끝까지 가격이 떨어지지 않았습니다.

 ③ 3초 시점의 ￦3은 1초 뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.

 ④ 4초 시점의 ￦2는 1초간 가격이 떨어지지 않았습니다.

 ⑤ 5초 시점의 ￦3은 0초간 가격이 떨어지지 않았습니다.

 

programmers.co.kr/learn/courses/30/lessons/42584

코딩테스트 연습 - 주식가격

---

문제 풀기 전 THINK

 § 큐를 사용하여 가격을 넣었다 뺐다 하는 알고리즘을 사용.

 § peek()과 poll()의 차이점을 알고 사용.

 § 가격이 떨어졌을 때에도 1초는 유지해야 하므로 cnt를 +1 해줌.

나의 Solution

public class StockPrice {
	public static int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Queue<Integer> queue = new LinkedList<Integer>();
        
        for(int i = 0; i < prices.length; i++) {
        	queue.add(prices[i]);
        } // for end
        
        for(int i = 0; i < prices.length; i++) {
        	// queue.peek() 하면 앞 데이터가 삭제가 안됨.
        	int pri = queue.poll();        	
        	int cnt = 0;
        	
        	for(int q : queue) {
        		if(pri <= q) { // 가격 안 떨어졌을 때
        			cnt++;
        		} else { // 가격 떨어졌을 때
        			cnt++; // 떨어지고(1초는 유지해야 함)
        			break; // 끝
        		} // if ~ else end
        	} // for q : queue end
        	answer[i] = cnt;
        } // for(i) end
        return answer;
    }
}

Comment...

첫 번째로 이렇게 풀었더니 굉장히 빨리 테스트가 통과돼서 굉장히 잘 푼 줄 알았다.

근데 다 실패 실화냐고..ㅜ_ㅜ

public class StockPrice {
	public static int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        int cnt;
        
        for(int i = 0; i < prices.length; i++) {
        	cnt = 0;
        	for(int j = i + 1; j < prices.length; j++) {
        		if(prices[i] <= prices[j]) {
        			cnt++;
        		} // if end
        		answer[i] = cnt;
        	} // for(j) end
        } // for(i) end
        return answer;
    }
}

 

  처참 그자체...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ;;;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

그래서 두 번째로 푼 방법은 Queue를 써보았다. 조금 더 효율적이지 않을까!? 해서!

public class StockPrice {
	public static int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Queue<Integer> queue = new LinkedList<Integer>();
        int cnt;
        int pri;
        
        for(int i = 0; i < prices.length; i++) {
        	queue.add(prices[i]);
        } // for end
        
        for(int i = 0; i < prices.length; i++) {
        	// queue.peek() 하면 앞 데이터가 삭제가 안됨.
        	pri = queue.poll();        	
        	cnt = 0;
        	System.out.println("pri = " + pri);
        	
        	for(int j = i + 1; j < prices.length; j++) {
        		if(pri <= queue.peek()) { // 가격 안 떨어졌을 때
        			cnt++;
        		} else { // 가격 떨어졌을 때
                		cnt++; // 떨어지고(1초는 유지해야 함)
        			break; // 끝
        		} // if ~ else end
        	} // for(j) end
        return answer;
    }
}

그래도 첫 번째 방법처럼 실패가 주르르르륵....뭐가 문제일까...? 더 생각해보자....

 

＊이중 for문이 문제였나..? 향상된 for문이랑 일반 for문이랑 성능의 차이가 있는 것일까.....