1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
- 생각
PriorityQueue를 이용하면 쉽게 풀 수 있는 문제이다.
1) 카드 묶음을 PriorityQueue에 담는다.
2) 카드 묶음이 1개 이면 0을 출력한다.
3) 카드 묶음이 2개 이상이면 두 카드를 출력 변수에 더 해주고 queue에도 추가시켜준다.
- 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class Main {
static int N;
static PriorityQueue<Long> queue;
static long answer;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
queue = new PriorityQueue<Long>();
answer = 0;
for(int i = 0; i < N; i++)
queue.add(in.nextLong());
TurnQueue();
}
private static void TurnQueue() {
while (queue.size() > 1) {
long firstCard = queue.poll();
long secondCard = queue.poll();
answer += firstCard + secondCard;
queue.add(firstCard + secondCard);
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 20164번 : 홀수 홀릭 호석 (0) | 2021.04.01 |
|---|---|
| [BOJ/JAVA] 백준 1744번 : 수 묶기 (0) | 2021.03.31 |
| [BOJ/JAVA] 백준 4179번 : 불! (0) | 2021.03.26 |
| [BOJ/JAVA] 백준 14888번 : 연산자 끼워넣기 (0) | 2021.03.26 |
| [SW Expert Academy/JAVA] 1767번 프로세서 연결하기 (0) | 2021.03.26 |
