SWEA D3 9229 한빈이와 Spot Mart

 

문제링크

SW Expert Academy

 

한빈이와 Sport Mart 는 시간이 넉넉해서 O^2 방법으로 모두 돌아서 계산하는 방법과

왼쪽과 오른쪽으로 포인터를 구분해서 계산하는 방법으로 접근할 수 있다.

 

1)

 

import java.util.*;
import java.io.*;


public class Solution {
	static int n, m;
	public static void main(String[] args) throws Exception {
		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());
			n = Integer.parseInt(st.nextToken());
			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 max = -1;
            // 이중 for문으로 무식하게 다 계산하기
			for(int i = 0; i < n-1; i++) {
				for(int j = i+1; j < n; j++) {
					int tmp = arr[i]+arr[j];
					if(tmp > max && tmp <= m) {
						max = tmp;
					}
				}
			}
			System.out.println("#"+t+" "+max);
		}
	}
}

 

2) 두번째 방법이 좀 특이한데

배열을 먼저 오른차순으로 정렬한다.

1 2 5 8 9 11 이라는 과자가 존재한다고 치자

빨간색 포인터가 파란색 포인터보다 인덱스가 크다면 계속 반복하는 내용이다.

1 + 11  > 10 보다 크다

그러면 빨간색을 왼쪽으로 한칸 옮겨준다.

 

 

1 + 9 는 10이니깐 최대값을 구했으므로 return 한다.

근데 일단 계속 진행해보자 원래라면 여기서 정답이다.

 

9가 없다고 치고

1+ 8 은 10 보다 작다 그래도 9는 정답이 될 수 있으니깐 max로 갱신한다.

 

2+ 8 은 10이다. 또 10이 나와버렸지만 만약 이 값이 이전에 구한 max보다 큰지 비교하고 갱신하는 로직으로

계속 이어진다면 효율적인 투포인터 알고리즘이 된다.

 

class Solution
{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int tc = 1; tc <= t; tc++) {
            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());
            }
            Arrays.sort(arr);
            int pt = 0;
            int pt2 = arr.length-1;
            int max = -1;
            while(pt2 > pt) {
                int tmp = arr[pt] + arr[pt2];
                 
                if(tmp == m) {
                    max = tmp;
                    break;
                }
                 
                if(tmp < m) {
                    max = Math.max(max, tmp);
                    pt++;
                }
                 
                if(tmp > m) {
                    pt2--;
                }
            }
            System.out.println("#"+tc+" "+max);
        }
         
    } // end of public static void main(String[] args) throws Exception