[백준/Java] 16209 : 수열 섞기

📌 문제 정보

• 번호: 16209
• 제목: 수열 섞기
• 난이도: Gold 3
• 분류: 그리디 알고리즘, 정렬

---

💡 접근 방식

내부 원소는 이웃이 2개 → 절댓값이 큰 값일수록 가운데에 배치해야 이득
음수끼리는 곱이 양수이므로 양수 그룹 / 음수 그룹을 분리해 각자 지그재그 배열 후 연결
처음엔 전체를 단순 내림차순 정렬 후 지그재그를 적용했는데, 음수를 토글 두 번 해서 방향이 고정되는 버그와 음수 그룹 처리 전략 자체가 틀려서 서브태스크 2(양수만)만 통과

---

🔹 단계별 풀이

1단계 – 양수 / 음수 그룹 분리 및 정렬

• 양수(0 포함): 내림차순 정렬 → 가장 큰 값부터 지그재그에 투입
• 음수: 오름차순 정렬(= 절댓값 내림차순) → 절댓값 가장 큰 값부터 지그재그에 투입

입력: [7, -4, 12, -1, 14]
양수: [14, 12, 7]
음수: [-4, -1]  (오름차순 → [-4, -1])

2단계 – 각 그룹 지그재그 배열

정렬된 순서대로 Deque에 번갈아 addFirst / addLast
결과: 절댓값 큰 원소가 가운데, 작은 원소가 양 끝

양수 [14, 12, 7] 지그재그:
  14 → [14]
  12 → [14, 12]
   7 → [7, 14, 12]
결과: 7 14 12

음수 [-4, -1] 지그재그:
  -4 → [-4]
  -1 → [-4, -1]
결과: -4 -1

3단계 – 경계 곱 최소화 후 연결

양수 그룹 끝 ↔ 음수 그룹 앞의 곱은 무조건 음수
양수 최솟값 × 음수 절댓값 최솟값이 경계에 오도록 각 배열 방향 조정 후 연결

양수 배열: [7, 14, 12]  → 끝(12) > 앞(7) 이므로 그대로 (끝이 더 작음)
음수 배열: [-4, -1]     → |-4| > |-1| 이므로 역전 → [-1, -4]

연결: 7 14 12 -1 -4
경계 곱: 12 × (-1) = -12  (최솟값끼리 연결)

---

💻 핵심 코드

// 양수 지그재그
Deque<Integer> posDeque = new ArrayDeque<>();
boolean addToFront = true;
for (int x : positive) {
    if (addToFront) {
        posDeque.addFirst(x);
    } else {
        posDeque.addLast(x);
    }
    addToFront = !addToFront;
}

// 경계 곱 최소화: 양수 최솟값이 posList 끝에, 음수 절댓값 최솟값이 negList 앞에
if (posFirst < posLast) {
    Collections.reverse(posList);
}
if (Math.abs(negFirst) > Math.abs(negLast)) {
    Collections.reverse(negList);
}

---

⏳ 복잡도 분석

• 시간 복잡도: O(N log N)
  • 정렬 O(N log N), 지그재그 및 출력 O(N)
• 공간 복잡도: O(N)
  • 양수/음수 분리 리스트 및 Deque

---

⚠️ 어려웠던 점

• 처음에 전체 배열을 내림차순 정렬하고 조건문으로 음수가 나오면 음수끼리 붙도록 했는데 생각해보니 틀렸습니다.
• 그래서 결국 음수 양수 분리해서 각각 정렬한 뒤에 합쳤습니다.

---

📄 전체 코드

package rtaeho.week02.B16209;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        List<Integer> negative = new ArrayList<>();
        List<Integer> positive = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(st.nextToken());
            if (x < 0) {
                negative.add(x);
            } else {
                positive.add(x);
            }
        }

        positive.sort(Collections.reverseOrder());
        Collections.sort(negative);

        Deque<Integer> posDeque = new ArrayDeque<>();
        boolean addToFront = true;
        for (int x : positive) {
            if (addToFront) {
                posDeque.addFirst(x);
            } else {
                posDeque.addLast(x);
            }
            addToFront = !addToFront;
        }

        Deque<Integer> negDeque = new ArrayDeque<>();
        addToFront = true;
        for (int x : negative) {
            if (addToFront) {
                negDeque.addFirst(x);
            } else {
                negDeque.addLast(x);
            }
            addToFront = !addToFront;
        }

        List<Integer> posList = new ArrayList<>(posDeque);
        List<Integer> negList = new ArrayList<>(negDeque);

        StringBuilder sb = new StringBuilder();

        if (negative.isEmpty()) {
            for (int x : posList) {
                sb.append(x).append(' ');
            }
        } else if (positive.isEmpty()) {
            for (int x : negList) {
                sb.append(x).append(' ');
            }
        } else {
            int posFirst = posList.get(0);
            int posLast = posList.get(posList.size() - 1);
            int negFirst = negList.get(0);
            int negLast = negList.get(negList.size() - 1);

            if (posFirst < posLast) {
                Collections.reverse(posList);
            }
            if (Math.abs(negFirst) > Math.abs(negLast)) {
                Collections.reverse(negList);
            }

            for (int x : posList) {
                sb.append(x).append(' ');
            }
            for (int x : negList) {
                sb.append(x).append(' ');
            }
        }

        System.out.println(sb.toString().trim());
    }
}