[백준]1940 주몽(투포인터 응용문제)

저번 게시물에서 투 포인터에 관한 문제를 살펴보았죠? 이번엔 그걸 응용한 실전 문제를 풀어보았습니다.

인프런 do it! 코딩테스트 자바 강의를 참고한 것임을 알립니다.

https://www.inflearn.com/course/%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%90%EB%B0%94

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA | 하루코딩 - 인프런

 

문제 링크

https://www.acmicpc.net/problem/1940

 

문제

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

 

풀이

일단 정렬을 하고 투 포인터로 해결했습니다. 정렬을 할 때 개수 제한이 15000이기 때문에 O(nlogn)을 해도 시간 복잡도에 문제가 없습니다!! 배열을 양 끝단을 index로 두고 양 쪽에서 안으로 들어오기 때문에 반복문에서 시간 복잡도는 O(n)그러므로 총 시간 복잡도는 O(nlogn)이라 문제없습니다.

 

코드

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

public class Back_2018주몽의명령 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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 stringTokenizer = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			A[i] = Integer.parseInt(stringTokenizer.nextToken());
		}
		Arrays.sort(A);
		int count =0;
		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 {
				count++;
				i++;j--;
			}
		}
		System.out.print(count);
	
	}

}

 

회고

항상 Scanner만 써서 입력을 받아왔었습니다. BufferedReader는 코테 공부를 하며 처음 써본 것인데, 그것에 대한 지식이 부족에 코드를 작성하는데 헷갈림이 많았습니다. BufferedReader와 StringTokenizer에 대한 내용은 따로 게시물로 정리하도록 하겠습니다. 시간 복잡도에 대한 내용도 점점 이해가 가고 있습니다.