[백준][C++] 20210 파일 탐색기

20210. 파일 탐색기

20210번: 파일 탐색기

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

단계단계 차례차례 조건을 해결해가는 게 엄청 재미있었던 문제! 구현할 코드가 많았지만, 그렇게 어려워하면서 풀지는 않았다. 예쁘장한 코드를 짜진 못했지만...

알고리즘 설계!

algorithm 헤더의 sort에 들어가 cmp 함수를 구현하는 데 집중했다.

 

1. 비교할 문자 2개의 길이 중 큰 길이로 반복문을 돌린다!

 

2. 어느 하나라도 문자이고 둘이 같지 않다면, 2개의 비교를 해준다.

if ((isalpha(str1[i]) || isalpha(str2[i])) && str1[i] != str2[i])...

• 만약 한쪽이 숫자라면, 숫자인 쪽이 더 위로 정렬된다.

// 문자 < 숫자
if (isdigit(str1[i]) || isdigit(str2[i]))
{
   return isdigit(str1[i]);
}

• 둘 다 문자라면, AaBbCc...Zz 순으로 정렬한다. 정수로 바꿔 더 작은 쪽이 위로 정렬된다.

// a = 0, A = 0... b = 1, B = 1
char temp1 = (isupper(str1[i])) ? str1[i] - 'A' : str1[i] - 'a';
char temp2 = (isupper(str2[i])) ? str2[i] - 'A' : str2[i] - 'a';

// 같은 문자라면 (a, A)
// 대문자가 위로 정렬
if (temp1 == temp2)
{
   return isupper(str1[i]);
}

// a to z 문자 정렬
return temp1 < temp2;

 

3. 둘 다 숫자라면 숫자로 비교한다.

• 비교할 문자 모두 숫자가 0부터 시작된다면, 0의 개수를 각각 세어주고 string에서 erase 해준다.

int zCnt1 = 0, zCnt2 = 0;

while (str1[i] == '0')
{
    str1.erase(str1.begin() + i);
    zCnt1++;
}
while (str2[i] == '0')
{
    str2.erase(str2.begin() + i);
    zCnt2++;
}

• 만약 한 문자열의 현재 값이 먼저 알파벳이 됐을 때, 자릿수가 더 작다는 뜻이므로 위로 정렬해준다.

if (isalpha(str1[i]) || isalpha(str2[i]))
{
	return isdigit(str2[i]);
}

• 만약 두 숫자의 길이가 같고, 값이 같지 않을 때 작은 자릿수의 숫자가 더 작았던 문자열이 숫자가 더 작은 문자열이므로 위로 정렬해준다.

// 숫자가 큰 쪽
// state == 1 > false, 2 > true
// 기본값 0
if (state == 0 && str1[i] != str2[i])
{
 state = 1 + (str1[i] < str2[i]);
}

// 나중에 비교할 때
if (state)
 return (state - 1);

• 두 숫자의 길이가 같고, 값이 같을 땐 비교하기 전 세주었던 0의 개수가 더 작은 쪽이 위로 정렬되게끔 해준다.

if (zCnt1 != zCnt2)
return zCnt2 > zCnt1;

 

4.  정렬이 아직 되지 않았다면, 길이가 더 짧은 문자열이 위로 정렬된다.

return str1.size() < str2.size();

설명이 조금 불친절하긴 하지만... 이렇게 설계를 해봤다.

전체 코드를 보자.

main

int main()
{
	int len;

	cin >> len;
	strs.resize(len);

	for (int i = 0; i < len; i++)
	{
		cin >> strs[i];
	}

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

	for (string s : strs)
	{
		cout << s << '\n';
	}
}

cmp function

bool cmp(string str1, string str2)
{
	bool isGreater = true;
	int maxSize = max(str1.size(), str2.size());

	for (int i = 0; i < maxSize; i++)
	{
		if (i >= str1.size() || i >= str2.size()) break;

		// 그냥 문자
		if ((isalpha(str1[i]) || isalpha(str2[i])) && str1[i] != str2[i])
		{
			// 문자 < 숫자
			if (isdigit(str1[i]) || isdigit(str2[i]))
			{
				return isdigit(str1[i]);
			}

			char temp1 = (isupper(str1[i])) ? str1[i] - 'A' : str1[i] - 'a';
			char temp2 = (isupper(str2[i])) ? str2[i] - 'A' : str2[i] - 'a';

			if (temp1 == temp2)
			{
				return isupper(str1[i]);
			}

			// a to z 문자 정렬
			return temp1 < temp2;
		}

		// 숫자 비교
		else if (isdigit(str1[i]) && isdigit(str2[i]))
		{
			int zCnt1 = 0, zCnt2 = 0;
			int state = 0;

			while (str1[i] == '0')
			{
				str1.erase(str1.begin() + i);
				zCnt1++;
			}
			while (str2[i] == '0')
			{
				str2.erase(str2.begin() + i);
				zCnt2++;
			}

			while (isdigit(str1[i]) || isdigit(str2[i]))
			{
				if ((i >= str1.size() || i >= str2.size()) && str1.size() != str2.size())
				{
					return (str1.size() < str2.size());
				}

				// 자릿수가 더 큰 쪽이 위로
				if (isalpha(str1[i]) || isalpha(str2[i]))
				{
					return isdigit(str2[i]);
				}

				// 숫자가 큰 쪽
				if (state == 0 && str1[i] != str2[i])
				{
					state = 1 + (str1[i] < str2[i]);
				}

				i++;
			}

			if (state)
				return (state - 1);

			if (zCnt1 != zCnt2)
				return zCnt2 > zCnt1;

			i--;
		}
	}

	return str1.size() < str2.size();
}

딱 봐도 잘 쓰고 예쁜 코드는 아니지만... 나름 잘 해결해낸 것 같다! 단계별로 차근차근 풀어야하는 문자열 문제의 참맛을 알 수 있었다!

기분이 좋다 ㅎㅎ b ^_^ d

그리 길지 않았던 문자열 추천 문제의 대장정이 끝나고... 나는 내가 부족한 다이나믹 프로그래밍 쪽을 풀어보려고 한다. dp는 조금 겁나긴 하지만... 언젠가 허물어야 할 벽이기 때문에 최대한 빨리 허물고 dp 문제를 연마하고 싶다!!

기다려라 dp...