JAVA_투포인터 알고리즘1_주몽의 명령

자바 알고리즘-  투포인터 활용 알고리즘

시간 제한	메모리 제한
2 초	128 MB

▶ 문제

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

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

 

▶ 나의 문제풀이 

우선 이번 문제에서는 Scanner 대신에 BufferedReader를 사용했습니다.

숫자를 받으려면?

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

int n = Integer.parseInt(bf.readLine());

 

핵심

// 7. 두 배열의 포인터가 만나지 않을때까지 돌면서
while (i < j) {
  if (array[i] + array[j] < M) {
  i++;
} else if (array[i] + array[j] > M) {
  j--;
} else {
//계속해서 포인터를 움직이면서 비교하기
  count++;
  i++;
  j--;
}}

 

<그냥,, 어려운 용어 정리>

1. StringTokenizer 사용목적
BufferedReader는 잘라서 배열과 같이 인덱스를 사용하여 접근하여 사용.
StringTokenizer는 공백이 있다면 뒤에 문자열이 공백 자리를 땡겨 채우도록 한다.
StringTokenizer가 BufferedReader보다 빠르게 사용될 수 있다.
문자열을 자르게 위해 split을 사용할땐, split은 정규식을 기반으로 자르는 로직으로서 내부는 복잡하다. 

그에 비해 StringTokenizer의 nextToken()메소드는 단순히 공백 자리를 땡겨 채우는 것이다. 

그렇기 때문에 속도 차이가 날 수 밖에 없다.
정규식이나 인덱스 접근과 같은 처리가 필요없다면 StringTokenizer를 사용하는 것이 효율적이다.

 

2. split VS StringTokenizer의 nextToken
StringTokenizer는 공백이 있다면 뒤에 문자열이 공백 자리를 땡겨 채우도록 한다.
StringTokenizer가 BufferedReader보다 빠르게 사용될 수 있다.
문자열을 자르게 위해 split을 사용할땐, split은 정규식을 기반으로 자르는 로직으로서 내부는 복잡하다. 

그에 비해 StringTokenizer의 nextToken()메소드는 단순히 공백 자리를 땡겨 채우는 것이다. 

정규식 처리가 딱히 필요한게 아닌 경우 StringTokenizer가 효율적이다.
정규식이나 인덱스 접근과 같은 처리가 필요없다면 StringTokenizer를 사용하는 것이 효율적이다.

 

결론적으로 Scanner 보다 BufferedReader을 사용하면 속도가 빨라집니다.

문자열에 최적화 된 BufferedReader에 비해 Scanner는 다양한 기능을 지원해서 무겁기 때문입니다.

같은 문제를 풀었을 때, Scanner와 BufferedReader를 사용했을 때의 처리속도차이
BufferedReader를 사용했을시, 거의 절반까지 (ex. 112MS -> 92MS)로 처리속도 단축되는 것이 확인이 됩니다.

 

 

 

▶ 나의 코드 

package algorithm.doit;

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

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

	public static void main(String[] args) throws IOException {
		// ( a )+ ( b )= M
		// 배열 = {a,b};

		// Scanner를 사용하지 않고 InputStreamReader를 사용한다.
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		// 1. N에 가지고 있는 재료의 개수를 적는다.
		System.out.println("현재 가지고 있는 재료의 개수를 적으시오!!");
		int N = Integer.parseInt(bf.readLine());

		// 2. 갑옷이 만들어져야하는 수를 M 에 저장한다.
		System.out.println("갑옷의 가격은?!!");
		int M = Integer.parseInt(bf.readLine());

		// 3. 재료의 개수만큼 반복하여 배열에 저장한다.
		int[] array = new int[N];

		// 4. StringTokenizer를 사용하여들어오는 다음 값을 st에 저장한다.
		System.out.println("재료는 띄어쓰기 해서 하나씩 입력하세요 예시) 2 7 4 1 5 3");
		StringTokenizer st = new StringTokenizer(bf.readLine());
		// for 문을 돌면서 N개만큼의 수를 받아 배열에 저장한다.
		for (int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}


		// 5. 들어온 수를 Sort를 해준다.
		Arrays.sort(array);

		// 6. 각각 count를 하는 변수를 초기화한다.
		int count = 0;
		int i = 0;
		int j = N - 1;
		// j는 들어오는 N개보다 1를 뺸 값을 저장한다,
		// 즉 배열의 뒤에서 부터 포인터를 돈다는 뜻!!!!

		// 7. 두 배열의 포인터가 만나지 않을때까지 돌면서
		while (i < j) {
			if (array[i] + array[j] < M) {
				i++;
			} else if (array[i] + array[j] > M) {
				j--;
			}else {
				//계속해서 포인터를 움직이면서 비교하기
				count++;
				i++;
				j--;
			}
		}
		System.out.println(count);
		bf.close();
	}

}

 

 

 

 

 

<참고>

책: do it 알고리즘 코딩 테스트 자바편

코딩 테스트: https://www.acmicpc.net/