[백준] 1431번 시리얼 번호 파이썬 정답 코드

https://www.acmicpc.net/problem/1431

1431번: 시리얼 번호

---

1. 접근 방식

• 가장 먼저 입력받은 시리얼 번호에 내장 함수 sort( )를 적용하여 3번째 조건으로 정렬하자.

3번째 조건이긴 하지만, 1, 2번 조건으로 비교할 수 없다면 알파벳 사전 순으로 정렬해야 한다. 문자열을 sort( )하면 ASCII 코드 값을 기준으로 오름차순 정렬된다. 그럼 일단 알파벳 순서대로도 정렬이 되는 것이므로, 먼저 sort( )를 적용한다.

 

• sorted( )의 key를 사용하여 1번과 2번 조건으로 정렬하자.

sorted( ) 메서드에 key를 사용하여 정렬에 대한 조건을 줄 수 있다. 여기선 lambda를 사용하여 조건을 제시해야겠다고 판단했다. 각 시리얼 번호에 대해 (1) 시리얼 번호의 길이와 (2) 시리얼 번호 내 숫자들의 합이라는 어떠한 반환된 값을 기준으로 정렬할 것이기 때문이다. 이를 위해선 아래와 같은 함수가 필요하다.

• 1번 조건: 시리얼 번호의 길이를 반환하는 내장 함수 len( )
• 2번 조건: 시리얼 번호 내 숫자들의 합을 반환하는 함수 (직접 구현)

 

 

2. 정답 코드

• sort( )의 key에 여러 조건을 사용하려면, 튜플로 그 순서를 표현하면 된다.

def getSum(x):
    result = 0
    for e in x:
        if e.isdigit():
            result += int(e)

    return result

def Sort(data):
    return sorted(data, key=lambda x: (len(x), getSum(x)))

# main
n = int(input())
serials = [input() for _ in range(n)]
serials.sort()

for s in Sort(serials):
    print(s)

 

 

3. 새로 알게 된 내용

• 정규식은 실행 시간이 오래 걸리므로, 되도록 다른 방법으로 똑같은 기능을 구현하자.

def Sort(data):
    import re
    return sorted(data, key=lambda x: (len(x), sum(list(map(int, list(re.sub('[^0-9]', '', x)))))))

처음에는 위 코드처럼 re 모듈을 사용하여 정규식으로 시리얼 번호 내 숫자의 합을 구했다. 시리얼 넘버 내에 0, 1, 2, ... 8, 9의 숫자가 아닌 다른 문자는 제거하고, 이들을 int형으로 변환한 후 sum( ) 메서드를 적용하는 것이다.

그러나 실행 시간이 120ms가 걸렸다. 따라서 정규식 대신 시리얼 넘버를 순회하면서 각 문자에 대해 isdigit( ) 메서드를 적용하는 방식으로 코드를 바꾸었더니, 44ms로 실행 시간이 단축되었다.