[Softeer Level.3] Phi Squared

문제

언어	시간	메모리
C++	1초	1024MB
JavaScript	5초	1024MB
C	1초	1024MB
Java	3초	1024MB
Python	5초	1024MB
Kotlin	3초	1024MB
Swift	1초	1024MB

선아는 최근에 어떤 미생물을 연구하고 있다. 선아는 연구 과정에서 이 미생물 여러 마리를 한 줄로 나열하면 미생물이 한 마리만 남을 때까지 다음 규칙들에 따라 미생물들이 서로 흡수한다는 사실을 알아냈다.

1. 하루에 한 번 줄의 맨 앞에 있는 미생물부터 각 미생물은 차례대로 인접한 미생물 중 자신보다 크기가 작거나 같은 것들을 전부 흡수한다. 다른 미생물을 흡수한 경우, 미생물의 크기는 흡수한 미생물의 크기의 합만큼 커진다.

2. 흡수당한 미생물은 사라지며 행동할 수 없다. 즉, 3,2,1의 크기를 가지는 세 마리의 미생물들이 있는 경우 2는 자신의 차례가 오기 전에 3에게 흡수당하기 때문에 하루가 지난 후 남아있는 미생물들의 크기는 5,1이 된다.

3. 흡수하는 미생물은 하루에 흡수할 모든 미생물을 한 번에 흡수한다. 즉, 3,4,5의 크기를 가지는 세 마리의 미생물들이 있고 4의 차례인 경우 4는 3만 흡수한다. 4가 3을 흡수해서 7이 된 후 같은 날 5를 흡수하는 행동은 불가능하다. 따라서 하루가 지난 후 남아있는 미생물들의 크기는 7,5가 된다.

선아에게는 이 미생물이 N마리 있다. 이 N마리의 미생물들이 한 줄로 나열되었을 때 마지막에 남는 미생물의 최종 크기와 초기 위치를 찾는 프로그램을 작성해 보자.

---

제약조건
1≤N≤500000
각 미생물의 초기 크기는 1 이상 N 이하의 정수이다. 또한 같은 초기 크기를 가지는 두 미생물은 존재하지 않는다.

입력형식
첫 번째 줄에 미생물들의 수 N이 주어진다.
두 번째 줄에 미생물들의 초기 크기를 나타내는 N개의 정수 a1​,a2​,…,aN​가 공백으로 구분되어 주어진다. ai​는 i번째 미생물의 초기 크기를 나타낸다.

출력형식
첫 번째 줄에 마지막에 남는 미생물의 최종 크기를 출력한다.
두 번째 줄에 그 미생물의 초기 위치를 출력한다.

입력예제1

5
4 1 3 2 5

출력예제1

15
5

과정 설명
다음과 같은 순서로 미생물들이 합쳐지게 됩니다. (위치, 크기)는 초기 위치가 해당 위치인 미생물의 현재 크기를 의미합니다.

• 초기 상태: (1, 4) (2, 1) (3, 3) (4, 2) (5, 5)
• 1일 후: (1, 5) (5, 10)
• 2일 후: (5, 15)

따라서 답은 15 5 입니다.

입력예제2

3
1 2 3

출력예제2

6
3

---

문제 접근 방식

1. Deque를 이용한다:

2. 초기 설정:

   • 미생물의 초기 위치와 크기를 저장한 후 curDeque에 삽입합니다.

3. 주변 미생물 흡수:

   • 주변을 흡수할 차례가 된 미생물 객체 (순서, 크기)을 차례대로 pollFirst 합니다.
   • nextDeque에 담겨있는 마지막 미생물 객체와 큐에 담겨있는 첫 번째 미생물 객체를 현재 미생물과 크기를 비교합니다.
   • 주변의 미생물이 현재 차례의 미생물 크기보다 작다면 모두 흡수한 뒤 nextDeque에 담습니다.

4. Deque 관리:

   • 현재 일차가 끝나면 curDeque를 비우고 nextDeque를 curDeque로 설정하여 다음 일차를 준비합니다.
   • 이 과정을 큐에 한 개의 미생물이 남을 때까지 반복합니다.

소스코드

import java.io.*;
import java.util.*;

/**
 * 소프티어 Phi Squared - Deque
 * https://softeer.ai/practice/7697
 */
public class Main {
    // 미생물을 나타내는 클래스
    static class Microbe {
        int idx;   // 미생물의 초기 위치 인덱스
        long size; // 미생물의 크기

