[알고리즘풀이]백준 1715: 카드 정렬하기 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이전에 알고리즘 스터디에서 JAVA를 이용해 백준 1715번 카드 정렬하기를 풀었습니다. 이를 정리해보고자 합니다.

1715번: 카드 정렬하기

본문

1) 문제

 

2) 과정

이번 문제는 꽤 많이 어려웠습니다. 생각을 코드로 표현하는 과정이 쉽지 않아서 5시간 정도 매달려서 풀어낸 문제입니다.

 

문제를 푸는 데 사용된 아이디어는 다음과 같습니다.

• 최소의 비교를 하기 위해서는 최소의 값을 더해나가야함.
• 10, 30, 50이 주어졌다고 했을 때,
  • 10+50 을 하고 30을 더하면 1차비교로 (10+50), 2차비교로 (60+30)로 총 150임.
  • 반면에 10+30을 하고 50을 더하면 1차비교로 (10+30), 2차비교로 (40+50)으로 130임.
• 여기서 알 수 있는 핵심은 바로 1차비교(앞선 비교)의 값을 최소로 만들어야 최소의 값으로 더해나갈 수 있다.

이번 문제도 main에 Input, Initialize, Logic, Output을 넣어 구성을 했습니다.

 

2-1) main

    public static void main(String[] args) throws IOException {
    	// Input
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());

        PriorityQueue<Long> intList = new PriorityQueue<Long>();
        for(int i =0;i<n;i++) intList.add(Long.parseLong(reader.readLine()));

	// Initialize
        long answer = 0;
        
        // Logic
        while(intList.size()>=2){ // 비교가 가능하려면 2개이상이어야하기 떄문
            long tmp1 = intList.poll();
            long tmp2 = intList.poll();

            //앞의 두개를 더해서 기존의 답에 추가하고
            answer +=tmp1+tmp2;
            // 두 값의 합을 큐에 다시 추가해서 넣어줌. (값의 합을 반영하기 위함)
            intList.add(tmp1+tmp2);
        }
        
        // Output
        System.out.println(answer);
    }

먼저 Input부분에서는 입력 받은 카드 묶음의 수 n과 카드 묶음의 크기 intArr을 받아옵니다.

 

Initialize 부분에서는 정답으로 출력할 최소비교횟수 answer을 0으로 초기셋팅해줍니다.

 

Logic부분에서는 비교가 가능하다면, 두개의 값을 꺼내 기존의 답에 추가하고, 추가된 값을 intList에 넣어줌으로써, 더해진 묶음과 다른 묶음을 묶음이 1개만 남을 때까지 비교할 수 있습니다.

 

Output부분에서는 Logic의 결과로 나온 answer을 출력해줍니다.

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

package sujeong.greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ1715 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());

        PriorityQueue<Long> intList = new PriorityQueue<Long>();
        for(int i =0;i<n;i++) intList.add(Long.parseLong(reader.readLine()));


        long answer = 0;
        while(intList.size()>=2){ // 비교가 가능하려면 2개이상이어야하기 떄문
            long tmp1 = intList.poll();
            long tmp2 = intList.poll();

            //앞의 두개를 더해서 기존의 답에 추가하고
            answer +=tmp1+tmp2;
            // 두 값의 합을 큐에 다시 추가해서 넣어줌. (값의 합을 반영하기 위함)
            intList.add(tmp1+tmp2);
        }
        System.out.println(answer);
    }
}

 

이번 기회로 자료구조 공부의 필요성을 크게 느꼈습니다. 문제를 풀며 넣었던 것을 반복해서 넣는 경우에는 리스트말고도 queue나 stack을 생각해보자는 마음가짐을 갖게 되었는데, 이전에는 배열 아니면 ArrayList로만 값을 넣으려 했습니다. 하지만 이번 문제를 풀기위해 찾아다녀 본 후에는 Queue, Stack, LinkedList, LinkedHashSet 등 다양한 구조의 필요성을 머리로만 이해한 게 아닌 몸소 느낄 수 있었습니다. 그렇게 알게 된게 PriorityQueue로 sort가 귀찮은 Queue와 달리 poll을 오름차순으로(comparator로 바꿀수도 있다.) 할 수도 있어 이번 문제에서 유용하게 사용하였습니다.

 

깃헙의 주소는 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/greedy/BOJ1715.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비