[Level2] 주식가격 답안 및 풀이

◇ 문제 설명

초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않았습니다.

 

◇ 초기 내용

※ [출처] 프로그래머스-코딩테스트 연습-문제명

※ 초기 내용을 참고하여 문제에 맞는 코드를 작성하세요.

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = {};
        return answer;
    }
}

 

---

◇ 풀이 과정

문제의 풀이과정은 이러했다.

1. answer에 prices의 길이만큼 배열을 할당한다.
2. 각 시점마다 몇초 이후에 가격이 떨어지는지 확인하기 위해 prices의 길이만큼 반복문을 반복한다.
3. 현재 인덱스 +1 부터 prices의 전체길이까지 반복하며 몇 초뒤 현재 시점보다 가격이 떨어지는지 확인한다.
4. 만약, 현재 시점보다 가격이 떨어지는 시점을 만난다면 그 시점에서 현재 시점을 뺸 값을 answer 배열에 저장한다.
5. 모든 시점을 다 체크한 후 끝까지 현재시점보다 가격이 떨어지는 시점이 없다면 배열의 전체 길이에서 현재 시점을 뺀 값을 answer배열에 저장한다.

 

◇  참고 사항

첫번째, 문제 이해가 중요하다!

• 단순히 배열에서 현재보다 낮은 가격을 찾는 문제가 아닌, 몇 초간 현재 가격이 떨어지지 않는지에 관한 문제이다.
• 만약 배열에서 현재보다 낮은 가격을 찾게된다면 아래와 같은 풀이과정이 발생할 것이며 이는 답안과 다르다는 것을 알 수 있을 것이다.

 

• ex. 배열에서 현재보다 낮은 가격을 찾아 반환할때
  [1, 2, 3, 2, 3]
  • i = 1일(인덱스)때 배열에서 1보다 크거나 같은 수의 개수 : 4개
  • i = 2일(인덱스)때 배열에서 2보다 크거나 같은 수의 개수 : 2개
  • i = 3일(인덱스)때 배열에서 3보다 크거나 같은 수의 개수 : 1개
  • i = 4일(인덱스)때 배열에서 2보다 크거나 같은 수의 개수 : 1개
  • i = 5일(인덱스)때 배열에서 4보다 크거나 같은 수의 개수 : 0개
  • 반환되는 배열의 값 : [4, 2, 1, 1, 0]
• ex. 기존 풀이대로 몇 초간 현재 가격이 떨어지지 않는지 찾아 반환할때
  [1, 2, 3, 2, 3]
  
  • i = 1일(인덱스)때 가격이 떨어지지 않는 기간 : (끝까지 떨어지지 않는다) 4초
  • i = 2일(인덱스)때 가격이 떨어지지 않는 기간 : (끝까지 떨어지지 않는다) 3초
  • i = 3일(인덱스)때 가격이 떨어지지 않는 기간 : (i가 4일때 2초로 떨어지므로 가격이 1초간 지속된다) 1초
  • i = 4일(인덱스)때 가격이 떨어지지 않는 기간 : (끝까지 떨어지지 않는다) 1초
  • i = 5일(인덱스)때 가격이 떨어지지 않는 기간 : (끝까지 떨어지지 않고, 마지막 수이므로 0초간 지속된다) 0초
  • 반환되는 배열의 값 : [4, 3, 1, 1, 0]
• 위 두 예제에서 볼 수 있듯이 반환되는 배열의 값이 다르며, 지금 문제에서는 2번째 방법으로 문제를 풀이하는것을 원하고 있다는 걸 잘 이해하면 좋을것 같다.

두번째, 효율성

• 반복문을 2번 돌리게 되므로 메모리를 많이 사용할 수 있기에 조건문을 달아 break문을 이용하여 가격이 떨어지는 첫 값을 찾은 후 반복문을 멈추게 함으로써 효율성을 향상 시켰다.

 

◇ 답안

class Solution {
    public int[] solution(int[] prices) {
        //prices의 길이만큼 배열 생성
        int[] answer = new int[prices.length];
        //자신보다 작은 값이 없으면 false, 있으면 true(없으면 끝까지 가격이 떨어지지 않은것으로 간주)
        boolean flag = false;
        
        //각 시점마다 몇초 이후에 가격이 떨어지는지를 확인해야하므로 prices의 길이만큼 반복문 반복
        for(int i = 0; i<prices.length-1; i++){
        	//각 초마다 flag를 확인할 것이므로 flag 초기화
            flag = false;
            
            //현재 인덱스 +1번 부터 prices의 전체 길이까지 반복
            for(int j = i+1; j<prices.length; j++){
            	//현재 인덱스의 값보다 작은 값이 오는 첫번째 시점(인덱스)을 찾음(가격이 떨어지는 시점)
            	if(prices[i]>prices[j]){
            	    //answer[i]에 j-i(가격이 떨어지는 시점 - 현재 시점 = 가격이 떨어지는 기간)
                    answer[i] += (j-i);
                    //중간에 가격이 떨어졌으므로 flag를 true로 바꿈
                    flag = true;
                    //효율성 증대를 위한 break문 작성(떨어지는 첫 시점만 찾으면 되기 때문)
                    break;
                }
            }
            //만약 flag가 false라면(자신의 시점에서 끝까지 가격이 떨어지지 않는다면)
            if(!flag){
            	//answer[i]에 (전체 길이) - (i+1)을 저장
            	//배열의 인덱스는 0부터 시작하므로 i+1을 하여 빼준다.
                answer[i] = (prices.length - (i+1));        
            }
        }
        
        //값을 return
        return answer;
    }
}

 

◇ 실행결과

주식가격 실행결과

 

◇ 출처

https://programmers.co.kr/learn/challenges

코딩테스트 연습