[Python] 구현 및 시뮬레이션 알고리즘을 파헤쳐 보자! (문자열 재정렬)

문제

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

입력

K1KA5CB7

출력

ABCKK13

내가 제출한 풀이 - 정답

import sys
import re

# 숫자 제거한 오름차순 문자 리스트
s = sys.stdin.readline().strip()
word_list = sorted((re.sub("\d", "", s)))

# 문자 제거한 숫자
num = re.sub("[a-zA-Z]", "", s)
sum_res = 0

for n in num:
    sum_res += int(n)

print(f"{''.join(word_list)}{sum_res}")

정답

data = input()
result = []
value = 0

for x in data:
    if x.isalpha():
        result.append(x)
    else:
        value += int(x)

result.sort()

if value != 0:
    result.append(str(value))

print(''.join(result))

Tip

정규식

'''
	re.sub(정규식, 치환될 문자, 문자열) => 문자열 치환
    \d => 숫자만
    \w => 숫자, 소문자만
    \W => 숫자, 소문자, 대문자 영어만
    [a-zA-Z] => 소문자, 대문자 영어만
'''
word_list = re.sub("\d", "", s)
num = re.sub("[a-zA-Z]", "", s)

정규식은 re 라이브러리를 사용하여 문자를 치환할 수 있다. 정규식은 모든 문자열을 봐야하므로, 시간복잡도는 O(n)이다. 그래서 내가 쓴 코드는 모든 문자열을 2번 돌리고 숫자를 더하기 위해 for문을 한 번 더 돌려 총 3번을 돌리게 된다.

하지만, 리스트에 저장하여 출력하는 정답을 보면 반복문이 1번만 사용되기 때문에 지금 같은 예제는 2번 째 정답이 더 빠르고 좋다라고 할 수 있다.

 

isalpha(), isdigit(), isalnum()

해당 변수가 어떠한 유형인지 확인하는 함수이다.

메소드 이름	설명	반환값
x.isalpha()	x가 알파벳인지 확인	True OR False
x.isdigit()	x가 숫자인지 확인	True OR False
x.isalnum()	x가 알파벳 또는 숫자인지 확인	True OR False

   References

본 그리디 알고리즘 문제 예제 및 개념은 나동빈 (이코테 2021 강의 몰아보기)  2. 그리디 & 구현을 참고합니다.