[BOJ][JAVA] 2295: 세 수 찾기

 

import java.io.FileInputStream;
import java.util.Arrays;
import java.util.Scanner;

class Main{
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int max = 0;
        for(int i=0; i<n;i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        for(int a=0;a<n; a++){
            for(int b=a;b<n; b++){
                for(int c=b;c<n; c++){
                    int tmp = arr[a]+arr[b]+arr[c];
                    int bs = Arrays.binarySearch(arr, tmp);
                    if(bs >= 0){
                        // 이러면 값이 있다는 얘기
                        max = Math.max(max, bs);
                    }
                }
            }
        }
        System.out.println(arr[max]);

        sc.close();
    }
}

---

오답노트(푸는 동안 사고과정 및 개선점)

3중 for문으로 다 경우의 수를 세면서 합을 찾는 코드를 작성해봤다. 짜면서 이거 무조건 시간초과 날텐데.. 했는데 진짜 시간초과 났다. 그래서 좀 경우의수를 줄여보고 자 한게 세 수 합이 집합 최대값을 넘어가면 아예 break를 내버리는 아이디어 였는데 아래와 같이 짜도 40% 근처에서 시간 초과가 났다. 더 줄여아할 듯 하다.

import java.io.FileInputStream;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class Main{

    public static int binarySearch(int[] arr, int target){
        int l=0; int r = arr.length-1;
        while (l<=r){
            int m = (l+r)/2;
            if(arr[m]<target) l = m+1;
            else if(arr[m]>target) r = m-1;
            else return 1;
        }
        return 0;
    }

    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int max = 0;
        for(int i=0; i<n;i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        for(int a=0;a<n; a++){
            for(int b=a;b<n; b++){
                for(int c=b;c<n; c++){
                    int tmp = arr[a]+arr[b]+arr[c];
                    int bs = Arrays.binarySearch(arr, tmp);
                    if (tmp <= arr[arr.length-1]){
                        if(bs >= 0){
                            // 이러면 값이 있다는 얘기
                            max = Math.max(max, bs);
                        }
                    }else {
                        break;
                    }
                }
            }
        }
        System.out.println(arr[max]);

        sc.close();
    }
}

 

해결 해야될 부분이 세 수를 고르는 방식이다..!

---

정답코드

import java.io.FileInputStream;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class Main{

    public static int binarySearch(int[] arr, int target){
        int l=0; int r = arr.length-1;
        while (l<=r){
            int m = (l+r)/2;
            if(arr[m]<target) l = m+1;
            else if(arr[m]>target) r = m-1;
            else return 1;
        }
        return 0;
    }

    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int max = -1;
        for(int i=0; i<n;i++){
            arr[i] = sc.nextInt();
        }
        int[] set = new int[(n*(n+1))/2];
        int idx = 0;
        for(int i=0; i<n;i++){
            for(int j=i; j<n; j++){
                set[idx++] = arr[i]+arr[j];
            }
        }
        Arrays.sort(set);
        for(int x=0;x<n; x++){
            for(int c=0;c<n; c++){
                int tmp = arr[x]-arr[c];
                int bs = Arrays.binarySearch(set, tmp);
                if(bs >= 0){
                    max = Math.max(max, arr[x]);
                }
            }
        }
        System.out.println(max);

        sc.close();
    }
}

 

두 수의 합에서 했었던 식 쪼개기가 여기서도 들어간다. a+b+c=x를 a+b=x-c로 바꿔서 작성하는 방식인데, 이러면 삼중포문 하나가 이중포문 2개로 쪼개져서 막대한 시간적 여유가 생긴다.

 

이진탐색 대상 배열을 만들 때는 세 수의 합의 최대값 까지 들어갈 수 있어야하니까 n까지의 합을 최대 크기로 잡아 선언하면 된다. 수 세기에서는 이진탐색을 그냥 구현했는데 라이브러리에 Arrays.binarySearch()가 있어서 이번에는 이걸 사용해봤다.

 

풀고 나서 등급을 보니 골드 4다.. 아마 이 생각의 전환이 골드급이라는 뜻일 것 같다.

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^