[백준/자바] 3273 두수의 합

[백준/자바] 3273 두수의 합

 

 

 

---

 

 

 

 

💡 코드 구현

 

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

public class Main {

	private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(bufferedReader.readLine());

		int[] numbers = new int[N];
		String numberList = bufferedReader.readLine();
		StringTokenizer stringTokenizer = new StringTokenizer(numberList);
		for (int i = 0; i < N; i++) { // O(n)
			numbers[i] = Integer.parseInt(stringTokenizer.nextToken());
		}

		int numberToSum = Integer.parseInt(bufferedReader.readLine());

		Arrays.sort(numbers); // O(nlogn)

		int count = 0;
		// for (int i=0;i<numbers.length/2;i++){ // O(n)
		// 	if (numbers[i]+numbers[numbers.length-(i+1)]==numberToSum){
		// 		count++;
		// 	}
		// }


		int start = 0;
		int end = numbers.length-1;
		while (start < end) {   // O(n)
			if (numbers[start] + numbers[end] == numberToSum) {
				start++;
				end--;
				count++;
				continue;
			}

			if (numbers[start] + numbers[end] > numberToSum) {
				end--;
				continue;
			}
			start++;
		}

		System.out.println(count);
	}
}

 

문제 풀이 아이디어는 어렵지 않다. 두가지 방식에 대해 살펴본다. 첫번째는 정렬을 이용하고, 두 번째는 배열을 이용한다. 

 

1. 정렬 

 

먼저 정렬을 시키고 앞과 뒤를 비교하면서 합을 검증한다.

 

만약 이 문제를 모든 경우의 수를 탐색하는 버블 소트로 풀이한다면 버블 소트 자체의 시간 복잡도가 O(n^2)이므로 1백만 건 데이터에 대해 1초를 넘길 수 있다 (1백만 x 1백만 = 1억). 

 

따라서 단순 모든 탐색으로 풀면 안되고 선정렬 후 정렬된 데이터의 특성을 이용해 합 경우의 수를 까져야 한다. 

 

이때 Java.util.Array 클래스에서 제공하는 Arrays.sort() 메서드를 이용해 정렬하면 굳이 큌정렬이나 병합정렬을 직접 구현하지 않아도

간편하게 정렬 할 수 있다. Arrays.sort()의 시간 복잡도는 O(nlogn)이므로 넉넉하게 연산을 한다. 

 

Arrays.sort()에 대한 보다 자세한 설명은 다음 글에서 볼 수 있다.

 

https://upcurvewave.tistory.com/379

Java의 Arrays.sort() 정렬 메서드

 

이를 이용하여 정렬한 데이터가 다음과 같다고 가정해보자. 

 

1, 2, 3, 4, 5, 6, 7 

 

만약 x가 8로 주어질 경우 경우의 수는 (1, 7), (2, 6), (3, 5)로 직관적으로 보아도 3개이다. 이처럼 끝과 끝의 합을 이용하여 경우의 수를 구할 수 있다. 

 

이 성질을 그대로 적용한 코드는 다음과 같다. 

 

// for (int i=0;i<numbers.length/2;i++){ // O(n)
//     if (numbers[i]+numbers[numbers.length-(i+1)]==numberToSum){
//        count++;
//     }
// }

 

이 방식은 정확한 방법이 아니다. 

 

왜냐하면 1:1로 대응하지 않는 경우가 있기 때문이다. 

 

예를 들어 

 

배열: 1, 2, 3, 5, 7, 9, 10, 12 

구해야 하는 합: 14

 

인 경우를 생각해보자. 

 

만약 위의 코드로 이를 풀이한다면 답은 0이 될 것이다. 

 

하지만 실제 정답은 2이다. 이때 해는 (2, 12), (5, 9)이다.

 

따라서 아래 코드에서와 같이 

i) 끝과 끝의 합이 정답과 맞는 경우 

ii) 끝과 끝의 합이 정답보다 큰 경우 

