[S4] 백준 14911번 궁합 쌍 찾기 C++ 브루트포스 알고리즘, 정렬, Hash

리뷰

 

5달만에 다시 찾아와 깨부신 문제 파이썬에 비해 입력을 처리하는데 시간이 더 쓰인거 같다.

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

 

문제 풀이

1. 정수형 벡터 lst를 초기화 해주고 getline을 통해 첫 줄을 문자열로 받아와 준 뒤 두번째 줄은 정수 l에 저장해 준다.
2. 문자열 s를 stringstream타입 ss로 변환해 주고, 공백을 기준으로 문자를 뽑아 정수형으로 변환 시킨다.
3. 변환시킨 정수를 lst에 넣어준 뒤 length변수에 lst의 사이즈를 구해준다.
4. lst를 오름차순으로 정렬시킨 후 length!번의 브루트포스 알고리즘을 실행해 준다.
5. 만약 lst[i] + lst[j]가 l과 같다면 set에 해당 숫자 쌍을 추가해 준다.
6. 브루트포스가 끝나면 ans에 저장된 숫자 쌍을 모두 출력해 주고, ans의 size를 출력해 주면 된다.

 

참고 사항

lst를 sort해준 후 브루트포스를 진행하기에 ans에 저장되는 숫자쌍은 이미 오름 차순인 상태이다.

ans 역시 set 타입이므로 사실상 정렬 상태를 유지해 주긴 하지만 pair를 사용해 주기 위해 set을 사용하였다.

문제 상에서 첫째 줄에 들어올 값의 개수를 명시해 주지 않고 2 ~ 10개의 숫자가 주어진다고 되어 있기 때문에, 한 줄 전체를 받아온 뒤 공백을 통해 숫자를 분리해 주어야 한다. python에서는 split 하나로 끝날 걸..

 

정답 코드

#include<iostream>
#include<set>
#include<vector>
#include<string>
#include<sstream>
#include<algorithm>

using namespace std;

set<pair<int, int>> ans;

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

	vector<int> lst;
	string s; getline(cin, s);
	int l;  cin >> l;
	stringstream ss = stringstream(s);
	while (getline(ss, s, ' ')) lst.push_back(stoi(s));
	
	int length = lst.size();
	sort(lst.begin(), lst.end());
	for (int i = 0; i < length - 1; i++) {
		for (int j = i + 1; j < length; j++) {
			if (lst[i] + lst[j] == l) {
				ans.insert({ lst[i], lst[j] });
			}
		}
	}
	for (const auto& it : ans) cout << it.first << " " << it.second << "\n";
	cout << ans.size();
}