007. 주몽 (백준1940번)

문제

문제 분석하기

문제 안에서 얻을 수 있는 정보들을 찾아보자!

• 시간제한 2초 = 약 2억번의 계산안에 구해야한다.
• 시간복잡도는 $N$ 기준으로 $N^2$ 이 되어버리면 2억번이 넘어가므로, $N^2$ 이하의 시간복잡도를 가진 알고리즘을 사용해야 한다.
• 2개의 재료로 갑옷이 만들어진다. + 재료는 유니크 하다.
• 2가지의 재료의 고유번호를 합쳐 $M$ 이 되면, 갑옷이 만들어진다.

투포인터를 가지고 문제를 접근해보자!
= 2개를 가지고 값을 만드는구나...?

손으로 풀어보기

정렬을 한 후 접근하면 더 편하지 않을까? 라는 생각이 들어야한다.
정렬을 한 후 양쪽 끝에 포인트를 잡고 이동시켜보자!

투 포인터 이동 원칙 ( i=start(min), j=end(max) )

A[i] + A[j] > K j--; // K == M
A[i] + A[j] < K i++;
A[i] + A[j] == K j--; i++; count++;

슈도코드 작성하기

N(재료의 개수 저장)
M(갑옷이 되는 번호 저장)
A(재료의 개수만큼의 배열 선언)
count(만들어진 갑옷의 수를 담을 변수 선언)

for(N만큼) {
	A배열 저장
}

A배열 정렬

while(i<j) {
	if(재료합 < M) i++;
	else if(재료합 > M) j--;
	else i++; j--; count++;
}

count 출력

코드 구현하기

import java.io.BufferedReader;  
import java.io.BufferedWriter;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.io.OutputStreamWriter;  
import java.util.Arrays;  
import java.util.StringTokenizer;  
  
public class Main {  
  
    public static void main( String[] args ) throws IOException {  
       BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );  
       BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System.out ) );  
  
       int N = Integer.parseInt( br.readLine() );  
       int M = Integer.parseInt( br.readLine() );  
       int[] A = new int[ N ];  
       int count = 0;  
  
       StringTokenizer st = new StringTokenizer( br.readLine() );  
       for ( int i = 0; i < N; i++ ) {  
          A[ i ] = Integer.parseInt( st.nextToken() );  
       }  
  
       Arrays.sort( A );  
  
       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 {  
             i++;  
             j--;  
             count++;  
          }  
       }  
  
       bw.write( String.valueOf( count ) );  
  
       bw.flush();  
       bw.close();  
    }  
  
} // end