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를 이용하면 모든 조건들이 내림차순으로 바뀌어버리던데, 문자열의 오름차순과 내림차순이 섞여 있는 경우에는 람다함수에 조건을 어떻게 줘야 정렬이 제대로 될까요??

lcr7324   3년 전

Python의 sort는 stable sort임을 이용하여 다음과 같이 두 번에 나누어서 정렬하면 됩니다.

antoliny0919   3년 전

[['a', 'b'], ['a', 'a'], ['b', 'b'], ['b', 'a']]

lcr7324   3년 전

@antoliny0919

이 방법은 단일 문자인 경우에만 성립합니다.

phc328   3년 전

@lcr7324

파이썬 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라도 정렬 순서를 다르게 하는 것이 결과에 영향을 미치나요? 이 부분이 이해가 잘 되지 않습니다..

lcr7324   3년 전

해당 문제를 기준으로 말씀드리면, "멘토를 기준으로 사전 순으로 정렬하되, 멘토가 같은 순서쌍들에 대해선 멘티의 사전 역순으로 정렬"해야 하기 때문에 그렇습니다.

멘토와 멘티가 단어가 너무 비슷해 헷갈리니, 이후로는 첫 번째 열과 두 번째 열로 서술하겠습니다.

올바른 방법을 먼저 살펴봅시다.

먼저 두 번째 열의 사전 역순으로 정렬을 하게 됩니다.

이 이후 첫 번째 열의 사전 순으로 정렬을 하면, 문제의 조건을 모두 만족하게 됩니다. 그 이유는,

1) 마지막 정렬이 첫 번째 열을 기준으로 사전 순으로 정렬한 것이니, 첫 번째 조건은 당연히 만족되었습니다.

2) 첫 번째 열이 같은 경우는 두 번째 열의 사전 역순으로 정렬이 되어 있습니다. 왜냐하면, 처음으로 한 정렬에서 이 순서를 만들어주었고, stable sort의 특성 때문에 마지막 정렬이 이 순서를 그대로 유지해주기 때문입니다.

그런데 이 정렬을 순서를 바꾸어 하면 어떻게 될까요?

먼저 첫 번째 열을 기준으로 사전 순으로 정렬합니다.

그 다음, 두 번째 열을 기준으로 사전 역순으로 정렬하면, 첫 번째 열을 기준으로 사전 순으로 정렬한 것이 다 깨지게 됩니다.

stable sort는 정렬 기준에서 두 원소가 동일한 경우에만 기존 순서를 유지해주지, 동일하지 않은 경우는 당연히 정렬 기준에 따라 순서를 바꾸기 때문입니다.

다음 반례를 생각하시면 쉬울 겁니다.

phc328   3년 전

계속 보다 보니 이해가 되는 느낌입니다.

답장이 좀 늦어졌지만 답변을 너무 잘 해주셔서 감사드려요!

댓글을 작성하려면 로그인해야 합니다.