[백준] 단계별로 풀어보기(단계:26, 투 포인터,JAVA)3273번, 두 수의 합

문제 링크

3273번: 두 수의 합

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

투 포인터는 두 가지의 위치를 가리키는 포인터 Start, End를 이용하여 1차원 배열에 저장된 값들에 범위를 더하여 해당하는 값을 구하거나 포인터가 가리키는 값을 더해서 원하는 값을 구할 수 있도록 하는 알고리즘입니다.

 

투 포인터를 사용할 때에는 주로 정렬한 상태에서 사용합니다.

 

이 문제에 핵심은

1. 수열의 값들로 쌍을 만들어 입력값과 동일한 합이 나오는 경우의 수를 출력한다.

 

투 포인터 알고리즘을 사용하는 문제를 한 번도 풀어본적이 없었기 때문에 이 문제를 보자마자 브루트포스를 이용해서 문제를 해결해보았지만 결과는 실패...

 

이 문제에 주제인 투 포인터에 대해 검색을 통해 이해한 후 다시 문제를 살펴보니 생각보다 쉬운 문제였습니다.

 

투 포인터 알고리즘에서는 위치를 가리키는 2가지 포인터를 설정하였습니다.

Start = 0

End = 배열의 크기 - 1

 

이후 저는 수열을 오름차순으로 정렬한 뒤에 아래에 규칙대로 탐색하였습니다.

1. start의 값 + end의 값 > 만들어야할 자연수 : end - 1

2. start의 값 + end의 값 < 만들어야할 자연수 : start + 1

3. start의 값 + end의 값 = 만들어야할 자연수 : count + 1, start + 1

 

예제입력 1을 표로 오름차순으로 정렬한 뒤 표로 표현하면

만들어야할 자연수 : 13, Count : 0

1	2	3	5	7	9	10	11	12
Start								End

Start(1) + End(12) = 13

규칙 3 적용 → Count(0) + 1, Start + 1

 

1	2	3	5	7	9	10	11	12
	Start							End

Start(2) + End(12) = 14

규칙 1 적용 → End - 1

 

1	2	3	5	7	9	10	11	12
	Start						End

Start(2) + End(11) = 13

규칙 3 적용 → Count(1) + 1, Start + 1

 

1	2	3	5	7	9	10	11	12
		Start					End

Start(3) + End(11) = 14

규칙 1 적용 → End - 1

 

1	2	3	5	7	9	10	11	12
		Start				End

Start(3) + End(10) = 13

규칙 3 적용 → Count(2) + 1, Start+ 1

 

1	2	3	5	7	9	10	11	12
			Start			End

Start(5) + End(10) = 15

규칙 1 적용 → End - 1

 

1	2	3	5	7	9	10	11	12
			Start		End

Start(5) + End(9) = 14

규칙 1 적용 → End - 1

 

1	2	3	5	7	9	10	11	12
			Start	End

Start(5) + End(7) = 12

규칙 2 적용 → Start + 1

 

1	2	3	5	7	9	10	11	12
				Start, End

Start와 End가 같은 곳이면 쌍을 못만드는 것으로 탐색 종료

Count = 3

결과로 Count를 출력하여 3이 출력됩니다.

 

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값(수열, 만들어야할 자연수)를 저장합니다.

2. 저장한 수열을 오름차순으로 정렬합니다.

3. 위 규칙을 적용하여 Count를 구합니다.

4. Count는 만들어야할 자연수의 개수로 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 수열에 대한 정보 분리하였습니다.
• 수열에 쌍으로 만들어야할 자연수를 만드는 경우의 수를 구하는 sum함수를 만들었습니다.
• BufferedWriter에 Count를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• sum은 투 포인터 알고리즘을 통해 Start, End를 이용해서 경우의 수를 구하였습니다.
• sum은 반복문을 통해 위 규칙을 적용하였습니다.

import java.io.*;
import java.util.*;
public class Main{
	static int[] num;		//수열 저장 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //----------입력값 저장 및 배열 초기화------
    	int n = Integer.parseInt(br.readLine());
    	num = new int[n];
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	
    	for(int i=0;i<n;i++) 
    		num[i] = Integer.parseInt(st.nextToken());
    	
    	Arrays.sort(num);		//수열 오름차순 정렬
    	int x = Integer.parseInt(br.readLine());
    	int result = sum(n, x);		//함수 실행
    	bw.write(result + "\n");		//경우의 개수 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();	
    }
    //--------경우의 수 구하는 함수--------
    public static int sum(int n, int x) {
    	int start = 0;		//Strat 포인터
    	int end = n-1;		//End 포인터
    	int count = 0;		//Count
    	while(start<end) {
    		int temp = num[start] + num[end];
    		if(temp > x)	//규칙 1.
    			end--;
    		else {		//규칙 2, 3
    			if(temp == x)		//규칙 2에 Count + 1
    				count++;
    			start++;	
    		}
    	}
    	return count;	//Count 결과로 반환
    }
}