[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은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
※ 공지 - 2019년 2월 28일 지문이 리뉴얼되었습니다.

✨Methodology

brute force Algorithms

스택/큐 문제에 있지만 간단하게 이중 for loop를 돌려서 풀면 더 쉽게 접근할 수 있을 것 같아 이중 for loop를 통해 풀었다.

• answer 배열은 입력된 prices의 길이와 동일
• 이중 for loop를 통해 i번째 가격과, 그 후의 가격(i+1 부터)들을 차레로 비교한다
• 만약 i번째 가격이 j번째 가격보다 높으면 가격이 떨어짐-> escape loop
• else: 가격 유지 또는 상승

✨전체 소스 코드

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
		for(int i = 0; i< prices.length ; i++) {
			for (int j =i+1; j < prices.length; j++) {
				answer[i]++;
                		if(prices[i]>prices[j])break;//가격 떨어짐
			}
		}
		return answer;
    }
}

---

✨문제 이해

문제 설명 이해

수정 전 코드

for (int j =i+1; j < prices.length; j++) {
    if(prices[i]<=prices[j])answer[i]++; //가격이 떨어지지 않았다
}

위의 코드처럼 풀었지만 첫번째 테스트케이스를 제외한 모든 테스트 케이스에서 fail이 났다. 문제 예제 중, 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. 설명을 잘못 이해하고 있었다.

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

prices = 3일떄, 떨어짐->유지 : {1} 이라고 이해하고 있었지만
1초 뒤에 가격이 떨어졌기 때문에 1 이었다.

[예시] prices = 3 일때:

prices	return
{1, 2, 3, 2, 3, 3}	{5, 4, 1, 2, 1, 0}

처음에는 문제를 읽고 prices = 3일때, -1, 유지, -1 -> 2 라고 생각하고 코드를 짰다.
따라서 위 예제의 답을 {5,4,2,2,1,0} 이 된다고 생각했다.

하지만, prices = 3일때, 1초 후인 2에서 가격이 떨어지기 때문에 답은 {1} 이 된다.
즉, count하는게 아니라 주식의 가격이 떨어질 경우에는 떨어진 시점이 몇초 후인지 세는 것이다.

수정된 코드

for(int i = 0; i< prices.length ; i++) {
	for (int j =i+1; j < prices.length; j++) {
		answer[i]++;
    		if(prices[i]>prices[j])break;//가격 떨어짐
	}
}

따라서 answer[i]++로 매 순간 초를 센 후에 만일 가격이 떨어진 경우에는 멈춰주면 된다.