[백준, 1940] 주몽의 명령

문제

 

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다.

 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성

 

N개의 재료는 각각 고유 번호를 가지고 있고 두 재료의 고유 번호를 더해서 M이 되면 갑옷이 만들어진다.

 

문제의 예시를 보면 [2, 7]과 [4, 5]으로 2개가 만들어진다.

6 //N
9 //M
2 7 4 1 5 3 // 고유 번호

 

 

2개의 고유 번호를 더해서 확인해야 되기 때문에 일일이 더하면서 확인하면 대략 N^2번을 체크할 것 같다.

 

M에서 첫번째 재료의 고유 번호를 뺀 값이 있으면 갑옷을 만들 수 있기 때문에 Set을 사용해서 페어가 있는지 확인하면 좋을 것 같다.

 

Set<Integer> elements = new HashSet<>();
List<Integer> numbers = new ArrayList<>();
int count = 0;

while (st.hasMoreTokens()) {
    int value = Integer.parseInt(st.nextToken());
    elements.add(value);
    numbers.add(value);
}

for (Integer num : numbers) {
    if (elements.remove(num) && elements.remove(M - num)) {
        ++count;
    }
}

 

고유한 번호이기 때문에 정렬을 하고 양쪽 끝에서 투 포인터로 숫자를 비교하면서 값을 구할 수도 있다.