[백준 알고리즘 자바]3273 : 두 수의 합

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

3273번: 두 수의 합

---

문제

• n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다.
• ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다.
• 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

• 문제의 조건을 만족하는 쌍의 개수를 출력한다.

입출력 예제

---

분명 포인터 문제 풀었고..간단한 문젠데 왜 혼자 완벽하게 못푼건지 ㅠㅠ

이중 for문을 사용하면 답은 나오지만 백준에서는 시간초과 로 정답처리가 되지 않는다.

그러므로 투포인터를 사용해서 풀이 방식을 정리해보자.

Scanner와 BufferedReader 총 2가지 방식으로 정리할 것이다.

1. Scanner

1. N과 arr[], X 를 선언하고 값을 입력받는다. 그 후에 메소드를 구현하자.

• N : 정수의 개수
• arr[ ] : 수열
• X : 두 원소의 합
• 이 때 변수 X 는 배열을 입력받은 뒤에 선언해야 한다는 것을 명심하자!

2. result, sum, lt, rt 를 선언하고 각각 초기화한다.

• result : 결과값으로, X 가 나오는 쌍의 개수
• sum : (ai, aj)에서 ai + aj 를 합한 값
• lt : 맨 처음에 위치한 포인터
• rt : 맨 끝에 위치한 포인터로, N-1로 초기화해야 맨 끝 위치값이 나온다.

3. Arrays.sort() 를 사용해서 배열을 정렬한다.

• Arrays.sort() : 배열을 자동으로 오름차순으로 정렬해준다.

4. lt가 rt보다 작을 때 반복해서 돌아가는 while문을 선언한다.

• lt가 rt보다 작다는 의미는 아래 이미지를 보면 알 수 있다. 시작점이 끝점보다 작아야 범위 내에 있다.

5. sum 에 arr[rt] + arr[lt] 값을 넣는다.

 

6. 만약 sum이 X와 같으면 result에 1을 누적한다.

 

7. sum이 X보다 작다면 lt에 1을 누적한다.

 

8. 그게 아니라면 rt에 1을 빼서 끝 포인터를 변경한다.

 

수행 결과를 확인해보자.

답안 소스(Scanner)

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

public class Main {
	public int count(int N, int[] arr, int X) {
		int result = 0;
		int sum = 0;
		int lt = 0;
		int rt = N-1;
		
		Arrays.sort(arr);
		
		while(lt < rt) {
			sum = arr[rt] + arr[lt];
			
			if(sum == X) result++;
			
			if(sum < X) {
				lt++;
			}else {
				rt--;
			}
		}
		return result;
	}
	
	public static void main(String[] args) {
		Main num = new Main();
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		for(int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		int X = sc.nextInt();
		
		System.out.println(num.count(N, arr, X));
	}
}

---

2. BufferedReader

1. BufferedReader를 통해 버퍼를 생성한다.

 

2. StringTokenizer 과 br.readLine() 통해서 공백 기준으로 문자를 분리한다.

• StringTokenizer : 하나의 문자열을 여러 개의 토큰으로 분리하는 클래스이다.
• br.readLine() : 공백 기준으로 문자열을 나눈다.

3. Integer.valueOf() 를 사용해서 N을 입력받는다.

• valueOf : 괄호 안에 입력한 객체를 String 형으로 변환한다.
•  br.readLine() 만 사용하면 아스키 코드값으로 리턴하기에 형변환이 필요하다.

4. arr[ ] 배열에 값을 넣기 위해 StringTokenizer 객체를 생성한다.

• nextToken()을 사용하기 위해 객체화를 해주는데, 객체화를 한 다음에 받을 변수가 없으면 NoSuchElementException 에러 발생
• 즉, 토큰으로 뽑을 원소가 있으면 뽑기 전에 객체화를 해줘야 한다.
• N 변수를 위해 앞서 객체화를 하고, arr[] 배열을 위해 앞서 객체화를 한다.

5. N과 같은 방식으로 X를 입력받는다.

 

6. 메소드는 Scanner 와 동일한 형태로 구현한다.

 

수행 결과를 확인해보자.

답안 소스(BufferedReader)

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

public class Main {
	public int count(int N, int[] arr, int X) {
		int result = 0;
		int sum = 0;
		int lt = 0;
		int rt = N-1;
		
		Arrays.sort(arr);
		
		while(lt < rt) {
			sum = arr[rt] + arr[lt];
			
			if(sum == X) result++;
			
			if(sum < X) {
				lt++;
			}else {
				rt--;
			}
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		Main num = new Main();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.valueOf(st.nextToken());
		st = new StringTokenizer(br.readLine());
		
		int[] arr = new int[N];
		
		for(int i=0; i<N; i++) {
			arr[i] = Integer.valueOf(st.nextToken());
		}
		
		int X = Integer.valueOf(br.readLine());
		
		System.out.println(num.count(N, arr, X));
	}
}