[백준] 9417번 최대 GCD C++ 코드

코드

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

using namespace std;

int n;
string s;

// 유클리드 호제법, 최대공약수 구하기
int gcd(int x, int y) {
	while (y) {
		int tmp = x;
		x = y;
		y = tmp % y;
	}
	return x;
}

// 문자열 파싱
vector<string> split(string s, string sp) {
	vector<string> v;
	long long idx = -1;
	while ((idx = s.find(sp)) != string::npos) {
		string tmp = s.substr(0, idx);
		v.push_back(tmp);
		s.erase(0, idx + sp.length());
	}
	v.push_back(s);
	return v;
}

int main() {
	cin >> n;
	cin.ignore();
	while (n--) {
		int res = 0;
		getline(cin, s);
		vector<string> v = split(s, " ");
        // 조합 구하기
		for (int i = 0; i < v.size(); i++) {
			for (int j = i + 1; j < v.size(); j++) {
				res = max(res, gcd(stoi(v[i]), stoi(v[j])));
			}
		}
		cout << res << '\n';
	}
	return 0;
}

풀이

테스트케이스를 파싱하는 게 일이었던 문제. C++에서는 split 함수가 따로 없어서 직접 구현해야한다. 파싱할 문자열과 나눌 기준이 되는 문자열 (이를테면 " ")을 인자로 두고 split 함수를 구현했다.

 

find함수를 이용해 기준이 되는 문자열을 찾아주고 거기까지 substr을 이용해 문자열을 만들어준다. 그 후 벡터에 넣어주고 문자열을 지워준다. 그리고 마지막 문자열을 벡터에 넣어주면 split 함수가 완료된다. 파싱을 쉽게 하려면 Python을 사용하는 게 좋겠다...

 

문자열을 파싱하면 다음은 수의 조합 중에 가장 큰 최대공약수를 구해주면 된다. 최대공약수는 유클리드 호제법을 이용해서 구했다. 참고로 최소공배수는 a * b / gcd(a, b)로 구할 수 있다.

 

getline을 이용해서 한 줄을 받아줬는데, 이 함수를 사용할 때 주의해야할 점이 있다. cin을 이용해서 입력을 받으면 버퍼에 '\n'가 저장되어있는데, 이를 지워줘야한다. 그래서 cin.ignore()를 이용해주었고 다음에 getline(cin, s)를 이용해서 입력값을 받았다. 참고로 string헤더에 있는 getline 함수를 사용했다.