007. 주몽의 명령 (백준 1940) - 정렬, 투포인터

문제 분석

• 재료의 개수 N(1~15,000),
  갑옷을 만드는데 필요한 수 M(1~10,000,000)이 주어졌을때
  몇개의 갑옷을 만들 수 있는지?

---

• 크기를 비교하므로 정렬(2 7 4 1 5 3 -> 1 2 3 4 5 7)

• N의 최대 범위가 15,000이므로 O(nlongn)시간 복잡도 알고리즘 사용가능
  시간복잡도

• 따라서 정렬 + 투포인터로 접근

  단계	시간
  정렬	O(N log N)
  투 포인터	O(N)

손으로 풀기

1. 오름차순 정렬
2. start_index와 end_index를 양 끝에서 시작
   2-1. sum < M, start_index를 올림
   2-2. sum > M, end_index를 내림
   2-3. sum == M이면, 양쪽 다 이동하고 count++

슈도코드 작성

N(재료의 개수)
M(갑옷이 되는 번호)
for(N만큼 반복)
{
	재료 배열 저장1
}
재료 배열 정렬
while(start_index < end_index)
{
	if(재료합 < M) 작은 번호 재료를 한 칸 위로 변경
    else if(재료합 > M) 큰 번호 재료를 한 칸 아래로 변경
    else 경우의 수(count) 증가, 양쪽 index 각각 변경
}
count 출력

정답

package A0study;

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

public class p1940_주몽 {
    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 count = 0;
        int i = 0;      //A[0]   -> Min
        int j = N - 1;  //A[N-1] -> Max
        while(i<j) {
            if(A[i] + A[j] < M) {
                i++;
            } else if(A[i] + A[j] > M) {
                j--;
            } else {
                count++;
                i++;
                j--;
            }
        }
        System.out.println(count);
    }
}

숫자 1개씩 받기:
int N = Integer.parseInt(br.readLine());
숫자 한줄씩 받기:
StringTokenizer st = new StringTokenizer(br.readLine());