백준 1940번 주몽 (c++)

1940번: 주몽

문제 분석

N개의 갑옷 재료 중, 두개의 조합으로 M을 만드는 문제이다. 투 포인터를 사용하여, 원소 두 개의 조합이 목표로 하는 숫자가 되는가를 확인하면 되는 문제이다.

문제 풀이를 총 2가지를 가져왔다.

투포인터를 이용한 풀이와 그렇지 않은 풀이이다.

투 포인터에 대해 알고싶다면 아래 링크로 공부해보자.

[Algorithm] 투 포인터(two pointer) 완.전.정.복

---

1. 투포인터를 이용하지 않은 풀이

#include <iostream>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, num = 0;
	cin >> N >> M;
	vector<int> vec(N);
	for (int i = 0; i < N; i++) {
		cin >> vec[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (vec[i] + vec[j] == M) 
				num++;
		} // 받은 배열의 모든 경우의 수를 보면서, M과 같으면 ++하도록 함.
	}

	cout << num;
	return 0;
}

c++로 풀었을 때는 맞으나, python으로는 틀린 코드이다.

받은 배열의 모든 조합을 보면서, M과 같으면 1씩 증가시키도록 한 코드이다. 문제를 처음 보자마자 직관적으로 풀어낸 풀이라 효율적인 측면에서는 떨어진다.

---

2. 투 포인터를 이용한 풀이⭐

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, num = 0;
	cin >> N >> M;
	vector<int> vec(N);
	int start = 0, end = N - 1; 
    // start : 시작점, end : 배열의 끝

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

	sort(vec.begin(), vec.end());
   	// 투 포인터를 이용하기 위해 정렬함.

	while (start < end) {
		if (vec[start] + vec[end] > M) {
			end--;
		} // 오름차순이기에, 끝부분을 --하면 작아진 숫자를 가리킬 수 있다.
		else if (vec[start] + vec[end] < M) {
			start++;
		}// 시작부분이기에, ++하면 큰 숫자를 가리킬 수 있다.
		else {
			num++;
			start++;
			end--;
		} 
        // 숫자가 서로 겹쳐지지 않기에 경우의 수에서 제외하고자
        // 두 포인터 모두를 이동시킨다
	}

	cout << num;
	return 0;
}

투 포인터를 사용하게 된다면, 살펴보아야 할 전체 경우의 수가 줄어들게 되므로, 시간복잡도가 O(n^2)d에서 O(nlogn)으로 줄어들게 된다. (sort함수의 시간복잡도가 O(nolgn)이다.) 아래 사진은 두 코드의 통과 화면과 시간복잡도의 차이를 보여준다.

첫번쨰가 투폳인터, 두번째가 그렇지 않은 것

코드 리뷰는 언제나 환영입니다!