[이취코] 알고리즘 유형별 기출문제: 구현 - 8. 문자열 재정렬 (Python)

8. 문자열 재정렬

• facebook 인터뷰 기출

문제

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

조건

• 입력: 첫째 줄에 하나의 문자열 S가 주어짐 (1≤S의 길이≤10,000)
• 출력: 첫째 줄에 문제에서 요구하는 정답을 출력함

예시

K1KA5CB7 → ABCKK13

AJKDLSI412K4JSJ9D → ADDIJJJKKLSS20

풀이

문자열 S를 순회하며 해당 문자가 알파벳 대문자면 문자열만 저장하는 변수에 더하고 숫자면 형변환 후 더하여 출력

sorted()의 시간 복잡도가 O(nlogn)이니까 최소 힙을 사용해서 풀고 싶었는데 ABKCC처럼 문자에 대한 정렬이 제대로 동작하지 않아서 기본적인 방법으로 풀었다. 파이썬 heapq 모듈로 문자열에 정렬하는 법은 따로 더 공부해봐야겠다.

 

시간 복잡도: O(nlogn)

공간 복잡도: O(n)

# 구현 - 2. 문자열 재정렬
import sys
input = sys.stdin.readline
S = input().rstrip()
alphabet = ''
num_sum = 0
for i in S:
    if '0' <= i <= '9':
        num_sum += int(i)
    else:
        alphabet += i
alphabet = sorted(alphabet)
print(''.join(list(alphabet)) + str(num_sum))

책에서는 문자열만 모아두는 변수를 리스트 자료형으로 관리하여 sort() 함수를 사용했고, 알파벳인지 숫자인지 구분하는 과정에서 isalpha() 함수를 사용했다.

문제에서 맨 뒤에는 모든 숫자를 더한 값을 이어 출력하라고 해서 맨 마지막에 +str(num_sum)으로 처리했는데, 교재에서는 합이 0이 아닌 경우에만 문자열로 변환해서 맨 뒤에 붙이도록 구현했다. 합이 0인 경우에 대한 처리는 문제 조건에 따라 달라질 것 같다.