[Java/백준] 주몽 #1940

문제

 

 

 

풀이

(1) 문제 분석하기

• 두 재료의 번호의 합, 크기를 비교하므로 먼저 정렬하고 시작
• N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘(=정렬 알고리즘)을 사용해도 문제없음
• 정렬한 다음 양쪽 끝의 위치를 투 포인터로 지정해 접근(데이터가 유니크하고 한 번 쓰면 없어진다? → 투 포인터)

 

(2) 손으로 풀어 보기

출처 : Do it! 알고리즘 코딩 테스트 - 실전문제 풀이(JAVA)

1. 재료 데이터를 A[N]에 저장한 후 오름차순으로 정렬
2. 투 포인터 i, j를 양쪽 끝에서부터 포인터 이동 원칙에 맞게 탐색
3. 2단계를 i와 j가 만날 때까지 반복, 반복이 끝나면 count 출력
   (N번만에 탐색이 끝남, 투 포인터는 시간 복잡도에 영향이 거의 없음)

// 투 포인터 이동 원칙
A[i] + A[j] > M : j--; // 번호의 합이 M보다 크면 큰 번호 index를 내림
A[i] + A[j] < M : i++; // 번호의 합이 M보다 작으면 작은번호 index를 올림
A[i] + A[j] == M : i++; j--; count++; // 번호의 합과 M이 같으면 양쪽 포인터 모두 이동, count 증가

 

(3) 슈도코드 작성하기

N(재료의 개수), M(갑옷이 되는 번호) 저장하기
for(N만큼 반복) {
	재료 배열 저장하기
}
재료 배열 정렬하기
while(i < j) {
	if(재료의 합 < M) 작은 번호 index 올리기
	else if(재료의 합 > M) 큰 번호 index 내리기
	else 양쪽 index 이동, count 증가시키기
}
count 출력하기

 

(4) 코드 구현하기

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


public class Jumong1940 {

	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());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int A[] = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.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 {
				i++;
				j--;
				count++;
			}
		}
		System.out.println(count);
	}

}

 

(번외) 2중반복문과 투 포인터는 얼마나 차이 날까?

차례대로 투 포인터를 이용한 방법, 2중 반복문을 이용한 방법

• 처음에는 2중반복문을 생각했지만 시간 복잡도를 고려하면 좋은 방법이 아님
• 투 포인터는 대부분 정렬을 해야 되거나, 데이터가 정렬인 채 주어진 경우가 많음
• 투 포인터의 이동 원칙은 문제에 맞게 설정할 것!

 

 

 

1940번: 주몽

 

※ 이 내용은 Do it! 알고리즘 코딩테스트 - 실전문제 풀이(JAVA) 강의를 듣고 정리한 내용입니다.