[JAVA] BOJ 백준 2295번 - 세 수의 합

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

다양한 시도를 해봤는데,, 일단 3중 for 문이 들어간 순간부터 시간 초과 혹은 메모리 초과가 발생한다. 그래서 x + y + z = k 식을 x + y = k - z 식으로 바꿔 풀었다. 기본적으로 x <= y <= z <= k 임을 정해두고 코드를 작성했다.

 

먼저 a + b 를 sum 이라는 배열에 넣어주었다.

int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
int[] sum = new int[N*N];

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

int cnt = 0;
for (int x = 0; x < N; x++) {
    for (int y = x; y < N; y++) {
        sum[cnt++] = arr[x] + arr[y];
    }
}
Arrays.sort(sum, 0, cnt-1);

 

이제 k - z 값이 sum 배열에 존재하는지 확인하면 된다.

search 함수는 인자 값으로 sum 배열 크기, sum 배열, 찾는 값을 전달하여 인덱스를 반환하는 함수이다.

-1을 반환할 경우에는 찾는 값이 없으므로 계속 진행해주고, -1이 아닌 값을 반환할 경우에는 break 문를 사용해 for문을 빠져나오면 된다.

int result = 0;
for (int x = N-1; x >= 0; x--) {
    for (int y = x; y >= 0; y--) {
        if (search(cnt-1, sum, arr[x] - arr[y]) != -1) {
            result = arr[x];
            break;
        }
    }
    if (result != 0) break;
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B2295.java

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

class Main {
    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 N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] sum = new int[N*N];

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

        int cnt = 0;
        for (int x = 0; x < N; x++) {
            for (int y = x; y < N; y++) {
                sum[cnt++] = arr[x] + arr[y];
            }
        }
        Arrays.sort(sum, 0, cnt-1);

        int result = 0;
        for (int x = N-1; x >= 0; x--) {
            for (int y = x; y >= 0; y--) {
                if (search(cnt-1, sum, arr[x] - arr[y]) != -1) {
                    result = arr[x];
                    break;
                }
            }
            if (result != 0) break;
        }
        
        bw.write(result+"");

        br.close();
        bw.flush();
        bw.close();
    }

    public static int search (int N, int[] arr, int sum) {
        int result = -1;

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

        while (start <= end) {
            int mid = (start + end) / 2;

            if (arr[mid] < sum) {
                start = mid + 1;
            }
            else if (arr[mid] > sum) {
                end = mid - 1;
            }
            else {
                result = mid;
                break;
            }
        }

        return result;
    }
}

---

4. 결과 및 회고

이전에 답지 본 풀이를 다시 풀어봤는데,, 한 번에 풀지 못했다,, ㅠㅠㅠ

그래도 이번에 제대로 입력값 범위에 따른 시간과 메모리에 대해 계산해봤다. 다음엔 한 번에 풀 수 있을 것 같다.