[프로그래머스]문자열 내 마음대로 정렬하기

[56] 문자열 내 마음대로 정렬하기

책 구매하기

문제 정보

• 분류: 정렬
• 정답률: 69%
• 권장 시간 복잡도: O(N log N)
• 핵심 키워드: 정렬, 보조 키, 문자 인덱스, 사전순
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12915

문제를 읽을 때 체크할 포인트

문자열 전체를 정렬하는 게 아니라 n번째 글자를 1차 기준으로, 문자열 자체를 2차 기준으로 정렬하는 문제다. 정렬 키만 정확히 잡으면 짧다.

정렬 문제는 손이 바빠지기 전에 비교 기준부터 정리하는 게 먼저다. 어떤 값을 기준으로 한 번만 정렬하면 그다음 오히려 짧아지는 경우가 많다.

풀이 흐름

1. 각 문자열의 n번째 글자를 꺼낸다.
2. 정렬 키를 (문자열[n], 문자열)로 잡는다.
3. 정렬 결과를 반환한다.

구현할 때 놓치기 쉬운 부분

n번째 문자를 먼저 비교하고, 같다면 문자열 전체를 다시 비교해야 한다. 정렬 기준을 하나로만 잡으면 동률 처리에서 어긋난다.

파이썬 정답 코드

def solution(strings, n):
  # 각 문자열의 n번째 글자를 꺼낸다.
  return sorted(strings, key=lambda s: (s[n], s))

시간 복잡도

N은 strings의 길이이다.

핵심 비용은 정렬이다. N개 데이터를 정렬하는 데 O(N log N)이 들고, 정렬 뒤에 붙는 한 번의 순회나 해시 조회는 선형이라 전체 차수를 바꾸지 않는다.

따라서 시간 복잡도는 O(N log N)이다.