[그리디] 백준 15903번 카드 합체 놀이 - JAVA

 

왜 Arrays.sort를 계속 써도 시간초과가 나지 않는지 의문이었던 문제...

 

 

---

1. 출처

---

 

https://www.acmicpc.net/problem/15903

15903번: 카드 합체 놀이

 

 

• 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()의 시간복잡도 비교

 

 

그런데 다른 개발자들이 짠 코드를 보니까 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