[백준/Java] 9024번 두 수의 합

 

문제 풀이

1. HashMap 사용(메모리 초과)

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		for(int t=0; t<T; t++) {
			st = new StringTokenizer(bf.readLine());
			int n = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			
			int[] arr = new int[n];
			st = new StringTokenizer(bf.readLine());
			for(int i=0; i<n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			Arrays.sort(arr);
			
			int start = 0;
			int end = n-1;
			
			HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
			while(start < end) {
				int sum = arr[start] + arr[end];
				int abs = Math.abs(arr[start] + arr[end] - K);

				if(map.containsKey(abs)) {
					map.replace(abs, map.get(abs)+1);
				}else {
					map.put(abs, 1);
				}
				if(sum >= K) {
					end--;
				}else {
					start++;
				}
			}

			int minKey = Collections.min(map.keySet());
			System.out.println(map.get(minKey));
			
		}
	}
}

한 줄 씩 설명 없이 전체 설명을 해보자면

일단 두 포인터, HashMap을 사용했다.

 

두 포인터로 두 값의 합에서 K를 뺀 절댓값을 map에 key 값으로 넣었고, value 값에는 카운트 값을 넣었다.

그리고 Collections.main을 사용해서 map의 최소 key 값에 대한 value 값을 출력하도록 했다.

이렇게 했더니 메모리초과가 났다. 아무래도 HashMap에서 많은 메모리를 잡아먹은 듯 했다.

 

그래서 HashMap 없이 다른 방법이 없을까하다가, 최소값을 담을 변수를 하나 만들어서 값이 최소가 될 때마다 갱신하고 카운트를 증가시키면 어떨까? 라고 생각했고 통과했다.

 

⭐⭐⭐⭐⭐그리고 꿀팁.⭐⭐⭐⭐⭐

자바로 푸는 사람들 JAVA8 말고 JAVA11로 언어 설정하면 통과할 확률 높음 !!!

나도 질문 게시판에서 본 꿀팁임 !! ㅎㅎ

 

 

2. 변수 사용(통과)

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());

int T = Integer.parseInt(st.nextToken());
for(int t=0; t<T; t++) {
    String [] input = bf.readLine().split(" ");
    int n = Integer.parseInt(input[0]);
    int K = Integer.parseInt(input[1]);

    String[] inputArr = bf.readLine().split(" ");			
    int[] arr = new int[n];

    for(int i=0; i<n; i++) {
        arr[i] = Integer.parseInt(inputArr[i]);
    }
    Arrays.sort(arr);

1. 문제에서 주어진 입력을 받는다.

n개의 정수를 arr 배열에 넣었고, 오름차순 정렬을 했다.

 

int start = 0;
int end = n-1;

int min = Integer.MAX_VALUE;
int cnt = 0;

2. start, end로 두 포인터를 만들었고,

start는 0, end는 n-1로 둬서 배열의 양쪽 끝에서부터 두 포인터를 시작하도록 했다.

 

최소값을 담기 위해 min 변수를 생성해서 정수의 최댓값을 대입시켰고, 최소값이 몇 개 있는지 세기 위해 cnt 변수를 생성했다.

 

while(start < end) {
    int sum = arr[start] + arr[end];
    int abs = Math.abs(arr[start] + arr[end] - K);

3. while 문을 빠져나올 수 있는 조건은 start < end 이고,

start와 end는 각각 인덱스를 의미하기 때문에 arr[start] + arr[end]로 현재 두 포인터 위치에 있는 값의 합을 sum에 담았고,

우리가 찾아야 하는 값이 두 값의 합이 K에 가까운지 확인하기 위해 (합 - K)를 abs 변수에 담았다.

 

이 때 주의할 점이 있다.

K = 4일 때,

{-7, -2, 5, 12} 인 서로 다른 정수가 있다고 해보자.

이 때 두 수의 합이 4가 되는 것은 없으므로 4에 가까운 정수를 찾아야한다.

 

두 수의 합이 4에 가장 가까운 쌍은 아래와 같다.

sum = -2 + 5 = 3
sum = -7 + 12 = 5

 

arr[start] + arr[end] - K 에 대입을 하면 각각

3 - 4 = -1

5 - 4 = 1 이 된다.

 

이 때, 두 쌍은 부호 상관 없이 모두 K=4와 1씩 차이가 난다.

그렇기 때문에 K에서 가장 가까운 수로 만족하는 두 수는 (-2,5) , (-7,12) 두 쌍이므로 이 문제에서 답은 2가 된다.

 

-1, 1은 엄연히 다른 수이지만 K=4와 1씩 차이 나기 때문에

(두 수의 합 - K)에 절댓값(abs)을 씌워야 한다.

 

if(abs == min) {
    cnt++;
}else if(min > abs){
    cnt = 1;
}
min = Math.min(abs, min);

4. 위에서 구한 절댓값 abs와 min이 같다면 cnt를 증가시켜주면 되고,

만약 현재 min보다 abs가 더 크다면 cnt를 1로 초기화 시켜줘야한다. (새로운 min값이 생겼기 때문에 이전에 카운트된 값은 없어져야함 !)

 

그리고 abs, min 중 더 작은 값을 min에 대입한다.

 

if(sum >= K) {
    end--;
}else {
    start++;
}

5. 이제 포인터를 움직여야할 차례이다.

만약 현재 두 수의 합이 K보다 크다면 end를 감소시켜서 두 수의 합을 더 작게 만들어야한다.

반대로 현재 두 수의 합이 K보다 작다면 start를 증가시켜 두 수의 합을 더 크게 만들어야한다.

 

System.out.println(cnt);

6. while문을 빠져나오면

min에는 abs[(K와 가장 가까운 두 수의 합) - K]이 담겨 있을 것이고

cnt에는 min값에 해당하는 숫자 쌍이 몇 개인지 담겨 있을 것이다.

그래서 cnt를 출력한다.

 

 

 

코틀린으로도 풀어보려고 했으나 코틀린으로 푼 사람은 단 한 명도 없었다. 모두 메모리 초과 이슈 .....

아무래도 내가 메모리 관리를 제대로 못 한 이유이겠지만 한 명도 못 풀었다는건 코틀린으로는 풀 수 없는 문제 아닐까 ..싶다

 

 

 

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		for(int t=0; t<T; t++) {
			String [] input = bf.readLine().split(" ");
			int n = Integer.parseInt(input[0]);
			int K = Integer.parseInt(input[1]);
			
			String[] inputArr = bf.readLine().split(" ");			
			int[] arr = new int[n];
			
			for(int i=0; i<n; i++) {
				arr[i] = Integer.parseInt(inputArr[i]);
			}
			Arrays.sort(arr);
			
			int start = 0;
			int end = n-1;
			
			int min = Integer.MAX_VALUE;
			int cnt = 0;
			
			while(start < end) {
				int sum = arr[start] + arr[end];
				int abs = Math.abs(arr[start] + arr[end] - K);
				
				if(abs == min) {
					cnt++;
				}else if(min > abs){
					cnt = 1;
				}
				min = Math.min(abs, min);
				
				if(sum >= K) {
					end--;
				}else {
					start++;
				}
			}
			System.out.println(cnt);
		}
	}
}

 

https://www.acmicpc.net/problem/9024