[알고리즘] 2164번

1차 시도.

시간초과로 장렬히 전사하다.

import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        
        ArrayList<Integer> cards = new ArrayList<>();
        
        for(int i=1; i<=N; i++){
            cards.add(i);
        }
        
        for(int i=0; cards.size() != 1; i++){
            cards.remove(0);
            int temp = cards.get(0);
            cards.remove(0);
            cards.add(temp); // 와 링크드리스트쓰면 빠를텐데...
        }
        System.out.println(cards.get(0));
        input.close();
    }
}

시간초과로 장렬히

초기화시켜주고, 매번 빼고 이러면 시간복잡도가 O(N^2)가된다. 시간초과임.

Deque를 써보자.

 

Deque를 사용할때, 요소를 추가하는 상황이있다고하자.

`add`보다는 `offer`를 많이 사용한다고한다. 왜? 예외상황이 발생했을 때, offer의 경우 false를 반환한다.

마찬가지로, 제거하는 방법도 아래와같다. poll을 사용해보자.

remove()	예외 ❌
poll()	null ⭕

 

 

 

Deque 명령메서드

push_front	offerFirst
push_back	offerLast
pop_front	pollFirst
pop_back	pollLast
front	peekFirst
back	peekLast

 

이후 풀이한 Deque - 10866

import java.util.*;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Deque<Integer> deque = new ArrayDeque<>();
        int num=0;
        
        for(int i=0; i<N; i++){
            String s = sc.next();
            switch(s){
                case "push_front" :
                    num = sc.nextInt();
                    deque.offerFirst(num);  
                    break;
                case "push_back" : 
                    num = sc.nextInt();
                    deque.offer(num);
                    break;
                case "pop_front" :
                    if(deque.isEmpty()){
                        System.out.println("-1");
                        break;
                    }
                    System.out.println(deque.poll());
                    break;
                case "pop_back" : 
                    if(deque.isEmpty()){
                        System.out.println("-1");
                        break;
                    }
                    System.out.println(deque.pollLast());
                    break;
                case "size" :
                    System.out.println(deque.size());
                    break;
                case "empty" :
                    if(deque.isEmpty()){
                        System.out.println("1");
                    }
                    else{
                        System.out.println("0");
                    }
                    break;
                case "front" : 
                    if(deque.isEmpty()){
                        System.out.println("-1");
                        break;
                    }
                    System.out.println(deque.peek());
                    break;
                case "back" :
                    if(deque.isEmpty()){
                        System.out.println("-1");
                        break;
                    }
                    System.out.println(deque.peekLast());
                    break;
                    
            }
        }
        sc.close();
    }
}