[백준 - 10975][GOLD 5][해설 X] - 데크 소트 2 (JAVA)

문제 링크

---

https://www.acmicpc.net/problem/10975

 

문제

---

데크는 큐와 비슷하지만, 앞과 뒤 양쪽에서 자료를 넣거나 뺄 수 있는 자료구조이다.

N개의 수가 주어졌을 때, 첫 번째 수부터 마지막 수까지 순서대로 아래 세 가지 중에 한 방법을 이용해 데크에 넣어야 한다.

1. 수를 존재하는 데크중 하나의 맨 앞에 넣는다.
2. 수를 존재하는 데크중 하나의 맨 뒤에 넣는다.
3. 새로운 데크를 만들어서 그 곳에 수를 넣는다.

위의 방법을 이용해서 모든 수를 적절히 데크에 넣은 다음, 모든 데크를 적절히 이어 붙여 오름차순으로 만들려고 한다. 이때, 필요한 데크 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 수의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 한 줄에 하나씩 주어진다. 각 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.  

 

출력

---

첫째 줄에 데크 소트를 할 때, 필요한 데크의 최소 개수를 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        List<Integer> list = new ArrayList<>();
        List<Integer> sorted = new ArrayList<>();

        for(int i=0;i<N;i++){
            int num = Integer.parseInt(br.readLine());
            list.add(num);
            sorted.add(num);
        }

        Collections.sort(sorted);

        int offset = 1000;  //인덱스로 접근하기 위해 최소값(-1000)을 시작인덱스(0)으로 만들기 위한 오프셋
        int[]next = new int[2001];
        int[]prev = new int[2001];

        //초기화
        Arrays.fill(next,Integer.MAX_VALUE);
        Arrays.fill(prev,Integer.MAX_VALUE);

        //수의 오른쪽값과 왼쪽값을 갱신
        for(int i=0;i<sorted.size();i++){
            if(i+1 < sorted.size()){
                next[sorted.get(i)+offset] = sorted.get(i+1);
            }
            if(i-1 >= 0){
                prev[sorted.get(i)+offset] = sorted.get(i-1);
            }
        }

        List<Deque<Integer>> dequeList = new ArrayList<>();

        for(int i=0;i<list.size();i++){
            boolean valid = false;

            //deque를 순회하며 해당 숫자를 바로 옆에 놓을 수 있는지 판다
            for(Deque<Integer> deque : dequeList){
                //오른쪽에 놓을 수 있는지 판단
                if(deque.peekFirst() == next[list.get(i)+offset]){
                    deque.addFirst(list.get(i));
                    valid=true;
                    break;
                }
                //왼쪽에 놓을 수 있는지 판단
                else if(deque.peekLast() == prev[list.get(i)+offset]){
                    deque.addLast(list.get(i));
                    valid=true;
                    break;
                }
            }

            //아무데도 놓지 못했다면 새로운 deque생성
            if(!valid){
                Deque deque = new ArrayDeque();
                deque.add(list.get(i));
                dequeList.add(deque);
            }
        }

        //데큐 개수 출력
        System.out.println(dequeList.size());
    }
}

 

 

실행 결과

---

 

팁

---

• 문제를 풀기 전에 N의 크기를 파악하여 구현으로 가능한지 확인하자.