1253_좋다

사용 알고리즘: 투 포인터

사용 언어: java

 

테스트 통과되지 못한 코드 (시간 초과)

package week03;

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

public class Main_bj_1253_좋다 {
	static int n;
	static int[] numbers;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		numbers = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(numbers);
		//입 력 끝
		
		int ans = 0; //좋은 수의 개수 = 답
		
		//어차피 맨 앞 두 수는 좋을 수가 없음
		for (int i=2; i<n; i++) {
			if ( isGoodNumber(i) ) ans++;
		}
		
		System.out.println(ans);
	}

	private static boolean isGoodNumber(int idx) { //좋은 수인지 판별
		int curNumber = numbers[idx];
		
		int left = 0;
		int right = idx - 1;
		
		while (left < right) {
			int smaller = numbers[left];
			int bigger = numbers[right];
			
			if (smaller + bigger == curNumber) {
				return true; //좋은 수가 된다면 트루를 리턴
			}
			
			if (smaller + bigger < curNumber) { //목표값 보다 작은 수가 나온다면, left를 증가시키기
				smaller ++;
			}
			else { //목표값 보다 큰 수가 나온다면, right를 감소시키기
				bigger --;
			}
			
		}
		return false;
	}

}

 

 

맞는 답

package week03;

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

/**
 * 헐!! 
 * 음수가 나오면 나보다 큰 수도 사용될 수 있다!!
 *
 */

public class Main_bj_1253_좋다 {
	static int n;
	static int[] numbers;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		numbers = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(numbers);
		//입 력 끝
		
		int ans = 0; //좋은 수의 개수 = 답
		
		for (int i=0; i<n; i++) {
//			System.out.println(i+" 번째 테스트 시작!");
			if ( isGoodNumber(i) ) ans++;
		}
		
		System.out.println(ans);
	}

	private static boolean isGoodNumber(int idx) { //좋은 수인지 판별
		int curNumber = numbers[idx];
		
		int left = 0;
		int right = n - 1;
		
		while (true) {
			if (right == idx) right--;
			if (left == idx) left++;
			
			if (left >= right) break;
			
			int middle = (left + right) / 2;
			
			int smaller = numbers[left];
			int bigger = numbers[right];
			
			if (smaller + bigger == curNumber) {
				return true; //좋은 수가 된다면 트루를 리턴
			}
			
			if (smaller + bigger < curNumber) { //목표값 보다 작은 수가 나온다면, left를 증가시키기
				left++ ;
			}
			else { //목표값 보다 큰 수가 나온다면, right를 감소시키기
				right--;
			}
//			System.out.println("left and right: " + left + " "+right);
		}
		return false;
	}

}

 

요인 분석:

1. 인덱스를 움직여야 하는데 왜 수를 움직였지?..

2. 음수가 나올 수 있으니, 타겟 인덱스 보다 큰 인덱스에서도 확인을 해야 한다.

3. 2의 이유로 돌다보면 타겟 인덱스에 right나 left가 걸치는 때가 오는데, while의 조건이 left < right라고 해도 인덱스 조정이 들어가게 되면 left == right가 되는 경우가 발생할 수 있다.

그래서 종료 조건을 while문 자체에 두지 않고, 인덱스 조정 후 if문을 따로 두어서 break를 건다.