BOJ(C++) / 백준 20210 : 파일 탐색기

백준 20210 : 파일 탐색기

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

20210번: 파일 탐색기

 

문제

Windows의 파일 탐색기를 보면 파일이 정렬된 방식이 보통의 정렬 방식과는 다른 것을 알 수 있다.

보통 문자열을 정렬할 때는 맨 앞부터 한 글자씩 비교하다가 어느 한쪽이 끝나거나 일치하지 않는 글자가 있으면 그 위치의 문자를 비교한 결과가 문자열 전체를 비교한 결과가 된다. 한편 파일 탐색기는 여러 자리의 수를 한 글자로 취급해서 비교하는데, 이 때문에 "str12ing"과 "str123ing" 중 후자가 아니라 전자가 앞에 온다. 이러한 정렬 방식을 종종 "natural sort"라고 하기도 한다.

여러 개의 문자열이 주어지면 natural sort 방식으로 정렬한 결과를 출력하는 프로그램을 작성해 보자. 이 문제에서 구현할 알고리즘은 다음을 만족해야 한다.

1. 문자열은 알파벳 대소문자와 숫자로만 이루어져 있다.
2. 숫자열이 알파벳보다 앞에 오고, 알파벳끼리는 AaBbCc...XxYyZz의 순서를 따른다.
3. 문자열을 비교하는 중 숫자가 있을 경우 그 다음에 오는 숫자를 최대한 많이 묶어 한 단위로 비교한다. 예를 들어 "a12bc345"는 "a", "12", "b", "c", "345"의 다섯 단위로 이루어져 있다.
4. 숫자열끼리는 십진법으로 읽어서 더 작은 것이 앞에 온다. 이때 예제 2에서와 같이 값이 263을 초과할 수 있다.
5. 같은 값을 가지는 숫자열일 경우 앞에 따라붙는 0의 개수가 적은 것이 앞에 온다.

입력

첫 줄에 문자열의 개수 N(2 ≤ N ≤ 10,000)이 주어진다. 그 다음 N줄에 정렬할 문자열이 한 줄에 하나씩 주어진다.

모든 문자열의 길이는 100 이하이며, 알파벳 대소문자와 숫자로만 이루어져 있다.

 

출력

N줄에 걸쳐 문제에서 설명한 대로 문자열을 정렬한 결과를 출력한다.

 

코드

//백준 20210 파일 탐색기
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

bool cmp(vector<string>& a, vector<string>& b) {
	int min_size = min(a.size(), b.size());

	for (int i = 0; i < min_size; i++) {
		//두 문자가 같지 않을 때
		if (a[i] != b[i]) {
			//둘 다숫자일 때
			if (a[i][0] >= '0' && a[i][0] <= '9' && b[i][0] >= '0' && b[i][0] <= '9') {
				//앞 0없앤 진짜 수
				string a_num = "";
				string b_num = "";
				for (int j = 0; j < a[i].size(); j++) {
					if (a[i][j] != '0') {
						a_num = a[i].substr(j);
						break;
					}
				}
				for (int j = 0; j < b[i].size(); j++) {
					if (b[i][j] != '0') {
						b_num = b[i].substr(j);
						break;
					}
				}
				//수가 같을 때
				if (a_num == b_num) {
					//0이 더 많은 수 뒤로
					return a[i].size() < b[i].size();
				}
				//수가 다를 때
				else {
					// 3 , 12 비교 12 < 3이 큼
					if (a_num.size() < b_num.size())
						return true;
					else if (a_num.size() > b_num.size())
						return false;
					else {
						if (a_num < b_num)
							return true;
						return false;
					}
				}
			}

			//둘 중 하나가 숫자일 때
			if ((a[i][0] >= '0' && a[i][0] <= '9') || (b[i][0] >= '0' && b[i][0] <= '9')) {
				return a[i] < b[i];
			}

			//둘다 영어일 때
			if (toupper(a[i][0]) == toupper(b[i][0])) {
				return a[i] < b[i];
			}
			return toupper(a[i][0]) < toupper(b[i][0]); //대문자 변환 더 큰 값
		}
	}

	//비교할 수 있는 사이즈까지 똑같을 때 사이즈 작은 순으로 정렬
	return a.size() < b.size();
}

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

	int N;
	cin >> N;
	vector<vector<string>> v;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		vector<string> temp;
		string s_temp;
		for (int j = 0; j < s.size(); j++) {
			//숫자
			if (s[j] >= '0' && s[j] <= '9')
				s_temp += s[j];
			//숫자 이 외
			else {
				//숫자가 이미 저장되어 있을 때
				if (s_temp != "")
					temp.push_back(s_temp);
				s_temp = s[j];
				temp.push_back(s_temp);
				s_temp = "";//수 초기화
			}
		}
		if (s_temp != "")
			temp.push_back(s_temp);
		v.push_back(temp);
	}

	sort(v.begin(), v.end(), cmp);
	
	//출력
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v[i].size(); j++) {
			cout << v[i][j];
		}
		cout << "\n";
	}


	return 0;
}
//걸린 시간 : 3시간

