티스토리 뷰

문제 링크 ( https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW8Wj7cqbY0DFAXN& )

 

문제 핵심 파악

 - 정확히 2봉지를 구입하고, 최대한 들 수 있는 양을 구해야 하기 때문에 구할 수 있는 모든 합 중에서 최대값을 선택해야 한다.

 

소스 코드 

 - 과자 2봉지의 합을 저장하는 배열에서 최대 값을 구하기 위해 ArrayList를 역순으로 정렬한 뒤 최대값(0번 째)을 구했다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 한빈이와 Spot Mart
public class HanbinSpotMart {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T, N, M;
        List<Integer> ansArr;
        int[] arr;
        
        T = Integer.parseInt(br.readLine());
        
        for (int i = 1; i <= T; i++) {
            String[] strArr = br.readLine().split(" ");
            N = Integer.parseInt(strArr[0]); //과자 봉지 개수
            M = Integer.parseInt(strArr[1]); // 최대 무게 합
            arr = new int[N];
            String[] strArr2 = br.readLine().split(" "); 
            for (int j = 0; j < N; j++) {
                arr[j] = Integer.parseInt(strArr2[j]); // 과자 무게 배열에 저장
            }
            
            ansArr = find(N, M, arr); 
            
            Collections.sort(ansArr, Collections.reverseOrder()); //몇개가 들어간지 모르기 때문에 reverseOrder
            if(ansArr.size() == 0) {
                bw.write("#" + i + " " + -1 +"\n");
            } else {
                bw.write("#" + i + " " + ansArr.get(0) +"\n");
            }
            
            
        }
        
        br.close();
        bw.close();
        

    }
    
    static List<Integer> find(int N, int M, int[] arr) {
        List<Integer> ansArr = new ArrayList<Integer>();
        for (int j = N - 1; j >= 0; j--) {
            if (arr[j] < M) {
                for (int z = j - 1; z >= 0; z--) {
                    if (arr[j] + arr[z] <= M) {
                        ansArr.add(arr[j] + arr[z]);
                    }
                }
            }
         }
        
        return ansArr;
    }

}

내 초기 코드

 - 테스트 케이스 192개 밖에 통과 못함

 - (풀이 순서) 과자 봉지들의 무게를 배열에 저장 -> 배열을 오름차순으로 정렬 -> 가장 무겁게 들 수 있는 2개의 과자를 찾아야 하므로 가장 무거운 봉지부터 합을 찾는 반복 실행(find) -> 조건을 만족하면 출력

 - (깨달은 점) 내 코드는 최대값을 보장해주지 않으므로 반례가 존재한다.

ex) 과자의 무게가 {1, 2, 5, 8, 9}로 배열에 저장되어 있고, 최대 합의 무게(M)가 13일 경우 내코드는 9 + 2가 되면 조건을 만족하고 11을 답으로 출력한다, 하지만 최대값은 8 + 5인 13이므로 올바르지 않는 코드로 인해 모든 테스트 케이스를 통과하지 못했다.

 - (고친 점) 따라서 만족하는 합을 모두 저장한다음, 배열을 오름차순하는 방식으로 해야한다.

시간을 절약하려고 오름차순 -> 배열합 저장방식으로 코드를 작성했지만, 결과를 보장하지 못한 코드였다.

package swea.lever.three;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

// 한빈이와 Spot Mart
public class HanbinSpotMart {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T, N, M;
        int ans;
        int[] arr;
        
        T = Integer.parseInt(br.readLine());
        
        for (int i = 1; i <= T; i++) {
        	// 입력 받는 부분
            String[] strArr = br.readLine().split(" ");
            N = Integer.parseInt(strArr[0]);
            M = Integer.parseInt(strArr[1]);
            arr = new int[N];
            String[] strArr2 = br.readLine().split(" "); 
            for (int j = 0; j < N; j++) {
                arr[j] = Integer.parseInt(strArr2[j]);
            }
            
            // 과자 봉지 무게 오름차순 정렬
            Arrays.sort(arr);
            
            // 최대로 들 수 있는 두개 과자 찾기
            ans = find(N, M, arr);
            
            bw.write("#" + i + " " + ans +"\n");
        }
        
        br.close();
        bw.close();
        

    }
    
    // 최대로 들 수 있는 과자 찾기 수행
    static int find(int N, int M, int[] arr) {
        int ans = -1;
        for (int j = N - 1; j >= 0; j--) { // 오름차순으로 정렬되어 있으므로 큰값부터 판단
            if (arr[j] < M) {
                for (int z = j - 1; z >= 0; z--) {
                    if (arr[j] + arr[z] <= M) {
                        ans = arr[j] + arr[z];
                        return ans;
                    }
                }
            }
         }
        
        return ans;
    }

}

* 필요 개념

 - ArrayList 내림차순 정렬 : Collections.sort(배열이름, Collections.reverseOrder())

'Algorithm > SWEA' 카테고리의 다른 글

SWEA 9839. 최고의 쌍 (Java)  (0) 2020.07.01
댓글