백준 1253번 : 좋다

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

1253번: 좋다

 

 

 

 

 

 

문제

• N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
• N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
• 수의 위치가 다르면 값이 같아도 다른 수이다.

 

제한사항

• N(1 ≤ N ≤ 2,000)
• i번째 수 : |Ai| ≤ 1,000,000,000

 

 

풀이

처음에 떠오른 풀이는 이중 for문을 돌려 두 수의 합을 구하고, 그 수가 배열에 있는지 확인하는 것이었다. 하지만 틀려서 게시판에서 찾아보니, "N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면"의 조건을 자세히 보면 "주어진 N개의 수 중에서 '자신을 제외한' 다른 두 수의 합으로 나타낼 수 있다면"의 의미라고 했다.

 

그래서 풀이를 다시 생각해봤다.

 

방법1 : 2중 for문

1. 배열의 모든 수를 돌아가며 합으로 나타낼 수라고 한다.

2. 나머지 두 수를 이중 for문으로 얻고, 두 수의 합을 구한다.

3. 두 수의 합이 합으로 나타낼 수와 같은지 확인한다.

 

이 풀이는 3중 for문으로 시간복잡도가 O(N^3)이다. N이 최대로 2000이니까, 최대 8,000,000,000(80억)의 시간이 걸린다.. 시간 초과가 날 것이다!

 

 

 

 

두 수를 구하는 데, O(n^2)의 시간이 걸리는 것을 그 이하로 줄일 방법으로 투포인터와 해쉬테이블이 생각이 났다.

 

 

 

방법2 : 해쉬테이블

1. 배열의 모든 수를 돌아가며 합으로 나타낼 수라고 한다.

2. 해당 수의 인덱스를 제외하고 모든 수를 순회한다.

3. HashSet에 (현제 수 - 목표 수)의 값을 기록한다. 앞으로 그 수가 필요하다는 것을 의미한다.

4. 순회하며 나오는 수가 HashSet에 있는지 확인한다.

 

 

두 수를 찾는 과정은 배열을 한 번 순회하므로 O(N)의 시간이 걸린다. 그리고 배열의 모든 수를 타켓으로 돌아가며 구하니, 총 O(N^2)의 시간이 걸린다.

 

하지만 별도로 값이 해쉬에 있는지 확인하고, 넣는 연산 O(1)이 추가로 든다. 이걸 이중 for문 안에서 하니 자세히 따지면 O(N^2)이 추가로 드는 것이다. 그리고 해쉬테이블을 만드는 데, 추가적인 메모리가 든다. 

 

 

보통 해쉬테이블이 정렬 때문에 O(N*logN)의 시간이 걸리는 투포인터보다 빠르다는 것을 알고 있었기 때문에 해쉬테이블로 풀려고 했지만, 실은 어차피 바깥에서 target을 정하는 것 때문에 추가적으로 for문을 돌리게 되어 O(N)이 아닌, O(N^2)의 시간이 추가적으로 들게 되었다... 정렬은 탐색 알고리즘이 들어가기 전 진행되기 때문에, 이 문제에서 투포인터를 쓰게 될 경우에는 추가적으로  O(N*logN)이 시간이 발생하게 된다. 더 효율적이다.

 

 

 

방법3 : 투포인터

1. 포인터를 왼쪽과 오른쪽 끝에 두고 탐색을 하기 위해, 오름차순으로 정렬을 한다.

2. 배열의 모든 수를 찾아야 될 합(target)으로 정한다.

3. 포인터의 왼쪽을 0에, 오른쪽을 N - 1에 두고 탐색을 시작한다.

4. 만약 target의 인덱스를 만난다면, 그 인덱스를 건너뛴다.

5. 두 수의 합 target이라면, 카운트를 올려주고 target에 해당하는 탐색을 끝낸다.

6. 합이 target 보다 크다면, 오른쪽 포인터를 줄여주고, 작다면, 왼쪽 포인터를 증가시켜준다.

7. left < right 일때까지 반복한다.

 

 

두 수를 찾는 과정은 포인터를 활용해 배열을 한 번 순회하므로 O(N)의 시간이 걸린다. 그리고 배열의 모든 수를 타켓으로 돌아가며 구하니, 총 O(N^2)의 시간이 걸린다. 추가적으로, 탐색 전 정렬 때문에 O(N*logN)이 시간이 걸린다.

 

 

 

 

 

코드

해쉬테이블

package algorithm;

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

public class BOJ_좋다 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		//구현
		int count = 0;
		for(int i = 0; i < N; i++) {
			int target = arr[i];
			
			HashSet<Integer> set = new HashSet<>();
			for(int j = 0; j < N; j++) {
				if(i == j) continue;
				
				int diff = target - arr[j];
				
				if(set.contains(arr[j])) {
					count++;
					break;
				}
				
				set.add(diff);
			}
		}
		
		System.out.println(count);
	}

}

 

 

 

 

투포인터

package algorithm;

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

public class BOJ_좋다2 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		//구현
		Arrays.sort(arr); //정렬
		
		int count = 0;
		for(int i = 0; i < N; i++) {
			int target = arr[i];
			int left = 0;
			int right = N - 1;
			
			while(left < right) {
				if(left == i) {
					left++;
				} else if(right == i) {
					right--;
				}
				
				if(left == right) continue;
				
				int sum = arr[left] + arr[right];
				
				if(sum == target) {
					count++;
					break;
				} else if(sum > target) {
					right--;
				} else {
					left++;
				}
			}
		}
		
		System.out.println(count);
	}

}

 

 

 

 

 

 

 

결과

 

 

위 : 해쉬테이블 풀이

아래 : 투포인터 풀이 

 

 

 

 

 

배운점