[백준] 1940 : 주몽의 명령 - JAVA

문제 분석

크기를 비교하는문제(두 숫자의 합..)는 값을 정렬하면 문제를 더 쉽게 풀 수 있다!
시간제한은 2초이고, N의 최대범위가 15,000이므로 O(NlogN)시간복잡도 알고리즘을 사용해도 괜찮다.
일반적으로 정렬 알고리즘의 시간 복잡도는 O(NlogN)이다.
즉, 정렬을 사용해도 괜찮다!
입력받은 N개의 값을 정렬한 후, 양쪽 끝 위치를 투 포인터로 지정해 시작하자.

---

슈도코드

N입력받기
M입력받기
A[N] 선언
for(N만큼 반복) {
	A원소 입력받기
}
A정렬
answer = 0
start = 0
end = N-1
while(start < end){
	if(A[start] + A[end] == M) {
    	answer++
        start++
        end--
    }
    else if(A[start] + A[end] > M) end --
    else start++
}
answer출력

---

제출 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		int[] A = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i =0; i<N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(A);
		
		int answer = 0;
		int start = 0;
		int end = N-1;
		
		while(start<end) {
			if(A[start] + A[end] == M) {
		    	answer++;
		        start++;
		        end--;
		    }
		    else if(A[start] + A[end] > M) end--;
		    else start++;
		}
		System.out.println(answer);
	}

}

공부한 사항

• 투 포인터 - 두 수의 합 비교시, 투 포인터 이동 원칙 : 합이 기준보다 크면 큰 번호 index내리고, 합이 기준보다 작으면 작은 번호 index 올리고, 합이 기준과 같으면 양쪽 포인터를 모두 이동시킨다.
• bufferedReader, StringTokenizer 이용 - 한 줄에 하나의 입력이면 BufferedReader만 이용해서 바로 int로 변환하며 받고, 한 줄에 공백으로 구분되는 여러개의 입력을 받으면 BufferedReader을 StringTokenizer에 받은 후 이걸 int로 변환.
• 오름차순 정렬 : Arrays.sort(정렬할 배열명)