[코딩테스트] 문자열 내 마음대로

문제 설명

문자열 목록과 정수 n이 주어지면 각 문자열의 n번째 색인 문자를 기준으로 오름차순으로 정렬하려고 합니다. 예를 들어 문자열이 (“sun”, “bed”, “car”)이고 n이 1인 경우 문자열은 각 단어의 인덱스 1에서 문자 “u”, “e”, “a”로 정렬됩니다.

제한

• 문자열은 길이가 1보다 크거나 같고 50보다 작거나 같은 배열입니다.
• 문자열의 요소는 소문자입니다.
• 문자열의 요소는 길이가 1보다 크거나 같고 100보다 작거나 같은 문자열입니다.
• 문자열의 모든 요소 길이가 n보다 큽니다.
• 인덱스 1에 동일한 문자를 가진 문자열이 여러 개 있는 경우 사전순으로 앞에 오는 문자열이 먼저 옵니다.

I/O 예시

입출력 예제 1

Sun, Bed 및 Auto의 첫 번째 인덱스 값은 각각 u, e 및 a입니다. (“Car”, “Bed”, “Sun”) 기준으로 문자열을 정렬합니다.

입출력 예제 2

“abce”, “abcd” 및 “cdx”의 두 번째 인덱스 값은 “c”, “c” 및 “x”입니다. 따라서 정렬 후 “cdx”가 끝에 있습니다. “abce” 및 “abcd”가 알파벳순으로 정렬된 경우 “abcd”가 우선하므로 대답은 (“abcd”, “abce”, “cdx”)입니다.

복잡한 정렬

Python의 Timsort 알고리즘은 안정적인 정렬입니다. 따라서 공식 Python 설명서에 설명된 대로 복잡한 정렬을 수행할 수 있지만 정렬 순서가 중요합니다. 예를 들어 나이순으로 정렬하고 나이가 같으면 이름순으로 정렬하면 정렬 순서가 반대로 됩니다. 즉, 이름순으로 정렬한 후 나이순으로 정렬해야 합니다.

따라서 위의 문제를 해결하려면 먼저 알파벳순으로 정렬하십시오. n첫 글자를 기준으로 정렬합니다.

def solution(strings, n):
    res = sorted(strings) #사전식 정렬 후 n번째 글자로 다시 정렬
    return sorted(res, key = lambda string: string(n))

if __name__ == "__main__":
    sample1 = (("sun", "bed", "car"), 1)
    sample2 = (("abce", "abcd", "cdx"), 2)
    for strings, n in (sample1, sample2):
        print(solution(strings, n))

실행 결과

('car', 'bed', 'sun')
('abcd', 'abce', 'cdx')

한 번 더 분류 안정성 및 복잡한 분류 문서를 보고 공부해 봅시다.

람다 함수

위의 함수에서 정렬할 때 정렬할 키에 람다 함수를 사용했습니다. 람다 식이라고도 하는 람다 함수는 이름이 없는 익명 함수입니다.

일반함수와 람다함수를 비교하면 다음과 같다.

def 함수 이름(매개변수):
    ...
    return 결과값

lambda 매개변수: 결과값

그러므로 sorted(res, key = lambda string: string(n)) 람다 함수에서 매개변수 string~에서 n첫 번째 인덱스의 값을 반환합니다. 여기 string들어가는 논거 res의 요소이다

추가 정보 람다 식으로 함수 만들기보자

정렬 알고리즘

저는 파이썬만 알고 있고, 파이썬의 정렬 알고리즘이 그 문제에 적합하기 때문에 별 어려움 없이 풀었습니다. 이것은 다른 프로그래밍 언어가 어떤 정렬 알고리즘을 사용하느냐에 따라 어려운 문제가 될 수 있습니다.

정렬 안정성은 정렬되는 항목의 키 값이 동일한 경우 정렬 전 순서(또는 입력 순서)로 정렬하는 것을 말합니다.

안정적인 정렬 알고리즘

• 버블 정렬
• 삽입으로 정렬
• 병합, 정렬
• Tim Sort → Python의 정렬 알고리즘

불안정한 정렬 알고리즘

• 정렬 선택
• 빠른 다양성
• 힙 정렬

프로그래머의 원본 텍스트로 이동