[백준/자바] 1253 좋은 수 구하기

[백준/자바] 1253 좋은 수 구하기

 

📌 문제 

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

 

 

⚔ 입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000),
두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

 

 

📣 출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

 

 

 

---

 

 

 

💎 문제분석하기

 

 

문제의 예시로 주어진10까지 연속된 자연수를 생각해보면 

 

 

 

1,2를 제외한 나머지 수임을 알 수 있다. 

 

이전의 포인터 문제

와 동일한 로직으로 접근할 수 있다. 

 

따라서 먼저 받은 N을 배열에 저장하여 오름차순으로 정렬한다. 

 

이후 양 끝단에 포인터를 설정하고 i와 j가 만날 때까지 반복한다. 

 

이 문제에서는 sum을 통해 카운트 하는 조건은 단일 수(좋은수)를 만났을 때이다. 따라서 주어진 모든 숫자가 좋은 수인지를 판별하는 로직이 필요하다. 이는 좋은수를 설정하고 N회만큼 반복문을 돌리는 것으로 확인된다.

 

사용할 변수를 정리해보자. 

 

N = 입력받은 수의 개수 

A = 두번째로 입력받는 N개의 수의 값들을 저장할 배열 

K = A안에 저장된 값들 중에 찾아야 하는 좋은 수

i = 투 포인터 중 스타트 

j = 투 포인터 중 엔드 

count = 찾은 좋은 수 개수 

 

먼저 투포인터가 좋은수를 발견하는 원칙을 다음과 같이 작성할 수 있다. 

 

K를 판별하는 반복문이 0 ~ N 까지 돌아가고 있다고 하고 

A[k] 가 좋은 수인지를 판별하는 로직을 구성한다. 

 

1) start + end == K : 좋은 수 발견 => count ++; i++; j--; 

 

 

여기서 추가해야 하는 다른 로직은 중복을 처리하는 부분이다. 

 

문제의 조건에서 서로 다른 두 수의 합으로 표현되는 수를 좋은 수라 했으므로 A 안의 값들을 비교하는 로직에서 중복은 제외되어야 한다.

 

 

 

 

만약 1번 케이스에 따라 k값을 찾지 못했다면 다음 로직을 수행해주어야 하므로 

 

2) start + end > K => j가 충분히 내려갔음에도 K가 없는 상황이므로 패스시켜 반복문을 종료하고 다음 K값을 가져오게 한다 

=> j -1을 시키고 반복문의 조건으로 i >j를 설정하면 다음 while문에서 false를 띄우면서 다음 K 값을 가져오게 한다. 

 

 

예를 들어 k가 0으로 찾아야 하는 값이 최저값인 1로 세팅이 되는 경우 

 

 

j=0까지 내려가면서 반복문에서 false를 띄운다. 

 

따라서 2번 규칙으로 

2) start + end > K : 좋은 수가 없으므로 => j--;

 

 

만약 start + end < K 인 경우라면 어떻게 될까? 

 

제시된 문제의 조건에서 이와 같은 경우는 주어지지 않았지만 같은 원리에 따라 i +1을 해주는 것으로 처리할 수 있다. 

 

따라서 3번 규칙 

3) start + end < K => i++; 

 

 

 

 

 

 

 

💡 코드 구현하기

 

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[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // N 입력

		// N 의 값 배열에 저장
		int[] A = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}

		// 배열 A 오름차순 정렬
		Arrays.sort(A);
		int count = 0;
		for (int k = 0; k < N; k++) {
			long find = A[k];
			int i = 0;
			int j = N - 1;

			while (i < j) {
				if (A[i] + A[j] == find) {        //K 값 검증

					if (i != k && j != k) {    // 중복이 아니어야 하므로
						count++;
						break;
					} else if (j == k) {
						j--;
					} else if (i == k) {
						i++;
					}
				} else if (A[i] + A[j] < find) {
					i++;
				} else {        // j값을 낮춰줌으로써 반복문 탈출을 위한 장치를 마련 
					j--;
				}
			}
		}

		System.out.println(count);
		br.close();
	}
}

 

 

---

 

 

하지만 이번 문제는 투포인터로 풀기보다는 다른 방법을 사용해보는 것도 괜찮을 것 같다. 

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편