[백준] 1940번 주몽 (java)

<문제>

문제 출처 : https://www.acmicpc.net/problem/1940

<나의 풀이>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
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);    // 시간복잡도 nlogn
        int cnt = 0;
        int i = 0;
        int j = N-1;
        while(i<j){
            if(A[i]+A[j]<M)i++;
            else if (A[i]+A[j]>M) j--;
            else{
                cnt++;
                i++;
            }
        }
        System.out.println(cnt);
    }
}

<핵심 개념>

투포인트에서 시간복잡도는 O(n)이지만 정렬 알고리즘의 시간복잡도가 nlogn이므로 이 풀이의 시간복잡도는 nlogn이다.

풀이 자체는 그렇게 어렵진 않지만 투포인터라는 개념을 떠올리고 조건을 주는 부분이 조금 까다로우니 꼭 복습하고 다른 문제도 꼭 풀어보자.