[Java] SWEA 9229번: 한빈이와 Spot Mart

문제

한빈이는 퇴근길에 스팟마트에 들러 과자 두 봉지를 사서 양 손에 하나씩 들고 가려고 한다.

스팟마트에는 N개의 과자 봉지가 있으며, 각 과자 봉지는 ai그램의 무게를 가진다.

배가 많이 고픈 한빈이는 최대한 양이 많은 (무게가 많이 나가는) 과자 봉지를 고르고 싶으나,

과자 두 봉지의 무게가 M 그램을 초과하면 무거워서 과자를 들고 다닐 수 없다.

한빈이가 들고 다닐수 있는 과자들의 최대 무게 합을 출력하라. 한빈이는 과자를 “정확히” 두 봉지 사야 함에 유의하라.

[입력]

첫 번째 줄에 테스트 케이스의 수 TC 가 주어진다.

이후 TC 개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.

첫 번째 줄에 과자 봉지의 개수와 무게 합 제한을 나타내는 자연수 N, M이 주어진다.
(2 ≤ N ≤ 1000 , 2 ≤ M ≤ 2000000)

이후 N개의 줄에 각 과자봉지의 무게 가 주어진다. (1 ≤ ai ≤ 1000000)

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트 케이스 번호를 의미, 1부터 시작)를 출력하고,

한빈이가 들고 갈 수 있는 과자 봉지의 무게 합 최대를 출력하라.

만약 한빈이가 두 과자를 들고 갈 방법이 없는 경우에는 -1을출력한다.

---

일단 생각하기!

이 문제는 나만의 힘으로 풀어본 것이 아닌, 투 포인터를 배우기 위해 풀이를 참고한 문제다.
투 포인터는 ① 처음과 끝에서 시작 ② 동시에 시작하나 속도가 다름
이 두 가지가 있다고 들었는데 이 문제의 경우는 ①의 방법을 사용했다.
이중 for문으로 풀이한다면 시간복잡도가 O(N의제곱)이 되는데 투포인터를 사용한다면 O(N)까지도 된다. 이 문제에서는 잘 모르겠다.
② 경우의 문제도 얼른 풀어봐서 투 포인터를 익혀야겠다!

• 투 포인터 사용을 위해 과자 무게 배열을 Array.sort를 이용해 오름차순 정렬해준다.
• start 인덱스의 무게와 end 인덱스의 무게 합이 무게 합 제한 M보다 클 경우 end--를 해주고, 작거나 같을 경우 max를 비교한 뒤, start++를 해준다.

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 
 * @author 김유나
 * 2023-08-08
 * [문제] SWEA 9229번 한빈이와 Spot Mart
 * - 최대한 양이 많은, 그러나 M 그램을 초과하면 안되도록 과자 두 봉지를 사는 프로그램을 구현하라.
 * [아이디어]
 * - 과자 무게 배열을 오름차순으로 정렬하여 투포인터를 사용하여 한빈이가 들 수 있는, 가장 큰 값을 구한다.
 *
 * 메모리 : 25,496kb 실행 시간 : 142ms
 */
public class D3_9229_한빈이와SpotMart_김유나 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int TC = Integer.parseInt(br.readLine()); // 테스트 케이스
		
		for (int t = 1; t <= TC; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken()); // 과자 봉지 개수
			int M = Integer.parseInt(st.nextToken()); // 무게 합 제한
			int arr[] = new int[N]; // 과자 봉지 무게 배열
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			
			// 투포인터 사용
			int start = 0; // 시작 포인터
			int end = N - 1; // 끝 포인터
			int max = -1; // 방법이 없는 경우 -1 출력 위해
			
			Arrays.sort(arr); // 과자 무게 배열 오름차순 정렬
			
			while (start != end) { // start와 end가 같지 않을때까지 : start는 가장 앞, end는 가장 뒤에서부터 오므로
				if (arr[start] + arr[end] > M) { // 무게 합 제한보다 클 경우
					end--; // end를 하나씩 앞으로
				}
				else { // 무게 합 제한보다 작거나 같을 경우
					max = Math.max(max, arr[start] + arr[end]); // max와 비교
					start++; // start를 하나씩 앞으로
				}
			}
			
			System.out.println("#" + t + " " + max);
		}
	}
}