좋은 의미일수도 있고 아닐수도 있지만 며칠간 너무 스트레스 받았고 문제 볼때마다 머리털 빠질것만 같았던 문제를 이제서야 끝냈다. 내가 워낙 잘 안풀리는 문제 보면 집착이 심해서 그런지 다른 사람의 풀이를 보면서 도움을 받았음에도 나만의 코드로 작성하려고 너무 개고생을 하다보니 결국 이 문제에 집착을 오래했다.
개인적인 생각으로 정렬 (Sorting) 문제는 꽤 쉬운 편에 속한다고 생각한다. 그리고 이 문제는 흔히 말하는 "빡" 구현을 요구하는 문제이다. 정답 비율만 봐도 24프로고 골드2 수준에 백준 문제면은 대략 리트코드 하드~ 프로그래머스 레벨3 정도 되는 문제같다. 이상하게 내가 풀었을때 너무 안풀려서 화가 났었는데 백준 특성상 어떤 테스트 케이스가 틀렸는지 보여주지도 않고 그냥 정 없게 틀렸다고만 나와서 너무 서운했는데 이제야 좀 어떻게 푸는지 느꼈다.
먼저 문제에 대한 설명으로는, N만큼의 단어가 나오는데 이것을 "natural sort" 하는게 목적이다. 정렬을 구현하는 방법이 좀 색다로운데
- 숫자열은 알파벳보다 앞에 와야한다
- 알파벳 끼리는 AaBbCc..Zz 의 순서를 따라야한다
- 문자열을 비교하는 숫자가 있을경우 가장 큰 단위로 묶어야한다 a12b345 = "a", "12", b, "345"
- 숫자열끼리는 십진법으로 더 작은게 앞에 와야한다
- 같은 값을 가진 숫자열끼리는 앞에 붙는 0의 개수가 적은것이 앞에온다 -> 0000012 와 12 를 비교할경우 12가 앞에 와야한다.
테스트 케이스만 보고 실수할수있는 점은 숫자로 이루어진 문자열을 int 나 long long 계열로 바꿀려는 시도를 할때다. 이미 숫자는 2^63을 초과해서 프로그래밍 언어에서 주는 가장 큰 변환값을 해도 초과한다.
그리고 이 문제를 풀기 위해 가장 중요한 점은 내부적으로 쓰는 sorting 라이브러리의 이해도 였던거같다.
나같은 경우 가장 먼저 접근해야 하는 부분은 문자열을 문자와 숫자로 나누는 단계였다.
가장 먼저 예시로 주는 문자열을 담은 다음에 HashTable 을 이용해서 문자와 숫자를 깔끔하게 나누어주었다.
그 후에는 이 문자열들을 읽으면서 각각 문자열에 저장된 벡터를 이용해서 문제를 풀어야했는데 이 부분이 정말 어질어질 했다.
lambda 를 이용해서 sorting 방법을 선택했고 주석에 적혀있는것처럼 정렬을 해줬다. 그리고 이 단계에서도 내가 sorting 의 이해도가 낮다면 전혀 다른 방향으로 정렬이 되었을거다. 항상 정렬을 할때는 true/false 값을 생각하면서 정렬을 해줘야한다.
제일 쉬운 케이스였던 "둘 다 문자인 경우" 와 "하나만 문자고 하나는 숫자인 경우" 를 정렬해주었다. 그리고 둘 다 문자고 비교해주는 과정에서 난 생각못했는데 서로 "같은 값" 으로 변환시켜주고 비교하는게 맞았다. 이 예시에서는 toupper() 함수를 이용해서 대문자로 만든 후에 비교해주었다.
가장 어려웠던 부분이 아닐까 싶은데, 둘 다 숫자 일 경우 비교를 조심스럽게 해줘야하는데 나는 0의 숫자를 계속 카운트 해주었고 둘이 같은 숫자일 경우, 0의 숫자만큼 정렬해주었다. 그 외에 상황에서는 숫자가 더 작은 경우/ 큰 경우 비교를 해줘야했는데 문자열의 길이로 비교하며 숫자의 크기를 직접 int 계열로 변환하는 대신에 사용해주었다.
이 과정을 거치면은 정렬이 된것을 확인할수있다.
여러모로 어지러웠고, 내가 얼마나 sorting 알고리즘을 우습게 봤는지 알게되었다.
sorting 을 하는 과정에서 return true / return false 하는 과정이 좀 뭐지 하고 헷갈렸는데 stl sorting 은 조건이 true 만되면은 그 조건대로 움직이는것이다. 그리고 length() 가 다를때 길이가 작은게 먼저 나오게 boolean 세팅만 해주면 더 깔끔한 코드가 나오는것을 확인 할 수 있다.
배운점:
1. C++ sorting 알고리즘 작동 원리 알기
2. 문자열 비교 방법
