Jungol[1141] - 불쾌한 날(Bad Hair Day)

링크

Jungol[1141]

문제설명

• O(N^2)

문제풀이

• 최적화 해야함. Scanner 이용하면 시간초과. BufferedReader사용. Heap사용 최소화.

    cow   5  2  4  2  6  1  
    stack2              -2  
    stack1      -2  4 -4  
    stack0   5  5  5 -5  6  
    count 0  1  1  2  0  1

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.Stack;

public class Main1141 {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/jungol/1141.txt"));
//        Scanner sc = new Scanner(System.in);
//        int N = sc.nextInt();
//        int [] cow = new int[N];
//        for (int i = 0; i < N; i++) {
//            cow[i]=sc.nextInt();
//        }
//        /*
//         * 선형탐색
//         */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
//        int [] cow = new int[N];
        Stack<Integer> stack = new Stack();
        long ans = 0;

        int stk_temp=0;
        for (int i = 0; i < N; i++) {
//            cow[i] = Integer.parseInt(br.readLine().trim());
            stk_temp = Integer.parseInt(br.readLine().trim());
            while(!stack.isEmpty() && stack.peek()<=stk_temp) {
                stack.pop();
            }
            ans += stack.size();
            stack.push(stk_temp);
        }

//        for (int i = 0; i < N; i++) {
////            cow[i] = Integer.parseInt(br.readLine().trim());
//            stk_temp = Integer.parseInt(br.readLine().trim());
//            if(stack.isEmpty()) {
//                ans += stack.size();
//                stack.push(stk_temp);
//            }
//            else {
//                while(stack.peek()<=stk_temp) {
//                    stack.pop();
//                    if(stack.size()==0)break;
//                }
//                ans += stack.size();
//                stack.push(stk_temp);
//            }
//        }


//        int temp = 0;
//        for (int i = 0; i < N-1; i++) {
//            temp = cow[i];    //로컬 변수 사용(heap 가는거 단축)
//            for (int j = i+1; j < N; j++) {
//                if(temp>cow[j]) {
//                    ans++;
//                }
//                else break;
//            }
//        }

        System.out.println(ans);
    }
}

아쉬운점

• Heap사용 최소화 -> cow[i] 호출 최소화
• O(N^2) = 80000^2 = 6*10^9 = 6s 시간초과
• ans = 80000*100000000 이라 long 사용해야함
• stack 사용해서 좀 더 빠르게 풀 수 있다.
  • 명제의 대우
  • 자기가 보는 소 세기 -> 자기를 보는 소 세기
  • `stack.peek()<stk_temp`가 아니라 `stack.peek()<=stk_temp`다.(키가 같은 애들은 볼 수 없음. 더 큰 애들만 가능)
• 조건문 더 깔끔하게 적을 수 있음.

잘한점

• BufferedReader 공부함
• 조건문의 조건비교 최소화(if-else > if-elseif)