문제 링크
문제
티어: 골드 3
알고리즘: 그리디, 덱
준원이는 이 문제를 각색하려고 했는데 너무 귀찮다. 그냥 풀어보도록 하자.
당신은 길이 N인 정수열 a1, …, aN을 가지고 있다. 당신은 이 수열을 재배열하여, 수열에서 인접한 원소의 곱들의 합, 즉 a1a2 + a2a3 + … + aN-1aN을 최대화하려고 한다. 이렇게 재배열한 수열을 하나 출력해 보자.
입력
첫째 줄에는 수열의 길이 N이 주어진다. (2 ≤ N ≤ 500,000)
둘째 줄에는 수열의 각 원소가 공백을 사이에 두고 주어진다. 각 원소의 절댓값은 100만 이하이다.
출력
인접한 원소의 곱들을 최대화한 본 수열의 재배열을 하나 출력하자. 만약 최대화할 수 있는 재배열이 여러 가지 있다면 아무거나 하나 출력하면 된다.
풀이
출력해야 할 것은 인접한 원소의 곱들을 최대화한 재배열된 수열이다.
즉, a1a2 + a2a3 + … + aN-1aN을 최대화하기 위해서는 (큰 값 큰 값)을 해야한다.
a1 a2 + a2 * a3..를 보면 a2는 두 번 곱해지고 있다. 그러면 이 a2는 a1, a3보다는 큰 값을 가져야 한다.
예를 들어 1 3 5라고 했을 때 1 5 3으로 재배열해야 된다.
그리고 a1, a3중에 더 큰 값에 그 다음으로 큰 값을 붙여주고, 이를 반복하면 된다.
예제 입력을 보면
4
7 7 12 14
인데
내림 차순하면 14 12 7 7 이다.
14 양 옆에 2번 째로 큰 값과 3번 째로 큰 값을 붙여야한다.
그래서 12 14 7이 된다.
그리고 2번 째로 큰 값에는 그 다음 큰 값을 붙여주고, 3번 째로 큰 값에는 그 다음 큰 값을 붙여주면 최종적으로 7 12 14 7된다.
여기서 deque가 사용되는데 계속 앞 뒤로 붙이는 패턴이기 때문이다.
처음에 나는 - 경우는 생각하지 않아서 틀렸다. 이후 -가 들어올 수 있다는 것을 알고 코드를 고쳐줬다.
-원소도 생각해 보면 똑같다. -원소 2개를 곱하면 +이기 때문에 +원소와 같은 패턴으로 재배열을 하는데 중요한 점은 +원소와 -원소가 합쳐지는 구간이다.
이 구간은 곱하면 -이기 때문에 이 -값은 최소화를 해야한다.
그러기 위해서는 합치는 구간에서 가장 작은 +원소에 가장 큰 -원소부터 차례대로 합치면 된다.
어차피 가장 작은 +원소도 맨 앞이거나 맨 뒤이고, 가장 큰 -원소도 맨 앞아니면 맨 뒤이다. 그렇기 때문에 이를 고려해서 합쳐주면 최대화로 재배열된 배열을 출력해 줄 수 있다.
예를 들어
7
7 7 12 14 -8 -1 -5
이를 재배열 하면 다음과 같다.
+는 7 12 14 7이고
-는 -5 -8 -1이다.
이를 합칠 때 고려할 부분은 +에서 가장 작은 부분 여기서는 맨 앞이고
-부분에서 가장 큰 부분 여기서는 맨 뒤이다.
그래서 합쳐줄 때 +에 맨 앞에 -에 맨 뒤부터 차례대로 연결해 주면 된다. 그래서 답은
-5 -8 -1 7 12 14 7이 된다.
시간 복잡도는 O(N)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static ArrayList<Integer> plusS = new ArrayList<>();
static ArrayList<Integer> minusS = new ArrayList<>();
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
int v = Integer.parseInt(st.nextToken());
if(v > 0) {
plusS.add(v);
} else {
minusS.add(v);
}
}
Collections.sort(plusS, Collections.reverseOrder());
Collections.sort(minusS);
Deque<Integer> plusDeque = new ArrayDeque<>();
Deque<Integer> minusDeque = new ArrayDeque<>();
if(plusS.size() != 0) {
plusDeque.addFirst(plusS.get(0));
for(int i=1; i<plusS.size(); i+= 2) {
if(i < plusS.size()) {
plusDeque.addFirst(plusS.get(i));
}
if(i + 1 < plusS.size()) {
plusDeque.addLast(plusS.get(i + 1));
}
}
}
if(minusS.size() != 0) {
minusDeque.addFirst(minusS.get(0));
for(int i=1; i<minusS.size(); i+=2) {
if(i < minusS.size()) {
minusDeque.addFirst(minusS.get(i));
}
if(i + 1 < minusS.size()) {
minusDeque.addLast(minusS.get(i + 1));
}
}
}
boolean pFront = false;;
if(plusS.size() % 2 == 0) {
pFront = true;
}
boolean mFront = false;
if(minusS.size() % 2 == 0) {
mFront = true;
}
Deque deque = new ArrayDeque<>();
while(plusDeque.peekFirst() != null) {
deque.addLast(plusDeque.pollFirst());
}
while(minusDeque.peekFirst() != null) {
int v = 0;
if(mFront) {
v = minusDeque.pollFirst();
} else {
v = minusDeque.pollLast();
}
if(pFront) {
deque.addFirst(v);
} else {
deque.addLast(v);
}
}
StringBuilder sb = new StringBuilder();
while(deque.peekFirst() != null) {
sb.append(deque.pollFirst()).append(" ");
}
System.out.println(sb.toString().trim());
}
}