C++ / 백준 / 20210 / 파일 탐색기

문제

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

20210번: 파일 탐색기

문제풀이

단순 코딩이라 지저분하게 풀었다.

조건자체는 어려운 게 크게 없어 보이지만 0과 숫자가 2^63를 초과할 수 있단 점에서 고생을 했다.

조건이 많아 return 할 것이 많다 보니까 반례의 문자열 순서에 따라 답이 다르게 나오는 경우도 있었다.

문제를 제출한 사람이 거의 없어서 반례를 찾는데도 고생했다.

 

숫자와 알파벳이 오면 숫자가 더 앞에 온다.

같은 알파벳인 경우 대문자가 더 앞에 온다.

 

둘 중에 숫자가 있을 경우 문자열이 끝나거나 알파벳이 있기 전까지 숫자를 모두 입력받는다.

숫자가 같지 않은 경우에만 서로를 비교해서 return 한다.

둘 다 알파벳인 경우 tolower를 이용해 대소를 비교하고 return 한다.

인덱스가 둘 중 하나의 사이즈를 넘기면 사이즈가 앞에 두도록 return 한다.

 

숫자를 입력받을 때 stoi 등을 통해 비교하면 좋겠지만 숫자가 2^63을 초과할 수 있으므로 string형으로 비교를 해야 한다.

숫자를 입력받을 때 앞자리가 0일 때만 n에 입력받고 그 외에는 r에도 입력받았다.

n은 입력받은 숫자, r은 앞에 0이 없는 숫자이다.

 

if (idx >= s1.size() || idx >=s2.size()) {
	return s1.size() < s2.size();
}

아래의 조건문에서 모든 경우를 판별하므로 인덱스가 벡터를 넘겼다면 사이즈가 작은 것이 앞으로 오도록 return 한다.

 

else if (isdigit(s1[idx]) || isdigit(s2[idx])) {
		n1 = "", r1 = "", n2 = "", r2 = "";
		idx2 = idx;
		while (isdigit(s1[idx2])) {
			if (s1[idx2] == '0' && !r1.empty()) {
				r1 += s1[idx2];
			}
			else if (s1[idx2] != '0') {
				r1 += s1[idx2];
			}
			n1 += s1[idx2];
			++idx2;
		}
		idx2 = idx;
			while (isdigit(s2[idx2])) {
			if (s2[idx2] == '0' && !r2.empty()) {
				r2 += s2[idx2];
			}
			else if (s2[idx2] != '0') {
				r2 += s2[idx2];
			}
			n2 += s2[idx2];
			++idx2;
		}

둘 중 하나가 숫자인 경우이다.

isdigit함수를 이용해서 해당 문자가 숫자인지 판별한다. (참이면 true를 거짓이면 0을 반환한다.)

해당 문자가 0일 경우 숫자의 맨 앞에 오는 0인지, 중간에 껴있는 0인지를 확인하고

맨 앞에 오는 0이 아니라면 r1에도 더한다. n1에는 모든 숫자를 더한다.

s1, s2 두 문자열 모두 작업을 한다.

 

		if (n1.empty()) {
			return false;
		}
		else if (n2.empty()) {
			return true;
		}
		else {
			if (n1 == n2);
			else if (r1 == r2) {
				return n1.size() < n2.size();
			}
			else if (r1.size() == r2.size()){
				return r1 < r2;
			}
			else {
				return r1.size() < r2.size();
			}
		}

위에 이어진 코드다.

위의 else if (isdigit(s1[idx]) || isdigit(s2[idx])) { 에서 둘 중에 하나는 숫자이므로

n1이 비어있다면 s1[idx]는 알파벳이고, s2[idx]는 숫자이지만, 둘의 위치를 바꿔야 해서 false를 return 한다.

n2이 비어있다면 s1[idx]는 숫자, s2[idx]는 알파벳이므로 true를 return 한다.

 

그 이외의 경우는 둘 다 숫자이다.

문자열은 정수형과 다르게 크기를 비교하므로 주의해서 조건문을 짜야한다.

n1과 n2가 같으면 idx까지는 둘은 같은 문자열이므로 return을 할 수 없다.

0으로 시작하지 않는 숫자인 r1과 r2이 같으면 더 작은 사이즈가 앞에 오도록 return 한다.

r1과 r2이 다르지만 크기가 같을 때는 더 작은 수가 오도록 return 한다.

나머지 경우는 크기가 작은 것이 앞에 오도록 return 하면 된다.

 

	else if (!isdigit(s1[idx]) && !isdigit(s2[idx])) {
		if (s1[idx] == s2[idx]);
		else if (tolower(s1[idx]) == tolower(s2[idx])) {
			return s1[idx] < s2[idx];
		}
		else {
			return tolower(s1[idx]) < tolower(s2[idx]);
		}
	}

마지막으로는 둘 다 알파벳일 경우이다.

알파벳이 같고, 대소문자가 같으면 넘긴다.

아스키코드값에서는 대문자가 값이 작고, 소문자가 값이 크므로 둘 다 소문자로 바꾼 뒤 비교를 한다.

소문자로 변경한 값이 같으면 하나는 대문자, 하나는 소문자 이므로 대문자가 앞에 오도록 return 한다.

그 외의 경우는 소문자로 변경한 값이 작은 것이 앞에 오도록 return 한다.

 

코드

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

bool cmp(string s1, string s2) {
	int idx(0), idx2(0);
	string n1(""), r1(""), n2(""), r2("");
	while (1) {
		if (idx >= s1.size() || idx >= s2.size()) {
			return s1.size() < s2.size();
		}
		else if (isdigit(s1[idx]) || isdigit(s2[idx])) {
			n1 = "", r1 = "", n2 = "", r2 = "";
			idx2 = idx;
			while (isdigit(s1[idx2])) {
				if (s1[idx2] == '0' && !r1.empty()) {
					r1 += s1[idx2];
				}
				else if (s1[idx2] != '0') {
					r1 += s1[idx2];
				}
				n1 += s1[idx2];
				++idx2;
			}
			idx2 = idx;

			while (isdigit(s2[idx2])) {
				if (s2[idx2] == '0' && !r2.empty()) {
					r2 += s2[idx2];
				}
				else if (s2[idx2] != '0') {
					r2 += s2[idx2];
				}
				n2 += s2[idx2];
				++idx2;
			}
			if (n1.empty()) {
				return false;
			}
			else if (n2.empty()) {
				return true;
			}
			else {
				if (n1 == n2);
				else if (r1 == r2) {
					return n1.size() < n2.size();
				}
				else if (r1.size() == r2.size()) {
					return r1 < r2;
				}
				else {
					return r1.size() < r2.size();
				}
			}
		}
		else if (!isdigit(s1[idx]) && !isdigit(s2[idx])) {
			if (s1[idx] == s2[idx]);
			else if (tolower(s1[idx]) == tolower(s2[idx])) {
				return s1[idx] < s2[idx];
			}
			else {
				return tolower(s1[idx]) < tolower(s2[idx]);
			}
		}
		++idx;
	}
}

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

	int N(0), idx(0);
	cin >> N;
	vector<string>words(N, "");

	for (idx = 0; idx < N; ++idx) {
		cin >> words[idx];
	}

	sort(words.begin(), words.end(), cmp);

	for (idx = 0; idx < N; ++idx) {
		cout << words[idx] << '\n';
	}
}