[그리디] 백준 15903번 카드 합체 놀이 - JAVA
왜 Arrays.sort를 계속 써도 시간초과가 나지 않는지 의문이었던 문제...
1. 출처
https://www.acmicpc.net/problem/15903
15903번: 카드 합체 놀이
첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1,
www.acmicpc.net
- N개의 카드가 주어짐
- 2장의 카드를 더한 값을 2장의 카드에 적용 == 카드합체
- M번 카드 합체를 진행했을 때 모든 카드의 합이 가장 적게 나올 수 있는 경우를 구할 것
2. 설계
1. 타입은 long으로
카드 수는 최대 1000개가 나올 수 있고, 카드에 적힌 수는 최대 백만까지 나올 수 있다. 때문에 M번 더할 값은 int 범위 21억을 벗어날 가능성이 있다. 카드 합체도 최대 15000번이기 때문에 카드 수를 저장하는 배열이나 모든 수의 합을 저장하는 결과값은 long으로 진행한다.
long[] card = new long[st.countTokens()];
long sum = 0;
ArrayList를 사용하는 것이면 다음과 같이 쓴다.
List<Long> card = new ArrayList<>();
long sum = 0;
2. 합체는 작은수부터 진행한다.
작은수끼리 2장 더해나가야 최종적으로 최대한 작은 총합을 구할 수 있다. 이런 이유로 sort 과정이 필수이다.
Arrays.sort는 최악으로 O(N^2)이 나올 수 있기 때문에 최악에도 O(nlog(n))의 시간복잡도를 갖는 Collection.sort를 이용하고자 했다.
for(int i=0;i<M;i++){
Collections.sort(card);
long sum = card.get(0) + card.get(1);
card.add(sum);
card.add(sum);
card.remove(0);
card.remove(0);
}
0번에 있는 것을 빼면 1번에 있는게 0번으로 오기 때문에 0번 인덱스를 2번 빼준 것이다.
이렇게 정렬을 해주면 최종 시간은 224ms가 도출된다.
참고 : https://yuja-kong.tistory.com/183
[Java] Arrays.sort()와 Collections.sort()의 시간복잡도 비교
알고리즘을 풀다가 흔하디 흔한 sort() 정렬의 차이가 궁금해졌다. 보편적으로 배열을 정렬할 땐 Arrays.sort(), 컬렉션(List,Set..)을 정렬할 땐 Collections.sort()를 사용한다. 찾아보니 같은 sort 메서드지
yuja-kong.tistory.com
그런데 다른 개발자들이 짠 코드를 보니까 Arrays.sort도 되는 것이다...?
for(int i=0;i<M;i++){
Arrays.sort(card);
long sum = card[0] + card[1];
card[0] = sum;
card[1] = sum;
}
이렇게 정렬을 해주면 최종 시간은 536ms가 도출된다. 테스트케이스에 최악의 경우가 없는 것인가...? 아직도 왜 되는지 아리쏭하다 ㅎㅎ
3. 전체 코드
1. Collection.sort를 사용한 코드 - 33328 KB, 244 ms
import java.util.*;
import java.io.*;
class Main {
static int N;
static List<Long> card;
public static void main(String[] args) throws Exception {
// 카드수는 최대 1000개, 카드 숫자는 백만까지 나올 수 있음 -> long(카드, 결과)
// 합체는 최대 15000번
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String NM = br.readLine();
StringTokenizer st = new StringTokenizer(NM," ");
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
String cards = br.readLine();
st = new StringTokenizer(cards," ");
card = new ArrayList<>();
for(int i=0;i<N;i++){
card.add(Long.parseLong(st.nextToken()));
}
//입력 끝
for(int i=0;i<M;i++){
Collections.sort(card);
long sum = card.get(0) + card.get(1);
card.add(sum);
card.add(sum);
card.remove(0);
card.remove(0);
}
//3. 결과
long sum = 0;
for(int i=0;i<N;i++){
sum+=card.get(i);
}
System.out.println(sum);
}
}
2. Arrays.sort를 사용한 코드 - 30436 KB, 536 ms
import java.util.*;
import java.io.*;
class Main {
static int N;
static long[] card;
public static void main(String[] args) throws Exception {
// 카드수는 최대 1000개, 카드 숫자는 백만까지 나올 수 있음 -> long(카드, 결과)
// 합체는 최대 15000번
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String NM = br.readLine();
StringTokenizer st = new StringTokenizer(NM," ");
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
String cards = br.readLine();
st = new StringTokenizer(cards," ");
card = new long[st.countTokens()];
for(int i=0;i<N;i++){
card[i] = Long.parseLong(st.nextToken());
}
//입력 끝
for(int i=0;i<M;i++){
Arrays.sort(card);
long sum = card[0] + card[1];
card[0] = sum;
card[1] = sum;
}
//3. 결과
long sum = 0;
for(int i=0;i<N;i++){
sum+=card[i];
}
System.out.println(sum);
}
}
[시간 체크 테스트 케이스]
1000 15000
3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9 3 2 6 3 2 6 3 2 6 9