[BOJ_1940 | While] 주몽

 

풀이

반복문의 성질을 잘 이용해서 풀어야 하는 문제이다.

먼저 주어진 고유 번호를 arr 배열에 저장한 후 정렬한다.

Java의 Arrays.sort를 이용하면 데이터 크기에 맞게 O(nlogn) 시간복잡도를 가지는 정렬 알고리즘으로

Java가 데이터를 잘 정렬해 준다.

정렬해 준 데이터를 while문 안에 넣고 연산을 수행하면 된다.

연산 과정은 다음과 같다.

start = 0, end = num.of data -1 로 놓고 시작한다.

만약 arr[end]가 m보다 클 경우 end를 1만큼 감소시키고 continue한다.

그렇지 않을 경우 i를 start부터 end-1까지 반복하면서 arr[i]+arr[end] == m이 되는 i의 값을 찾는다.

값이 없으면 end를 감소시키고 continue, 

값이 있으면 counter를 1만큼 증가시키고, start를 1 키워주고, end를 1 줄여주면 된다.

while 문은 (start < end)인 조건에서만 반복하도록 한다.

start >= end인 경우 데이터를 가리키는 포인터가 엇갈렸다는 뜻이므로 반복문은 탈출해주면 된다.

이 알고리즘을 사용하면 약 O(n log n)의 복잡도로 문제를 해결할 수 있다.

소스 코드

import java.util.*;
import java.io.*;
public class BOJ_1940 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
 
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){ arr[i] = Integer.parseInt(st.nextToken()); }
        Arrays.sort(arr);
 
        int cnt = 0;int start  = 0; int end = n-1;boolean flag = false;
        while(start < end){
            flag = false;
            if(arr[end] >= m){end--; continue;}
            for(int i=start;i<end;i++){
                if(arr[i]+arr[end] == m){cnt++; start=i+1;end--;flag = true;break;}
            }if(!flag){end--; flag = !flag;}
        }
        bw.write(cnt+"\n");
        bw.flush();
        bw.close();
    }
}