[프로그래머스] 스택/큐 - 주식가격

 

주어진 prices에서 값을 하나씩 읽어 들어오며, 이전의 prices 값보다 크거나 같다면

인덱스에 해당하는 값을 하나씩 증가시키는 방향으로 코드를 작성하였다.

 

단, 숫자가 작다가 다시 커지는 경우도 있으므로 

가격이 떨어진 후 다시 값이 증가되어 값이 count 될 수 있으므로

prices와 같은 크기의 flag boolean 변수를 만들어 이미 값이 떨어진 변수는 더 이상 count 할 수 없도록 처리하였다.

 

마지막 prices는 값의 변동이 일어나지 않으므로 무조건 0값이다.

따라서 반복문에 포함시키지 않았다.

static int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        boolean[] flag=new boolean[prices.length]; //떨어졌다 다시 올라가는 경우 count 할 수 없도록 만든 변수
        
        // flag, answer변수 초기화
        for(int i=0;i<prices.length;i++) { 
        	flag[i]=true;
        	answer[i]=0;
        }
        
        //마지막 prices 값 제외
        for(int i=0;i<prices.length-1;i++) {
        	//현재 들어온 값 이전 값에 접근하며 조건을 만족하면 answer을 1씩 증가시킨다
        	for(int j=0;j<=i;j++) {
        		//값이 떨어진 적이 없고, 입력 값이 더 크거나 같은 경우에 answer 1증가
        		if(flag[j] && prices[i]>=prices[j]) answer[j]++;
        		// 입력값이 더 작은경우 flag=false
        		// 값이 떨어짐
        		else if(flag[j] && prices[j] > prices[i] ) flag[j]=false;
        	}
        }
        
        return answer;
    }

 

하지만 중첩 for문이 들어가 비효율적인 코드라는 것을 알 수 있다.

prices 배열의 크기는 최대 10만까지 이므로, 10만 x10만의 반복문을 수행해야 한다.

 

이 코드는 정확성 테스트는 다 맞았지만, 효율성 테스트는 충족시키지 못했다..

 

그래서 다시 생각한 코드가 아래이다.

 

static int[] solution(int[] prices) {
		
        int[] answer = new int[prices.length];
 
        int tmp=0;
        
        for(int i=0;i<prices.length-1;i++) {
        	for(int j=i;j<prices.length;j++) {
        		if(prices[i]>prices[j]) {
        			tmp=j-i;
        			break;
        		}
        		if(j==prices.length-1) tmp=prices.length-i-1;
        	}
        	answer[i]=tmp;
        }
        
        return answer;
}

 

위의 코드는 반복문을 모두 돌아야지 모든 원소에 해당하는 정답이 나오지만,

이 코드는 한 원소에 접근할 때마다 바로 정답을 계산하여 answer에 답을 넣는 형식이다.

 

위의 코드는 시간 복잡도가 최대 10만*10만이 될 수 있는 반면,

아래 코드는 j=i에서 반복문이 시작되므로 반복 횟수가 훨씬 적어지는 것을 알 수 있다.

 

아래 코드의 설명을 덧붙이자면

현재 접근한 i 인덱스부터 이후 인덱스까지 중 값이 떨어진 적이 있음을 확인하고

값이 떨어진 인덱스와 차이를 answer [i]에 넣은 것이다.

 

마지막까지 값이 떨어지지 않았더라면 전체 마지막 인덱스에서(prices 배열 길이-1)에서 i를 뺀 값으로 

answer [i] 값을 설정한다.