[투포인터] 백준 1940번

1. 문제
2. 문제 분석
3. 슈도코드 작성
4. 코드 작성

 

참고)
 CPU 연산은 1초에 1억번 (시간복잡도 계산하며 풀기)

문제

주몽의 명령 갑옷만들기
- 갑옷을 만드는데 필요한 재료 2가지
- 재료의 합 M ( 1 <= M <= 10,000,000 )
- 재료의 개수 N ( 1 <= N <= 15,000)

 

문제 분석

• 투포인터 사용 (start point , end point)

투포인터 이동 원칙
- A[i] + A[j] > M : j--;    #번호의 합이 M보다 크면 끝 번호 인덱스(j)를 한칸 아래로 이동
- A[i] + A[j] < M : i++;    #번호의 합이 M보다 작으면 시작 번호 인덱스(i)를 한칸 위로 이동
- A[i] + A[j] == M : i++, j--;    #양쪽 포인터를 모두 이동시키고 count를 증가

 

• 두가지 포인터를 이용하여, 값을 계산하며 추정
  • 정렬 필요 : 투포인터를 사용하기 위해서는 정렬을 해야함 (2초내 연산이므로 사용해도 괜찮다)

중요)  정렬의 시간복잡도 : O(NlogN)
ex) 재료의 개수 : 15,000
      15000 * (3 + log15)

 

슈도코드 작성

N(재료의 개수) , M(갑옷이 되는 번호) 저장하기
for (N만큼 반복)
{
   재료 배열 저장하기
}

재료 배열 정렬하기

while( i <j )
{
    if (재료 합 < M)  시작 포인터 위치를 한칸 위로 이동
    else if (재료 합 > M) 끝 포인터 위치를 한칸 아래로 이동
    else 카운트값 증가, 양쪽 포인터 각각 이동
}
count 출력하기

 

코드 작성

• 입력값 (bufferedReader)
• 공백 파싱 (StringTokenizer)
• 타입 변환 (parse[타입])
• 배열 정렬(java.util.Arrays)

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

public class App {
    public static void main(String[] args) throws Exception {
        

        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(buf.readLine());
        int M = Integer.parseInt(buf.readLine());
        int[] array = new int[N];
        
        StringTokenizer st = new StringTokenizer(buf.readLine());

        for (int i = 0; i < N; i++){
            array[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(array);
        
        int count = 0;
        int i = 0;
        int j = N-1;
        while( i < j){
            if (array[i] + array[j] < M){
                i++;
            }
            else if (array[i] + array[j] > M){
                j--;
            }
            else{
                count++;
                i++;
                j--;
            }
        }

        System.out.printf("count = %d", count);
        buf.close();


    }
}