설명

 

주석에서도 잘 설명했지만 다시 정리해서 설명해보면

• 입력받을 때 수와 문자를 구분하여 vector <vector <string>> 형태로 저장한다.
• 문제의 조건대로 정렬한다.
• 두 벡터를 비교할 때 더 작은 벡터 사이즈만큼 비교한다.  min_size만큼 비교해도 우선순위를 정하지 못하면 사이즈 크기 순으로 정렬(66줄)
• 반복문에서 비교할 두개의 벡터의 값을 같지 않을 때 어느 것이 더 우선순위에 있는지 비교해야 한다.
• 두 문자가 같지 않을 때는 둘 다 숫자일 경우, 하나만 숫자일 경우, 둘 다 영어일 경우로 나눠서 구분할 수 있다.

1. 둘 다 숫자일 경우 

• 숫자에서 앞에 0을 없앤 수로 비교한다. 두 수가 같을 경우에는 사이즈의 오름차순으로 정렬.(0이 더 많이 있는 수)
• 수가 다를 경우에는 사이즈를 비교하여 사이즈의 오름차순으로 정렬
• 사이즈가 같을 경우에는 오름차순으로 정렬
• 이렇게 하는 이유는 string에서 3과 12를 비교했을 때 3보다 12가 크지만 string에서는 12보다 3이 더 크다고 판단한다. 따라서 다음과 같이 구할 수 있다.(여기서 혼동되어.. 한 시간 버린 듯..)

2. 둘 중 하나만 숫자일 경우

• 숫자가 문자보다 우선순위가 높기 때문에 숫자 > 문자 순으로 정렬

3. 둘 다 영어일 경우

• 대문자로 변환하였을 때 알파벳순으로 정렬
• 대문자로 변환하였을 때 값이 같다면 대문자 > 소문자 순으로 정렬

조건이 많아서 어려웠지만 문제를 잘 읽고 조건을 잘 따라가다 보면 문제를 해결할 수 있다. 

고찰

걸린 시간 : 3시간(아마도 그 이상...?)

이렇게 오래 걸릴 문제가 아닌데 이상하게 엄청 오래 걸렸다. 생각하지 못한 부분들도 많았고 잘못 생각한 부분들도 있었다. 일단 0012 < 13에서 13이 더 큰데 사이즈로 비교했어서 틀렸었고 string에서 3과 12를 비교했을 때 3보다 12가 크지만 string에서는 12보다 3이 더 크다고 판단하는데 이 부분에서 시간으로 오래 잡아먹었다.

또한 invalid comparator라는 런타임 에러로 틀렸었는데 사실 아직도 왜 이런지 잘 모르겠다...? 

https://hanbi97.tistory.com/164

[C++] 비교함수 만들때 invalid comparator 에러

string 관련된 문제는 뭔가 나한테 계속 어렵게 느껴진다. 금방 풀릴 거 같은데 안 풀리고,,, 더 연습해야겠다.

 

난이도

Gold 2