[CodeUp] 3130 : 소들의 헤어스타일

[문제]

---

 

package day093;

public class Test01 {

	public static void main(String[] args) {

		int N = 6;
		int[] datas = {10, 3, 7, 3, 12, 2};
		int result = 0;
		// 1. 누적 값을 그대로 사용하여 마지막에 출력까지 하는 방식
		// 간편하다. 
		for(int i =0; i<N; i++) {
			int cnt = 0; 
			//2. 이처럼 내부 수행용 result를 새로 파는 방식도 있음
			// 근데 둘이 별 차이 없음.. 성능은 별 상관없으니 가독성, 디버깅 등을 장점으로 들기 
			for(int j = i+1; j<N; j++) {
				if(datas[i] <= datas[j]) {
					break;
				}

				cnt++;
			}
			result+=cnt;
		}
		System.out.println(result);
	}
}

 

[성능 개선 시]

import java.util.Stack;

public class Test02 {

	public static void main(String[] args) {

		int N = 6;
		int[] datas = {10, 3, 7, 3, 12, 2};

		int result = 0;

		Stack<int[]> stack = new Stack<int[]>();
		// 현재 소의 키, 볼 수 있는 소의 마리수

		for(int i = N-1; i>=0; i--) {
			int cnt = 0;
			// 두번째 방법

			while(!stack.isEmpty() && datas[i]> stack.peek()[0]) {
				// stack.peek()[0] == 소의 키
				cnt += stack.pop()[1];
			}

			result += cnt;
			stack.push(new int[] {datas[i], cnt+1});
		}
	}
}