백준 1940 문제풀이
in Computer Science on Algorithm
문제 링크
https://www.acmicpc.net/problem/1940
문제 설명
주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.
문제 분석
주어진 문제는 두 개의 재료 고유 번호를 합쳐 특정 값 ( M )을 만들 수 있는 조합의 개수를 찾는 것이다. 여기서 ( M )의 범위가 1에서 10,000,000까지라는 점은 문제 해결에 중요한 고려사항이 된다. 재료의 고유 번호가 ( M )에 비해 상대적으로 클 경우 유효한 조합을 찾기가 어려울 수 있다. 이 문제를 해결하기 위해 ( O(N^2) )의 시간 복잡도를 가진 이중 for문을 사용하는 것은 바람직하지 않다. ( N )이 최대 15,000일 경우, 이중 for문을 사용하면 최악의 경우 약 2억 번의 연산이 필요하므로 매우 비효율적이다.(1초에 1억번의 연산이라 생각하면 쉽다) 따라서 성능 저하와 시간 제한 문제를 피하기 위해 효율적인 알고리즘이 필요하다. 효율적으로 문제를 해결하기 위해 투 포인터 알고리즘을 적용하는 것이 적합하다. 재료의 고유 번호를 정렬한 후, 두 개의 포인터를 사용하여 한 포인터는 배열의 시작 부분에, 다른 포인터는 끝 부분에 위치시킨다. 두 포인터가 가리키는 값의 합을 계산하여 ( M )과 비교하고, 합이 ( M )보다 작으면 왼쪽 포인터를 오른쪽으로, 크면 오른쪽 포인터를 왼쪽으로 이동시킨다. 합이 ( M )과 같다면 조합을 찾은 것이므로 카운트를 증가시키고 두 포인터를 조정한다.
코드
import java.util.*;
import java.io.*;
public class P1940 {
static int n,m;
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(bf.readLine());
m = Integer.parseInt(bf.readLine());
List<Integer> list = new ArrayList<>();
StringTokenizer st = new StringTokenizer(bf.readLine());
while(st.hasMoreTokens()){
list.add(Integer.parseInt(st.nextToken()));
}
Collections.sort(list);
int count = 0;
int start_index = 0;
int end_index = n - 1;
while(start_index < end_index){
int sum = list.get(start_index) + list.get(end_index);
if(sum == m){
count++;
start_index++;
end_index--;
} else if(sum < m){
start_index++;
} else {
end_index--;
}
}
System.out.println(count);
}
}
간만에 자바로 코딩테스트를 준비해야 할 일이 있어서 자바로 문제풀이를 시작했다. 자바로 하니까 생각보다 코드가 길어졌다;; 그래도 알고리즘의 적용은 비슷하니 어서 문법에 익숙해져야겠다.