string padding 처리는 많이 들어보셨을 겁니다. 예를 들어 제가 낸 문제 중에 수인 분당선 문제도 답이 9:0:0인 경우에 09:00:00으로 출력하라고 했었습니다. 앞에 0을 padding을 해서 2자리로 맞추도록 한 것입니다. 그리고 오늘 새로 추가된 이 문제 역시 padding이 들어가 있습니다. 이 두 문제의 공통점은 left padding이였다는 점입니다.
제가 개최한 2회 코테의 1번 문제 또한, string을 long long으로 떨궈내면 여유롭게 해결을 하실 수 있는데요.
문자열을 long long으로 압축하는 방식을 2번 문제의 제 솔루션과 동일하게 하면 당연하게도 틀렸습니다를 보게 됩니다. 왜일까요? 해당 솔루션에 있는 압축 방식을 잘 읽어보면 문자열의 길이가 커질수록 숫자가 커지기 때문입니다. 그러면, 아래와 같은 경우에, 비교를 잘못 할 수가 있습니다.
위의 경우에는 37^4 + 37^3 + 37^2 + 37^1 + 1이 나옵니다. 그런데 밑의 경우에는 2가 나옵니다. 당연하게도, 37^4가 2보다는 큽니다. 그래서 실제로 "aaaaa"가 "b"보다 앞서야 한다는 결과가 나와야 함에도 불구하고, 뒤에 있다는 잘못된 판단을 해 버리게 됩니다. 그런데, 2번에서는 맞았단 말이죠.
이는, 2번 문제에서는 단지, 해당 문자열이 long long 하나로 1:1 대응이 되기만 하면 되었기 때문입니다. equal 연산은 그렇게 되면 됩니다. 그런데 1번은 정렬이 들어갔고, name과 확장자를 compare 해야 하니, 상대적인 비교도 같이 들어가야 합니다.
따라서, 나머지 부분을 NULL로 padding 처리를 해야 합니다. 이 NULL 문자는 0번으로 처리하고, 아스키 순서대로 따지면 0부터 9가 제일 앞서고, 그 다음에 알파벳 소문자일 것이니, 각각 1, ... , 36까지로 할당해 주면 됩니다. 확장자의 길이와 파일 이름의 길이가 최대 10자라고 했습니다. 그러면 10개짜리를 할당해 놓으면 됩니다.
예제의 maltise는 어떻게 압축시키면 될까요?
이렇게 압축시켜 버리면 됩니다. maltise가 7자이고, 나머지 3자는 NULL로 패딩시켜버리면 됩니다.
다음 yolo는 뒤에 6자를 NULL로 패딩시키면 됩니다. 그러면, yolo가 실제로는 더 짧지만, 사전순으로 길어서 압축한 값이 더 크게 됩니다. 뒤에 NULL 패딩을 붙여서 자릿수를 같게 만든다면 그렇게 만들어버릴 수 있습니다. 반면에, 어제 나온 빌런 호석 문제는
이런 형태였습니다. 이런 거는 그냥 4자리만큼 0으로 채운 다음에, 3번째 자리에 4, 4번째 자리에 3을 채우면 됩니다. padding 처리하는 것은 문자열 처리할 때 흔히 보이는 패턴이니 알아두시면 좋습니다.
padding에 대해서 언급했으니, 사전순 비교를 위해서 문자열을 long long으로 압축하는 일만 남았네요.
파일에 대한 메타 정보를 담습니다. nn과 ee와 flag가 있는데요. nn은 파일 이름을 long long으로, ee는 확장자를 long long으로 압축한 것입니다. ve는 확장자가 압축된 것을 저장합니다.
다음에, init에서 'a'부터 'z'까지는 어떤 수로 대응시킬 건지, 그리고 '0'부터 '9'까지는 어떤 수로 대응할 것인지를 채웁니다. 다음에, 26번째 줄의 for loop는 자릿수가 0이라면 어떤 character 값으로 대응되는지를 나타냅니다. 이 c는 역변환을 위한 것임을 알 수 있어요.
이것은 string을 long long으로 변환하기 위한 코드입니다. 64진법임을 한눈에 알 수 있는데요. 이는 나머지 연산과 나누기 연산의 효율성을 위해서입니다. 비트 연산으로 효율을 올릴 수 있기 때문입니다. 여기서 f는 캐릭터 하나가 어떤 수로 대응되는지 저장하는 배열임을 간파할 수 있습니다.
다음에, conv는 long long으로 압축된 수를 다시 string으로 변환하는 것입니다. padding으로 인해서 10자보다 작은 string의 경우도 10자가 되었습니다. 따라서, string으로 바꿀 때, 9번 위치부터 0번 위치까지 역순으로 돌게 됩니다.
그러면, 비교 함수는 매우 간결해 집니다. 문자열 둘을 string compare 하는 게 아니라 long long 2개를 compare 하기 때문에 상당히 빠르게 동작합니다. 최악의 경우에 21번 단위 연산이 돌아가는 거랑 3번 돌아가는 거랑 극단적으로 차이나게 됩니다. 키 2개를 비교하는 함수를 호출할 때 마다 문자열 비교하는 것 만큼의 오버헤드가 빠지게 됩니다.
제가 설명한 부분을 모두 반영한 코드는 여기에 있습니다.
'구현' 카테고리의 다른 글
라운드 로빈 스케줄링 알고리즘을 구현해 봅시다. (2) | 2021.08.04 |
---|---|
가희가 개최한 코딩 테스트에 나온 상대속도에 대한 이야기 (0) | 2021.07.29 |
우선순위 스케줄링 aging 처리를 구현해 봅시다. (0) | 2021.06.28 |
백트래킹과 가지치기에 대해서 예제 문제를 통해 알아봅시다. (0) | 2021.06.17 |
파이썬 2차원 배열 회전을 1줄에 구현해 봅시다. (4) | 2021.06.12 |
최근댓글