문제

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

풀이

1차 시도

풀이방법

1. 타겟일 될 숫자를 하나 정한다
2. 맨 앞, 맨뒤 설정
3. 합이 더 크면 뒤를 한칸 앞으로, 합이 더 작으면 앞을 한칸 뒤로 보냄

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 NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);

		int ans = 0;
		
		for(int i = 2; i < n; i++) {
			int target = arr[i]; 
			int front = 0;
			int rear = i-1;
			while(front != rear) {
				int temp =arr[front] + arr[rear]; 
				if(temp == target) {
					ans +=1;
					break;
				}
				
				if(temp > target) {
					rear -=1;
				}
				else {
					front+=1;
				}
			}
		}
		System.out.println(ans);
	}
}

결과

틀렸습니다.
목표 숫자를 3번째 숫자부터 하게 설정 해놨는데, 동일한 숫자가 여러개 올 때 이 방식대로 하면 문제가 생겼다.
그래서 해당 수 를 기준으로 앞을 탐색해주는 것과, 뒤를 탐색해주는 것을 만들기로 했다.

2차 시도

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 NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);

		long ans = 0;
		
		//앞에서 2개 이 후로 부터
		for(int i = 2; i < n; i++) {
			int target = arr[i]; 
			int front = 0;
			int rear = i-1;
			while(front != rear) {
				int temp =arr[front] + arr[rear]; 
				if(temp == target) {
//					System.out.println("target= "+target);
//					System.out.println(arr[front]+" "+ arr[rear]);
					ans +=1;
					break;
				}
				
				if(temp > target) {
					rear -=1;
				}
				else {
					front+=1;
				}
			}
		}
		
		//앞에 2개 숫자 처리
		for(int i = 0; i <2; i++) {
			int target = arr[i];
			int front = i +1;
			int rear = n-1;
			
			while(front != rear) {
				int temp =arr[front] + arr[rear]; 
				if(temp == target) {
//					System.out.println("target= "+target);
//					System.out.println(arr[front]+" "+ arr[rear]);
					ans +=1;
					break;
				}
				
				if(temp > target) {
					rear -=1;
				}
				else {
					front+=1;
				}
			}
		}
		System.out.println(ans);
	}
}

결과

틀렸습니다

이렇게 하니까 중간에 타겟 값이 설정 될 때
양 사이드의 값을 더해서 중앙에 있는 값을 만들어줘야 할 경우에 문제가 생겼다
그래서 앞을 탐색하는 함수, 뒤를 탐색하는 함수, 양 사이드를 탐색하는 함수를 만들었다.

최종 코드

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

public class Main {
	static long ans;
	static int arr[];
	static int state;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);

		ans = 0;
		
		for (int i = 0; i < n; i++) {
			state =0;
			int target = arr[i];
			
			if(i == 0&& state ==0) { // 맨 앞에 숫자는 뒤에 있는 숫자만 체크
				rearCheck(target,i+1,n-1);
			}
			else if(i == n-1  && state == 0) { //맨 뒤 숫자는 앞에만 체크 하면 됨
				frontCheck(target,0,i-1);
			}
			else { //state 변수 둔 이유는 동일한 타겟 앞에서 이미 찾았을 때 다른 함수 실행 안되게 하려고 
				if(state == 0) {
					frontCheck(target,0,i-1);
				}
				if (state == 0) {
					rearCheck(target,i+1,n-1);
				}
				if (state == 0) {
					centerCheck(target , 0, n-1,i);
				}
				
			}
		}
		System.out.println(ans);
	}
	
	static void frontCheck(int target, int front, int rear) { //타겟 기준 앞에 숫자만 체크 함수
		while(front != rear) {
			int temp =arr[front] + arr[rear]; 
			if(temp == target) {
				ans +=1;
				state = 1;
				break;
			}
			
			if(temp > target) {
				rear -=1;
			}
			else {
				front+=1;
			}
		}
	}
	
	static void rearCheck(int target, int front, int rear) { // 타겟 기준 뒤에 숫자만 체크 함수
		while(front != rear) {
			int temp =arr[front] + arr[rear]; 
			if(temp == target) {
				ans +=1;
				state =1;
				
				break;
			}
			
			if(temp > target) {
				rear -=1;
			}
			else {
				front+=1;
			}
		}
	}
	
	static void centerCheck(int target, int front, int rear, int now) { //타겟 기준 왼쪽 오른쪽 체크
		while(front != now && rear != now) {
			int temp =arr[front] + arr[rear]; 
			if(temp == target) {
				ans +=1;
				state =1;
				break;
			}
			if(temp > target) {
				rear -=1;
			}
			else {
				front+=1;
			}
		}
	}
}

state 변수를 두어 위에서 결과가 나왔을 떄 다른 함수 실행시키지 않게 했다.

문제 리뷰

투 포인터를 이용한 문제 였던거 같다.