[이코테] 문자열 재정렬

이것이 코딩 테스트다 Ch12 Q 08

12-8 문자열 재정렬

문제 설명

알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어집니다.
이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다.
예를 들어 K1KA5CB7이라는 값이 들어오면 ABCKK13을 출력합니다.

Input

S -> str

Output

문자열 - 알파벳은 오름차순, 숫자는 더한 값을 이어서 출력

Limit

1 <= S <= 10,000
time : 1 second
memory : 128 MB

구현 코드

문제를 푼 방식

문제 자체는 굉장히 쉬운 문제였으나, 효율적으로 풀기 위해서는 생각이 필요한 문제였다.

문자열 재정렬은 한 글자가 들어오면
1. 문자인지 숫자인지 확인한다.
2. 숫자이면 sum 변수로 더해준다.
3. 문자이면 정렬한다.
4. 반환 문자열을 만들어준다. 정렬된 순대로 문자열로 연결해주고, sum 변수도 문자열로 뒤에 붙여준다.
이 과정을 input 문자열에 한 글자씩 반복해준다.

난 이 과정에서 3번 문자이면 정렬한다를 조금 더 효율적으로 생각해보았다.
새로 들어온 문자를 정렬하기 위해서는, 들어온 값을 문자열 리스트에 넣을 자리를 search하고 그 위치에 insert 하는 두 가지 과정이 필요하다.
처음 구현시에는 selection sort의 순차 탐색 방법으로 $O(N)$의 시간 복잡도로 search하였다.
다시 구현할 때는 binary sort의 binary search를 이용하여 $O(logN)$의 시간 복잡도로 구현하였다.

Analysis

시간복잡도 : $O(N^2)$
공간복잡도 : $O(N)$

from bisect import insort


def solve(S):
    result = []
    sum_num = 0
    for s in S:
        # 숫자이면 합계에 더해준다.
        if s.isdigit():
            sum_num += int(s)
        # 문자이면 오름차순 list인 result에 맞는 문자순대로 insert해준다.
        else:
            insort(result, s)
    return "".join(result) + str(sum_num)

테스트 코드

class testSolve(unittest.TestCase):
    def testcase1(self):
        self.assertEqual(solve("K1KA5CB7"), "ABCKK13")

    def testcase2(self):
        self.assertEqual(solve("AJKDLSI412K4JSJ9D"), "ADDIJJJKKLSS20")


unittest.main()