[Jungol][Java][stack] 1141 - 불쾌한 날

농부 시현이의 N(1≤N≤80,000)마리의 소들은 "bad hair day"를 맞이하였다. 

 

각 소들이 자신들의 촌스런 머리 모양을 부끄러워 하자, 시현이는 소들이 다른 소들의 머리 모양을 얼마나 알 수 있는지를 알고자 했다.

i번째 소들은 키가 hi(1≤hi≤1,000,000,000) 이며, 동쪽(오른쪽)을 바라보고 서있다. 

 

따라서, i번째 소는 자신의 앞 ( i+1, i+2,...)의 소들의 머리 모양만 볼 수 있으며, 앞에 자신의 키보다 작은 소들만 볼 수 있다.​

다음 예제를 고려해보자: ()의 숫자는 키를 나타낸다. 

1번 소는 2,3,4번소의 머리 모양을 볼 수 있다. 

2번 소는 어떤 소의 머리 모양도 볼 수 없다. 

3번 소는 4번 소의 머리 모양을 볼 수 있다. 

4번 소는 어떤 소의 머리 모양도 볼 수 없다.  

5번 소는 6번 소의 머리 모양을 볼 수 있다. 

6번 소는 모든 소들의 머리 모양을 볼 수 없다!

 

i번 소들이 볼 수 있는 머리 모양의 수를 Ci 이라고 할 때, C1부터 CN 까지의 합을 출력하는 프로그램을 작성하라. 

 

위의 예제의 답은 3+0+1+0+1+0=5가 된다.​ 

 

---

문제 풀이

해당 문제는 그냥 하나씩 비교하게 되면 시간초과가 나는 문제이다.

 

Stack을 활용해서 풀면 되는데 풀이 알고리즘은 다음과 같다.

 

포인트는 자기를 볼 수 있는 소를 stack에 쌓아두는 것이다. 즉, 자기보다 작으면 제거하고 크면 남겨둔다.

 

 

1번 소는 처음에 stack에 반드시 들어간다.

 

2번 소부터 검사하면 되는데 2번 소와 stack에 제일 top에있는 소를 비교해서 top에 있는 소보다 크면 stack top에 있는 소를 제거한다.

 

그 이유는 자신보다 작은 소는 자신을 쳐다보지 못하기 때문에 의미가 없으므로 제거한다.

 

stack이 빌때까지 혹은 자신보다 큰 수가 나올때까지 검사한다. 

 

stack.size만큼 더해주면 되는데 이는 stack에는 자기를 볼 수 있는 소들이 남아있기 때문이다. 

 

출처: https://octorbirth.tistory.com/594

 

package jungol;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
// point 나를 볼 수 있는 소를 Stack에 쌓아두자!
public class Main_1141 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Integer> stack = new Stack<Integer>();
		long sum=0;
		int N=Integer.parseInt(br.readLine());
		
		for(int i=1;i<=N;i++) {
			int curCow=Integer.parseInt(br.readLine());
			while(!stack.isEmpty()) {
				if(stack.peek() <= curCow) {
					stack.pop(); // 나보다 키가 크면 못보니까 제거.
				} else {
					sum+=stack.size(); // 이 소를 볼 수 있는 소들이 stack에 쌓여있으니까 stack만큼 더해주면 이 소를 볼 수 있는 이전 소들의 수 + !!
					break;
				}
				
			}
			stack.push(curCow); 
		}
		System.out.println(sum);
	}

}