[Java] 백준 1253번: 좋다

[문제 바로 가기] - 좋다

유형 : 투 포인터

문제를 다시 풀었을때 15분 안에 풀지 못하면 풀지 못하는 문제라고 해서 n번째 다시 푸는 문제! n+1번째 다시 풀어야 할 것 같다.

💡 접근 방식

10
1 2 3 4 5 6 7 8 9 10

와 같이 N개의 수가 주어질 때 다른 두 수의 합으로 나타낼 수 있는 수를 좋은 수라고 한다. 이때 수의 위치가 다르면 값이 같아도 다른 수라고 했으므로 같은 수가 여러 개 있을수도 있음을 알아야 한다.

먼저 수가 들어있는 배열을 오름차순 정렬한 후, 투 포인터를 활용해서 좋은 수를 찾는다. for문의 i는 좋은 수를 찾는 인덱스, left와 right는 좋은 수의 합이 되기 위한 인덱스가 된다.

i가 left나 right와 같을 땐 left와 right를 옮겨주고, left가 right와 같거나 클 경우엔 while문을 종료한다.

일반적인 투 포인터로 문제를 풀이하면 된다!

---

풀이

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

public class Main {
	public static void main(String[] ags) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[] nums = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(nums);
		
		int answer = 0;
				
		for (int i = 0; i < N; i++) {
			int left = 0;
			int right = N - 1;
			
			while (true) {
				if (i == left) left++;
				if (i == right) right--;
				
				if (left >= right) break;
				
				if (nums[left] + nums[right] == nums[i]) {
					answer++;
					break;
				} else if (nums[left] + nums[right] < nums[i]) {
					left++;
				} else if (nums[left] + nums[right] > nums[i]) {
					right--;
				}
			}
		}
		
		System.out.println(answer);
	}
}