Python의 sort는 stable sort임을 이용하여 다음과 같이 두 번에 나누어서 정렬하면 됩니다.
[['a', 'b'], ['a', 'a'], ['b', 'b'], ['b', 'a']]
이 방법은 단일 문자인 경우에만 성립합니다.
파이썬 sort가 stable sort였군요! 이번에도 멋진 답변 감사드려요!!
사실 이 질문이 https://www.acmicpc.net/proble... 이 문제를 풀다가 나온거였는데,
s.sort(key=lambda x:x[1],reverse=True)
s.sort(key=lambda x:x[0])
위와 같이 코드를 짜면 테스트케이스처럼 올바르게 정렬이 되지만
s.sort(key=lambda x:x[0])
s.sort(key=lambda x:x[1],reverse=True)
이렇게 순서를 바꾸면 테스트케이스랑은 다르게 정렬이 되더라구요..
stable sort라도 정렬 순서를 다르게 하는 것이 결과에 영향을 미치나요? 이 부분이 이해가 잘 되지 않습니다..
해당 문제를 기준으로 말씀드리면, "멘토를 기준으로 사전 순으로 정렬하되, 멘토가 같은 순서쌍들에 대해선 멘티의 사전 역순으로 정렬"해야 하기 때문에 그렇습니다.
멘토와 멘티가 단어가 너무 비슷해 헷갈리니, 이후로는 첫 번째 열과 두 번째 열로 서술하겠습니다.
올바른 방법을 먼저 살펴봅시다.
먼저 두 번째 열의 사전 역순으로 정렬을 하게 됩니다.
이 이후 첫 번째 열의 사전 순으로 정렬을 하면, 문제의 조건을 모두 만족하게 됩니다. 그 이유는,
1) 마지막 정렬이 첫 번째 열을 기준으로 사전 순으로 정렬한 것이니, 첫 번째 조건은 당연히 만족되었습니다.
2) 첫 번째 열이 같은 경우는 두 번째 열의 사전 역순으로 정렬이 되어 있습니다. 왜냐하면, 처음으로 한 정렬에서 이 순서를 만들어주었고, stable sort의 특성 때문에 마지막 정렬이 이 순서를 그대로 유지해주기 때문입니다.
그런데 이 정렬을 순서를 바꾸어 하면 어떻게 될까요?
먼저 첫 번째 열을 기준으로 사전 순으로 정렬합니다.
그 다음, 두 번째 열을 기준으로 사전 역순으로 정렬하면, 첫 번째 열을 기준으로 사전 순으로 정렬한 것이 다 깨지게 됩니다.
stable sort는 정렬 기준에서 두 원소가 동일한 경우에만 기존 순서를 유지해주지, 동일하지 않은 경우는 당연히 정렬 기준에 따라 순서를 바꾸기 때문입니다.
다음 반례를 생각하시면 쉬울 겁니다.
댓글을 작성하려면 로그인해야 합니다.
phc328 3년 전
s=[['a','b'],['c','d']]와 같이 문자열만 들어있는 2중 리스트를 정렬하려고 합니다.
s[i][0] 성분을 기준으로 오름차순, s[i][1] 성분을 기준으로 내림차순으로 정렬을 하고 싶어서 아래와 같이 코드를 짰습니다.
s=sorted(s,key=lambda x:(x[0],-x[1]))
그런데 코드를 실행하니 bad operand 에러가 떴습니다. 검색해보니 문자열에서는 내림차순으로 정렬을 할 때 -x[1]과 같이 앞에 마이너스를 붙일 수 없는 것 같았습니다.
reverse=True를 이용하면 모든 조건들이 내림차순으로 바뀌어버리던데, 문자열의 오름차순과 내림차순이 섞여 있는 경우에는 람다함수에 조건을 어떻게 줘야 정렬이 제대로 될까요??