[백준]1253 좋다 - 자바/Java

1253번: 좋다

풀이

💡 메모리 18528KB, 시간 288ms

• 이중 포문까지만 가능, 삼중 포문 부터는 시간 초과가 날 것이다.
• 입력되는 값의 범위가 -10억~10억이고 Integer의 범위가 -20억~20억이므로 두 수의 합은 안전하게 Long 타입으로 가져갔다.이 때 검사할 숫자들은 정렬된 상태여야 한다. 정렬된 값들에만 적용 가능하다.
• 핵심은 검사할 숫자를 정하고, 해당 숫자를 기준으로 투포인터 알고리즘을 적용하는 것이다.
• 투포인터 알고리즘 구현에 익숙해져가는 것 같다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] numb = new int[N];
		for(int i = 0; i<N; i++) numb[i] = sc.nextInt();
		Arrays.sort(numb);
		
		int cnt = 0;
		for(int i = 0; i<N; i++) {
			int find = numb[i]; // 검사할 숫자
			int stIdx = 0;
			int edIdx = N-1; 
			
			while(stIdx < edIdx) { // 투포인터 알고리즘
				long sum = numb[stIdx] + numb[edIdx];
				if(sum == find) { // 각 숫자가 find와 같은 수면 안됨
					if(stIdx != i && edIdx != i) {
						cnt++; // 다른 위치의 숫자일때만 가산
						break;
					}
					else if(stIdx == i) stIdx++;
					else if(edIdx == i) edIdx--;
				}
				else if(sum < find) stIdx++;
				else edIdx--;
			}
		}
		System.out.print(cnt);
		sc.close();
	}
}

---

코드 리뷰

• 입력을 받을 때 BufferedReader를 사용했음에도 시간이 많이 사용되었다.
• findGood 함수는 입력된 숫자의 배열 A와 검사하고자 하는 값의 인덱스 번호를 받는다. 좋은 수라면 1을 반환하고, 아니라면 0을 반환한다.이는 자바에서 정수는 Primitive Type이기 때문이다. Primitive Type은 객체를 호출할 때 복제되어 전달되는 게 아니라, 주소값을 전달한다.
• Integer형 배열은 호출될 때 주소값을 반환한다. 즉 findGood 함수에서 A[]를 받아도 배열이 무한정 복제되어 사용되는게 아니라, 하나의 배열의 주소값을 받아 사용하는 일종의 공유 데이터다.
• 근데 왜 시간이 2384ms가 나왔지? 함수를 호출할 때 시간이 그렇게 오래 걸리나..?

💡 풀이자 : gi0204, 메모리 : 14640KB, 시간 2384ms

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        int[] A = new int[N];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        int good = 0;
        for (int i = 0; i < N; i++) {
            good += findGood(A, i);
        }
        System.out.println(good);
    }

    public static int findGood(int[] A, int idx) {
        int num = A[idx];
        for (int i = 0; i < A.length; i++) {
            if (i == idx) {
                continue;
            }
            for (int j = i + 1; j < A.length; j++) {
                if (j == idx) {
                    continue;
                }
                if (A[i] + A[j] == num) {
                    return 1;
                }
            }
        }
        return 0;
    }
}

 

• 해당 풀이는 나랑 완전히 똑같다. 배열을 선언할 때 타입 지정만 다르다.

💡 풀이자 : spparty 메모리 : 22232KB, 시간 408ms

import java.util.*;
import java.io.*;
public class Main {		
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long arr[] = new long[N];
		
		for (int i=0; i<N; i++)
		{
			arr[i] = sc.nextLong();
		}
		Arrays.sort(arr);
		
		int cnt=0;
		for (int i=0; i<N; i++)
		{
			int left=0;
			int right = N-1;
			
			while (left < right)
			{
				if (left == i)
				{
					left++;
					continue;
				}
				else if (right == i)
				{
					right--;
					continue;
				}
				
				if (arr[left] + arr[right] == arr[i])
				{
					cnt++;
					break;
				}
				else if (arr[left] + arr[right] < arr[i])
				{
					left++;
				}
				else if (arr[left] + arr[right] > arr[i])
				{
					right--;
				}
			}
		}
		System.out.println(cnt);
	}
}

 

• 얘도 로직은 똑같다. 입력받을 때 BufferedReader를 사용하여 시간이 단축됐다.

💡 풀이자 : jjjp9966 메모리 : 12792KB, 시간 124ms

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] nums = new int[N];
		int count = 0; // 좋은 수의 개수

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(nums);

		for (int i = 0; i < N; i++) {
			int startIdx = 0;
			int endIdx = N - 1;
			while (startIdx < endIdx) {
				int sum = nums[startIdx] + nums[endIdx];
				if (sum == nums[i]) {
					if (startIdx != i && endIdx != i) {
						count++;
						break;
					} else if (startIdx == i) {
						startIdx++;
					} else if (endIdx == i) {
						endIdx--;
					}
				} else if (sum < nums[i]) {
					startIdx++;
				} else {
					endIdx--;
				}
			}
		}
		System.out.println(count);
	}

}

---

Conclusion

• 이 문제는 풀이가 거의 정형화 되어있는 것 같다. 약간 응용된 투포인터 알고리즘.
• 자바에서 Primitive Type를 어떻게 취급하고 종류는 무엇인지 다시 한 번 정리해야겠다. 첫번째 풀이자의 코드가 왜 그렇게 시간이 오래 걸렸는지 알고싶다.