        public Microbe(int idx, long size) {
            this.idx = idx;
            this.size = size;
        }
    }

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

        int N = Integer.parseInt(br.readLine()); // 미생물의 개수

        Deque<Microbe> curDeque = new LinkedList<>(); // 현재 일차에서 처리할 미생물
        Deque<Microbe> nextDeque = new LinkedList<>(); // 다음 일차로 넘어갈 미생물

        // 초기 미생물 정보 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            curDeque.offerLast(new Microbe(i + 1, Long.parseLong(st.nextToken())));
        }

        // 큐에 한 개의 미생물만 남을 때까지 반복
        while (curDeque.size() > 1) {
            while (!curDeque.isEmpty()) {
                Microbe curMicrobe = curDeque.pollFirst(); // 현재 처리할 미생물
                long curSize = curMicrobe.size;

                // 다음 일차 미생물 큐에 있는 미생물이 현재 미생물보다 작은 경우 합치기
                if (!nextDeque.isEmpty() && nextDeque.peekLast().size <= curMicrobe.size) {
                    Microbe lastMicrobe = nextDeque.pollLast();
                    curSize += lastMicrobe.size;
                }

                // 현재 일차 미생물 큐에 있는 다음 미생물이 현재 미생물보다 작은 경우 합치기
                if (!curDeque.isEmpty() && curDeque.peekFirst().size <= curMicrobe.size) {
                    Microbe firstMicrobe = curDeque.pollFirst();
                    curSize += firstMicrobe.size;
                }

                // 합쳐진 결과를 다음 일차 큐에 추가
                nextDeque.addLast(new Microbe(curMicrobe.idx, curSize));
            }

            // 다음 일차 준비
            curDeque = nextDeque;
            nextDeque = new LinkedList<>();
        }

        // 최종 남은 미생물 정보 출력
        Microbe answer = curDeque.pollFirst();
        System.out.println(answer.size); // 남은 미생물의 크기
        System.out.println(answer.idx);  // 남은 미생물의 초기 인덱스
    }
}

자바의 Deque

Deque는 "Double Ended Queue"의 약자로, 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 큐입니다. 자바에서 Deque 인터페이스를 통해 다양한 구현체를 사용할 수 있습니다. 대표적인 구현체로는 ArrayDeque와 LinkedList가 있습니다.

Deque 인터페이스

Deque 인터페이스는 다음과 같은 메서드를 제공합니다:

요소 추가

• void addFirst(E e): 지정된 요소를 덱의 앞쪽에 추가합니다.
• void addLast(E e): 지정된 요소를 덱의 뒤쪽에 추가합니다.
• boolean offerFirst(E e): 지정된 요소를 덱의 앞쪽에 추가하고 성공 여부를 반환합니다.
• boolean offerLast(E e): 지정된 요소를 덱의 뒤쪽에 추가하고 성공 여부를 반환합니다.

요소 제거

• E removeFirst(): 덱의 앞쪽에서 요소를 제거하고 반환합니다.
• E removeLast(): 덱의 뒤쪽에서 요소를 제거하고 반환합니다.
• E pollFirst(): 덱의 앞쪽에서 요소를 제거하고 반환하며, 덱이 비어 있으면 null을 반환합니다.
• E pollLast(): 덱의 뒤쪽에서 요소를 제거하고 반환하며, 덱이 비어 있으면 null을 반환합니다.

요소 조회

• E getFirst(): 덱의 앞쪽에 있는 요소를 반환합니다.
• E getLast(): 덱의 뒤쪽에 있는 요소를 반환합니다.
• E peekFirst(): 덱의 앞쪽에 있는 요소를 반환하며, 덱이 비어 있으면 null을 반환합니다.
• E peekLast(): 덱의 뒤쪽에 있는 요소를 반환하며, 덱이 비어 있으면 null을 반환합니다.

ArrayDeque vs LinkedList

ArrayDeque와 LinkedList는 각각 Deque 인터페이스를 구현한 클래스입니다.

• ArrayDeque는 배열 기반의 덱 구현체로, 요소를 임의 접근하는 데 빠른 속도를 자랑하며, 대체로 더 효율적입니다.
• LinkedList는 링크드 리스트 기반의 덱 구현체로, 양쪽 끝에서의 삽입 및 삭제가 매우 빠릅니다.

둘 중 어느 것을 사용할지는 구체적인 사용 사례와 성능 요구사항에 따라 다릅니다.