티스토리 뷰
문제 링크 ( 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 |
---|
- 20200427
- 20200504
- 20200319
- 20201204
- 20200317
- 20200512
- 20200424
- 20200417
- 20200622
- 20200420
- 20200428
- chapter8
- 20200330
- likelion
- 20200425
- 20200503
- 20200406
- 20200502
- chapter7
- 생활코딩리눅스
- 20200413
- 20200415
- 20200423
- 20200624
- 20200421
- 백준
- 20200403
- 20200429
- 20200510
- 20200804
- Total
- Today
- Yesterday