를 나누어서 생각하여, 만약 크다면 그 이상(즉 오른쪽)의 숫자를 탐색하는 것은 의미가 없으므로 end 인덱스를 조정해주어야 한다. 

 

따라서 양방향으로 인덱스를 상황에 맞게 조정하는 탐색이 필요하다. 

 

int start = 0;
int end = numbers.length-1;
while (start < end) {   // O(n)
   if (numbers[start] + numbers[end] == numberToSum) {
      start++;
      end--;
      count++;
      continue;
   }

   if (numbers[start] + numbers[end] > numberToSum) {
      end--;
      continue;
   }
   start++;
}

 

 

그렇다면 이 반복문의 시간 복잡도는 어떻게 될까 ?

 

합 계산start와 end 변수를 사용하여 while 루프를 실행한다. 이 루프는 start가 end보다 작을 때까지 반복되므로 최대 N/2번 반복한다. 즉, 시간 복잡도는 O(N)이다.

 

최대 시간 복잡도가 배열 정렬 하는 부분에서 O(nlogn)이므로 총 시간 복잡도는 O(nlogn)이다. 

 

 

 

---

 

 

2. 배열

 

배열을 이용하면 보다 간단하다. 

카운트 배열을 이용해서 풀 수 있다. 

 

예를 들어, 1 + 7 = 8이 되는 경우는 무엇일까? 

 

만약 모든 경우의 수를 검증한다면 다음과 같은 방식으로 이중 반복문이 되어 

버블 정렬과 마찬가지의 시간 복잡도 O(n^2)을 가질 것이다. 

 

for (int i =0; i< n; i++) {
  for (int j= 0; j<n; j++) {
  if (A[i] + A[j] = X) {
   count++;
  }
}

 

하지만 위의 식을 두고 생각해보면 

1 = 8 - 7이라고도 할 수 있다. 

 

만약 1 ~ 10까지의 수를 검증한다면 어떨까?

1 + ? = x

2 + ? = x

3 + ? = x

.

.

.

 

즉, ?이 존재한다면 한번의 반복문만으로도 탐색이 가능하다는 결론에 도달하게 된다. 

 

예를 들어 x가 8인 경우 1의 pair는 7이 될 것이며, 7이 주어진 숫자 중에 존재한다면 count++;을 해줄 수 있다. 

 

따라서 다음과 같은 count 배열을 이용해 숫자의 발생을 체크해주고, 1번의 반복문으로 전체 숫자를 검증하면서 pair를 찾는다면 쉽게 답을 구할 수 있다.

 

주의 할 점은, 이와 같은 카운트 배열을 사용할 수 있는 이유가 중복 value가 존재하지 않다는 문제의 조건이 있기 때문이다. 또한 모든 숫자를 탐색할 경우 (1,7) (7,1)과 같이 중복 pairs에 대해서도 카운팅이 되므로 해당 값을 제외해주기 위해 탐색을 /2로 줄여준다. 

 

 

public static void main(String[] args) throws IOException {
   int N = Integer.parseInt(bufferedReader.readLine());

   int[] numbers = new int[N];
   String numberList = bufferedReader.readLine();
   StringTokenizer stringTokenizer = new StringTokenizer(numberList);
   for (int i = 0; i < N; i++) { // O(n)
      numbers[i] = Integer.parseInt(stringTokenizer.nextToken());
   }

   int numberToSum = Integer.parseInt(bufferedReader.readLine());

   boolean[] exist = new boolean[1000000];

   for (int i=0; i<N;i++){ // O(n)
      exist[numbers[i]] = true;
   }

   int count = 0;
   for (int i = 1; i< (N-1)/2; i++){ // O(n)
      if (i<=1000000 && numberToSum - i <=1000000){
         count+= (exist[i] && exist[numberToSum- i]) ? 1:0;
      }
   }
   
   System.out.println(count);
}

 

시간 복잡도는 1번의 반복문에 대해서 n/2번 검증을 하므로 O(n)이다. 

 

---