[BOJ] 백준 3273번: 두수의 합_자바(JAVA) *정렬, 투포인터 이용하지 않고 풀기

1. 문제

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

3273번: 두 수의 합

---

2. 접근 및 해결

2-1) 접근

투포인터를 사용하지 않고 구현하는 방법입니다. 

// 입력
9
5 12 7 10 9 1 2 3 11
13

int[] numList = new int[num]; // [5, 12, 7, 10, 9, 1, 2, 3, 11]
int[] list = new int[2000001];

먼저 입력으로 들어오는  a1, a2, ..., an으로 이루어진 수열을 저장할 numList를 만들어줍니다. 해당 배열의 크기는 첫 번째 입력으로 들어왔던 9로 설정합니다. *여기서는 numList = [5, 12, 7, 10, 9, 1, 2, 3, 11]가 됩니다.

그리고 list 배열도 만듭니다. 이 list배열의 크기는 2000001로 지정하고 각 값을 0으로 초기화 합니다.(new 를 이용하면 선언 시 바로 0으로 초기화됩니다.) 크기를 2000001로 만드는 이유는, X값이 최대 2000000이기 때문입니다. 아래에서 구현 시 X값에서 numList값들을 뺀 값으로 list를 검색할 것이기 때문입니다.

이렇게 크기를 만들지 않으면 런타임 에러 (ArrayIndexOutOfBounds) 가 발생합니다.

for(int i=0; i<num; i++) {
    int inputNum = Integer.parseInt(st.nextToken());
    list[inputNum]++; // 입력값을 인덱스로 생각하고 해당 인덱스 값을 +1을 해주고,
    numList[i] = inputNum; // 입력값으로 오는 a값(5, 12, 7..)들을 이 numList에 저장합니다.
}

입력값을 인덱스로 생각하고 해당 인덱스 값을 +1을 해주고,

입력값으로 오는 a값(5, 12, 7..)들을 이 numList에 저장합니다.

// list의 상태
index - 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...
value - 0 1 1 1 0 1 0 1 0 0 1  1  1  1  0  0  0  ...

 사실 입력으로 들어오는 a값이 서로 다른 자연수이기 때문에 list[inputNum]++을 하지 않고 list[inputNum] = 1을 해도 무방합니다.

그리고 X-numList[i] 즉, 13-5=8, 13-12=1, 13-7=6 .. 이렇게 밑줄 친 값이 list에서 1으로 존재하면 cnt값을 +1했습니다. 그리고 이 방법을 이용하면 마지막에 꼭 2로 나눠줘야 합니다.(중복제거)

 

2-2) 해결

if(X - numList[i] >= 0 && numList[i] != X - numList[i] && list[X - numList[i]] > 0){

여기서 문제 해결에 있어서 중요한 2가지가 있습니다.

1. X-numList[i] >= 0 

만약 X가 5일 때 numList[i]가 10이면 list[음수]를 확인하게 되기 때문에 꼭 조건을 달아줘야합니다.

2. numList[i] != X - numList[i]

만약 a(numList[i])가 10인데 X가 20이면 20-10=10 이니까 자기 자신에 대해서도 카운트하게 됩니다.

따라서 이 조건을 꼭 달아줘야 합니다.

---

3. 코드(JAVA) 

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

public class Main {
	public static void main(String args[]) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int num = Integer.parseInt(br.readLine());
		int[] numList = new int[num];
		int[] list = new int[2000001];
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0; i<num; i++) {
			int inputNum = Integer.parseInt(st.nextToken());
			list[inputNum]++;
			numList[i] = inputNum;
		}
		
		int X = Integer.parseInt(br.readLine());
		int cnt = 0;
		for(int i=0; i<num; i++) {
			if(X - numList[i] >= 0 && numList[i]!=X-numList[i] && list[X-numList[i]]>0){
				cnt++;
			}
		}
		bw.write(Integer.toString(cnt/2));
		
		
		br.close();
		bw.close();
		
	}
}

문제를 투포인터로 해결해야하는지 몰라서 마음대로 구현을 해버렸는데, 투포인터로도 해결 후 포스팅하겠습니다!