[G5] 백준 3649번 로봇 프로젝트 C++ 투 포인터, 정렬

리뷰

 

https://www.acmicpc.net/problem/3649

투 포인터 말고 이분 탐색으로 풀려고 접근 했다가 틀렸다. 이분 탐색 접근이 정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다. 라는 조건이 좀 까다로운 것 같다.

 

 

전역 변수

• x : 구멍이 너비를 저장할 변수
• n : 레고 조각의 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. x를 입력 받는 것을 조건으로 while루프를 수행한다.
2. 매 루프마다 x에 1000만을 곱해주어 나노미터 단위로 변경해 준다.
3. 매 테스트 케이스 마다 n값을 입력 받고, 벡터 legos를 n크기로 초기화해 준다.
4. n개의 레고의 길이 정보를 legos벡터에 입력 받고, sort함수를 통해 legos벡터를 오름차순으로 정렬해 준다.
5. 변수 l을 0, r을 n - 1로 초기화 하고, flag를 false로 초기화해 준다.
6. l이 r보다 작을때를 조건으로 while루프를 수행한다.
7. 변수 sum을 legos[l]+legos[r]값으로 저장해 준다.
8. sum이 x보다 클 경우 r을 감소시킨다.
9. sum이 x보다 작을 경우 l을 증가시킨다.
10. sum이 x와 같을 경우 yes조건에 맞게끔 legos[l], legos[r]을 활용하여 출력 후 flag를 true로 변경, break처리해 준다.
11. while루프가 종료된 후 flag가 false라면 "danger"을 출력해 준다.

 

트러블 슈팅

1. legos를 뒤에서부터 순회하며 lower_bound를 통해 x - legos[i]가 일치하는 값이 존재하는지를 탐색했었다.
2. lower_bound의 범위를 legos.begin()~legos.begin()+i로 잡아주어 legos[i]가 중복 포함되지 않게끔 했다.
3. 이터레이터가 legos.begin()+i일 경우 일치하는 값이 없는 것으로 판단하였는데 음... 어떤 부분이 틀린진 모르겠다.
4. 그래서 그냥 이분 탐색을 접고 투 포인터로 접근하니 훨씬 직관적이고 쉬웠다. 시간도 O(N)으로 더 효율적인듯

 

참고 사항

1. 투 포인터 풀이로 최적해를 찾은 경우 더 이상 탐색해줄 필요가 없다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int x, n;

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

	while (cin >> x) {
		x *= 1e7;
		cin >> n;
		vector<int> legos(n);
		for (int i = 0; i < n; ++i) cin >> legos[i];
		sort(legos.begin(), legos.end());

		int l = 0, r = n - 1;
		bool flag = false;
		while (l < r) {
			int sum = legos[l] + legos[r];
			if (sum > x) r--;
			else if (sum < x) l++;
			else {
				cout << "yes " << legos[l] << " " << legos[r] << "\n";
				flag = true;
				break;
			}
		}

		if (!flag) cout << "danger\n";
	}
}