백준 2309: 일곱 난쟁이[JAVA] / 투포인터

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

2309번: 일곱 난쟁이

9명 중 7명을 뽑는 것은 포함하지 않은 2명을 뽑는 것과 같다. 9명 난쟁이들의 키의 합을 구하고 100과의 차이를 구한다. 그 차이를 n이라고 두면 n은 일곱 난쟁이에 포함되지 않는 두 명의 키의 합과 같을 것이다. 

반복문을 돌려 키의 합이 n인 난쟁이 두 명을 찾아주는 알고리즘을 짰다. 

import java.util.*;
public class Main {
	public static void main(String[] args){
		int[] w = new int[9];
		Scanner sc = new Scanner(System.in);
		int total=0;
		for(int i=0; i<9; i++) {
			w[i] = sc.nextInt();
			total+=w[i];
		}
		
		int n = total - 100;
		int k1=-1, k2=-1;
		Arrays.sort(w);
		for(int i=0; i<9; i++) {
			for(int j=i+1; j<9; j++)
				if(w[i]+w[j]==n) {
					k1=i; k2=j;
					break;
				}
					
		}
		
		for(int i=0; i<9; i++)
			if(i!=k1 && i!=k2)
				System.out.println(w[i]);
	}

}

중첩 반복문을 사용하면 시간 효율이 떨어지기 때문에 쓰기 싫었는데 다른 좋은 방법이 떠오르지 않아 검색을 해보았는데 투포인터라는 알고리즘을 사용한 분들이 있었다. 

투포인터(Two Pointers)

:리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

정렬을 한 후 배열의 앞 부분부터 가르키는 s, 뒷 부분부터 가르키는 e를 둔다.

s + e가 n이면 두 난쟁이를 찾은것이고 

s + e < n이면  s를 증가시킨다

s + e > n이면 e를 감소시킨다.

이것을 반복하다보면 두 난쟁이를 찾을 수 있다. 

import java.util.*;
public class Main {
	public static void main(String[] args){
		int[] w = new int[9];
		Scanner sc = new Scanner(System.in);
		int total=0;
		for(int i=0; i<9; i++) {
			w[i] = sc.nextInt();
			total+=w[i];
		}
		
		int n = total - 100;
		int s=0, e=8;
		Arrays.sort(w);
		
		while(s<e) {
			if(w[s]+w[e]==n)
				break;
			if(w[s]+w[e]<n)
				s++;
			else
				e--;
		}
		
		for(int i=0; i<9; i++)
			if(i!=s && i!=e)
				System.out.println(w[i]);
	}

}

근데 input이 9개밖에 없어서 그런지 시간이 더 오래걸린다.