14행 코드AC-문제풀이 5-4교환학생(Foreign Exchange, UVa 10763)-문제풀이 보고서

적은 코드로 효율적인 표현을 하도록 격려하다

제목(제출) 링크→UVa-10763
이 문제는 물문제이기 때문에 중심은 문제풀이에서 최적화로 바뀌었다.
제목: 첫 번째 열의 숫자가 두 번째 열의 숫자와 같은지 판단한다(난서).문제풀이의 방향이 다양하고 탐구할 만하다. 1. 맵 해시표 해법: 정의map cnt;. 그 중에서 cnt[i]는 학교 i에 대응하는 인원수 증감 변화량을 나타낸다. 만약에 학교 i를 출발지로 삼는 사람이 있다면cnt[i]--.목적지로 삼으면cnt[i]++.최종적으로 각 학교의 변화량이 모두 0이면 프로젝트가 가능하다는 것을 설명한다.그렇지 않으면 안 된다.특징: 시간, 공간의 복잡도는 모두 O(n)로 모두 동태적으로 개척되고 기수가 작다.상등의 해법을 위해.2,vector+sort 해법: 두 개의vector 용기로 각각 제1열과 제2열의 데이터를 저장한다.입력이 완료된 후 정렬, if (v1 = v2), YES 를 입력합니다.특징: 시간 복잡도는 O(nlogn)이고 공간 복잡도는 O(n)이지만 동적 개척으로 기수가 작다.중등 해법을 위해3. 수조 해법: 두 개의 대수조a[50W],b[50W]를 열고 0을 배치하여 각각 제1열과 제2열의 숫자를 저장한다.예를 들어 23을 입력하면a[2]++,b[3]++;마지막으로 처음부터 끝까지 훑어보면if(a[i] != b[i]), NO다.특징: 시간, 공간의 복잡도는 O(n)이지만 기수가 크다(50w)는 하등 해법이다.
하등의 해법은 너무 형편없기 때문에 여기서는 중등, 상등의 해법만 제시한다.

vector+sort 해법:

#include
using namespace std;
int main() {
	int n; while((cin >> n) && n) {
		vector<int> v1, v2; 
		for(int i = 0; i < n; i++) {
			int x1; cin >> x1; v1.push_back(x1);
			int x2; cin >> x2; v2.push_back(x2);
		}
		sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end());
		cout << ((v1 == v2) ? "YES
" : "NO
"); 
	} 
	return 0;
} 

map 해시 표 매핑 해법:

#include
using namespace std;
int n, a, b;
int main() {
	while(cin >> n && n != 0) {
		map<int, int> cnt;			//              
		for(int i = 0; i < n; i++) {
			cin >> a >> b;
			cnt[a]--;  cnt[b]++;	//         。 
		} 
		bool isWork = true;			//      
		for(auto p : cnt) 
			if(p.second != 0) {
				isWork = false;
				break;
			}
		cout << (isWork ? "YES
" : "NO
");  
	}
	return 0;
}

하늘은 영원히 어두워지지 않을 것이다. 먹구름이 흩어질 때 푸른 하늘의 찬란한 햇빛이 대지를 밝게 비추고 푸른 풀은 여전히 신선하고 푸르며 꽃은 여전히 왕성하게 피어날 것이다. 啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊--평범한 세상