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

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=421&sca=3020

JUNGOL | 불쾌한 날(Bad Hair Day) > 문제은행

---

일열로 있는 소들은 자기보다 작은 소들만 볼수있다.

 

즉 높이가 1 3 5 4 2 인 소들의 집합은

 

0, 0, 2, 1, 0 으로 3인 값을가지고 정답은 이 모두의 합을 출력하는 예제이다.

 

문제는 간단하지만, 그냥 2중 For문을 돌린다면 문제조건이 80000마리의 소가 각각 최대 10억의 높이를 가진다.

 

따라서 적절한 자료구조나, 제한조건으로 시간복잡도를 낮추어야하는 문제이다.

 

---

 
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
 
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        Use_stack();
    }
    
    
    public static void Use_stack() throws Exception {
        ArrayDeque<Integer> dq = new ArrayDeque<Integer>();
         int height[]= new int [80001];
         int N ; 
         long ans =0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine().trim()) +1;
        dq.addLast(Integer.parseInt(br.readLine().trim()));
        
        for(int index = 2 ; index < N ; index++) {
            int temp = Integer.parseInt(br.readLine().trim());
            
            while(dq.peekLast() <= temp){
                dq.pollLast();
                if(dq.isEmpty())break;
            }
            
            ans+=dq.size();
            dq.addLast(temp);
        }
        System.out.println(ans);
    }
 
}
 

---

---

최적화를 위한 나의 노력...

 

결론은 다음과 같다.

 

1. Heap 의 영역에 다가는 횟수 최소화

 

array[index]에 참조하는 횟수가 많을때에 시간이 오래걸린다. 즉 array[index]에 자주 접근할 것 같다면,

이를 local 영역에 저장한후에 사용하자

 

2. scanner 대신에 bufferdreader를 선언하여 입력을 받자.

 

3. stack보다는 arraydeque사용

 

arraydeque는 stack과 queue를 결합해놓은 자료구조이다. 자바에 java.util에 있으며 

 

사용자가 stack으로 사용할 것인지 queue 로사용할 것인지 인지하고 add.frist/last ,pop.first/last, peek.first/last

 

를 잘 사용한다면 시간을 줄일 수 있다.

 

4. 메소드를 나누자

 

메인을최소한으로 줄이고, 메소드를 나누어서 작성하자. 자바는 내부적으로 메소드에대한 최적화가 진행되기 때문에

메소드를 나누어서 작성하는것이 좋다 (적당하게)

 

5. 명제가 참이라면 대우도 참이다.

 

명제를 증명하기 어렵다면, 대우를 증명하는 것으로 문제를 해결해보자.

( 내가 볼수있는소 O(N^2) => 나를 볼수있는 소 )