JUNGOL 1141 : 불쾌한 날(Bad Hair Day) (Java)(Stack)

문제출처: jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=421&sca=3020

 

풀이과정

- Stack

- 현재 데이터를 받은 소의 키를 nowHeight변수로 받고 바로 이전 순서의 소들의 키와 비교했을 때, nowHeight가 크거나 같으면 해당 순서의 소들은 이후로 안보일테니 pop으로 스택에서 제거해버린다.    

- 여기서 순서는 Stack의 후입선출법이므로 바로 이전 소부터 시작해서 한마리씩 이전으로 들어가 검사한다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class 불쾌한날_1141 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		long answer = 0;
		Stack<Integer> stack = new Stack<Integer>();

		// 값을 받으면서 풀이
		for (int i = 0; i < N; i++) {
			int nowHeight = Integer.parseInt(br.readLine());
			while (!stack.isEmpty() && stack.peek() <= nowHeight) {
				stack.pop();
			}
			answer += stack.size();
			stack.push(nowHeight);
		}

		System.out.println(answer);
	}
}

- nowheight(현재 검사를 시작하는 소)의 값이 오고, 그 값이 while문을 통해 이전의 소의 키들과 비교한다. 

 

- answer += stack.size()를 하는 이유: stack.size()가 곧 이전에 있는 소들 중 더 키가 큰 소들의 수이기 때문에

 

 

오답 코드(시간초과)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
 
        // 풀이
        int[] answerArr = new int[N];
        Set<Integer> set = new HashSet<Integer>();
        set.add(0);
        for (int i = 1; i < N; i++) {
            boolean check = false;
            for (int num : set) {
                if (arr[num] > arr[i]) {
                    answerArr[num]++;
                    check = true;
                }
            }
            if (!check) {
                set.clear();
            }
            set.add(i);
        }
 
        int answer = 0;
        for (int i = 0; i < answerArr.length; i++) {
            answer += answerArr[i];
        }
        System.out.println(answer);
    }
}

답은 일치하게 나오지만, set은 stack처럼 순서를 구분하지 않았고, set안의 모든 소들의 데이터를 조사해야 했기 때문에 시간초과가 나왔다.