백준 1940: 주몽(java/python)

문제

---

풀이

 

이중 for문을 사용해, i를 기준으로 j를 i부터 N까지 1씩 증가시키며 i번째 원소와 j번째 원소의 합이 M이 될 때 count++하는 풀이를 떠올릴 수 있지만, 이 방식은 \(O(N^{2})\)의 시간 복잡도를 가지므로 시간 초과 오류가 표시된다.

//오류 코드
for(int i=0; i<N; i++) {	//i 루프: N번 실행
	for(int j=i; j<N; j++) {	//j 루프: (N-i) 번 실행
		if(materials[i]+materials[j]==M) {
			count++;
		}
        //N*(N-i)번 실행되므로 시간복잡도는 O(N^2)
        ...
        
	}
}

 

따라서 배열을 정렬한 후, 시간 복잡도가 \(O(N)\)인 투 포인터 기법을 활용해야 한다.

(길이가 N인 배열 내에서 탐색하는 투 포인터 기법에서 왼쪽 인덱스와 오른쪽 인덱스를 각각 left, right라 했을 때, 항상 left < right이고 left와 right는 최대 N번의 이동 횟수를 가지므로 \(O(N)\))

 

투 포인터 기법을 사용해 재료 배열 materials[] 내에서 합이 M인 두 원소를 찾는 알고리즘을 작성하면 아래와 같다. 탐색하기 전에 materials[] 배열을 오름차순으로 정렬했음에 주의해야 한다.

int left=0, right=N-1;	//좌, 우 인덱스
int count=0, sum=0;	//count=갑옷 개수
	
while(left<right) {
	sum=materials[left]+materials[right];		//배열 양 끝에서부터 진행
			
	if(sum==M) {	//두 원소 합이 M이면
		count++;
		left++;
		right--;
	}
	else if(sum>M) {	//sum이 M보다 크면 sum값을 낮춰야 하므로
		right--;	//오른쪽 인덱스를 1 감소시킨 후 다시 탐색
	}
	else {	//sum이 M보다 작으면 sum값을 키워야 하므로
		left++;	//왼쪽 인덱스를 1 증가시킨 후 다시 탐색
	}
}

 

전체 코드

 

1. java

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

public class Main {
	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[] materials=new int[N];
		
		for(int i=0; i<N; i++) {
			materials[i]=Integer.parseInt(st.nextToken());
		}
		Arrays.sort(materials);
		
		int left=0, right=N-1;	
		int count=0, sum=0;
	
		while(left<right) {
			sum=materials[left]+materials[right];	
			
			if(sum==M) {
				count++;
				left++;
				right--;
			}
			else if(sum>M) {
				right--;
			}
			else {
				left++;
			}
		}
		
		System.out.println(count);
	}
}

 

2. python

N=int(input())
M=int(input())
materials=list(map(int, input().split()))

materials.sort()

left = 0
right = N-1

count = 0
sum = 0

while left < right:
    sum = materials[left]  + materials[right]

    if sum == M:
        count+=1
        left+=1
        right-=1
    elif sum > M:
        right-=1
    else:
        left+=1

print(count)