이취코테(구현 기초) - 문자열 재정렬 문제

문제.

알파벳 대문자와 숫자(0~9)로만 이루어진 문자열 s가 입력으로 주어진다.

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

조건 : 1<= s의 길이 <=10000, 시간제한 1초

 

예시 입력)

AJKDLSI412KJ4JSJ9D

 

예시 출력)

ADDIJJJJKKLSS20

 

- 나의 풀이

s = list(input())
s.sort() # 숫자 -> 영어(대->소) 순으로 정렬
n_list = list(map(str, [i for i in range(10)])) # 0~9 숫자를 str로 저장
result = ""
for i in range(len(s)) :
  if s[i] not in n_list : # s[i]가 알파벳이면 슬라이싱하고 break
    num = s[:i]
    string = s[i:]
    break

num = list(map(int, num))
result = ''.join(string) + str(sum(num))
print(result)

 

10000개의 데이터에 대해 시간제한 1초 -> 대략 O(N^2) 이하의 알고리즘 선택해야함

조건문에서 탐색한 총 횟수 = (s에 있는 숫자의 개수+1) x 10, 슬라이싱 총 횟수 = 2  이므로

시간복잡도는 worst-case에도 O(n)을 보장한다.

 

 

주의 : 리스트 s는 숫자와 문자가 함께 str 자료형으로 존재하므로 모든 원소를 동시에 형 변환 할 수 없다.

-> 문자와 숫자를 나누어 슬라이싱 한 배열로 각각 나누어야 map()으로 모든 원소 형 변환 가능

 

 

팁 :

숫자와 알파벳이 복합적으로 존재하는 리스트에 sort()를 적용하면

숫자 -> 영어(대문자 -> 소문자) 순으로 정렬한다. 

 

리스트를 문자열로 만드려면 아래와 같이 직접 구현해도 되지만 join()함수를 사용하면 손쉽게 만들 수 있다.

for j in range(len(string)) :
  result += string[j]