[c++] 백준 1940번: 주몽

 

 

 

 

 

 

 

 

 

문제풀이

1. 첫 번째 문제 풀이에서는 정렬과 투 포인터를 사용하지 않고 이중 for문을 사용하여 문제를 해결했다.

2. 두 번째 문제 풀이에서는 정렬과 투 포인터를 사용하여 문제를 풀었더니 실행 시간이 빨라졌다.

2 - 1. 정렬을 한 후 맨 앞의 인덱스와 맨 끝의 인덱스를 포인터로 잡고

        해당 포인터 값의 합이 주어진 m보다 작으면 앞의 포인터를 한 칸 뒤로 옮긴다.

        m보다 크면 뒤의 포인터를 한 칸 앞으로 옮긴다.

        두 포인터 값이 같으면 result값을 증가 시키고 양 쪽 포인터를 옮긴다.

2 - 2. 두 포인터가 서로 엇갈리면 반복문을 빠져나온다.

 

 

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int n, m;
	int a[15000];

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	sort(a, a + n);

	int result = 0;
    
    // 첫 번째 풀이
	/*for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (a[i] + a[j] == m)
				result++;
		}
	}*/
	int start = 0, end = n - 1;
	
	while (start < end) {
		if (a[start] + a[end] < m)
			start++;
		else if (a[start] + a[end] > m)
			end--;
		else {
			result++;
			start++;
			end--;
		}
	}

	cout << result;

	return 0;
}