[ 이것이 코딩테스트다 ] 문자열 재정렬 - 구현 (시뮬레이션)

[  이것이 취업을 위한 코딩테스트다 with 파이썬  ] 문자열 재정렬 _ Python 파이썬

 

" 문제 "

 

알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어집니다.

이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다.

예를 들어 K1KA5CB7 이라는 값이 들어오면 ABCKK13을 출력합니다.

 

<입력 조건>

 

첫째 줄에 하나의 문자열 S가 주어집니다. ( 1 <= S의 길이 <= 10,000 )

 

 

<출력 조건>

 

첫째 줄에 문제가 요구하는 정답을 출력합니다.

 

입력 예시	출력 예시
K1KA5CB7	ABCKK13

---

" 아이디어 "

문자열 정렬을 하면 쉽게 풀리는 문제이다.

정렬은 여러가지 방식이 있지만, 

입력은 알파벳 대문자와 한자리 숫자들로만 이루어진다.

즉, 입력받는 문자의 종류가 한정되어 있다는 특징이 있어서

카운팅정렬을 활용해보았다.

 

카운팅정렬은 각 문자당 등장하는 횟수를 세어서 정렬을 하는 방식이다.

예를들어 대문자만 입력이 들어오는 경우에는

맨 처음 알파벳 대문자 수만큼 배열을 만든다.

배열의 인덱스 0 부터 차례로 A~Z 가 들어온 횟수를 카운팅한다.

alphabet = [0] * 26

DDAACCCDE 가 입력으로 들어오면

alphabet = [2, 0, 3, 3, 1 ...]

이렇게 카운팅된다.

또다른 배열에 이 알파벳이 들어온 만큼 순서대로 넣으면 된다.

AA (B건너뜀) CCC DDD E 이렇게 정렬이 된다.

 

카운팅 정렬은

입력받는 문자의 종류가 많으면, 메모리를 많이 잡아먹지만

문자의 종류가 한정되어있어 메모리 걱정이 없다면 시간복잡도가 적다.

따라서 이번 문제에서는 카운팅 정렬방식을 차용하였다.

따로 정렬 후 배열에 넣지는 않고 문자의 갯수만큼 바로 출력하는 방식으로 풀이하였다.

숫자의 경우 카운팅하는 for문에서 바로바로 sum 에 누적해주었다.

 

---

" 코드 "

 

s = input()
 
alpha = [0]*26
sum = 0
 
for a in s:
    if a >= 'A' and a <= 'Z':
        alpha[ord(a)-65] += 1
    if a >= '0' and a <= '9':
        sum += int(a)
 
for i in range(26):
    for j in range(alpha[i]):
        print(chr(i+65), end='')
print(sum)

 

---

" 참고자료 "

 

▼ 파이썬 아스키코드와 문자간 변환 / 아스키코드 표

파이썬(python) 아스키를 문자로 변환 / 문자를 아스키로 변환 / 아스키 코드 표