백준 10814번 풀이

문제

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

10814번: 나이순 정렬

회원 정보를 나이순으로 정렬하되, 이름 순서는 바뀌지 않도록 하시오.

Reference

https://velog.io/@good159897/%EC%95%88%EC%A0%95-%EC%A0%95%EB%A0%AC-VS-%EB%B6%88%EC%95%88%EC%A0%95-%EC%A0%95%EB%A0%AC-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B8%ED%84%B0%EB%B7%B0

안정 정렬 VS 불안정 정렬 - [파이썬 알고리즘 인터뷰]

https://blog.naver.com/raylee00/222070980588

안정 정렬과 불안정 정렬(Stable sort, Unstable sort)

https://velog.io/@mquat/python-%EA%B8%B0%EC%B4%88-%EB%B0%B1%EC%A4%80-10814%EC%95%88%EC%A0%95%EC%A0%95%EB%A0%AC%EA%B3%BC-%EB%B6%88%EC%95%88%EC%A0%95%EC%A0%95%EB%A0%AC

[python 기초] 백준: 10814번 / 안정정렬과 불안정정렬

 

풀이

안정 정렬?? 뭔 생전 듣도보도 못 한 정렬이죠? 제가 모르는 알고리즘이 더 있는건가요? 아 그건 아니다. 일단 이거는 배열이 하나일 때를 예시로 들면 애매하니까 두 개의 요소를 갖는 어레이(...)를 예로 들어보자. 예를 들어서 트럼프 카드의 문양과 숫자를 값으로 갖는 배열을 입력했을 때

 

[[스페이드, 2],[하트, 5],[스페이드, 7],[다이아, 5]]

 

이런 배열이 있다 치자. 그리고 카드 숫자를 기준으로 정렬할 때 안정 정렬은

 

[[스페이드,2],[하트,5],[다이아,5],[스페이드,7]]

 

이런 식으로 숫자가 같은 카드의 문양 순서가 변하지 않지만 불안정 정렬의 경우 숫자가 같은 5의 문양 순서가 다이아-하트로 바뀔 수도 있다.

 

import sys

N = int(sys.stdin.readline())
user_list = []

for i in range(N):
    age, name = sys.stdin.readline().split()
    user = (int(age), name)
    user_list.append(user)

배열에 담는 건 맞는데, 나이와 이름을 튜플에 담을거다. 딕셔너리는 키값이 같으면 밸류가 달라도 먼저 들어온 값을 버리기때문에 안된다. 리스트랑 세트는... 안되나? 아무튼...

 

user_list.sort(key=lambda x:x[0])

그 다음은 익명함수 김람다씨 불러야지 뭐. .sort가 안정 정렬을 하기 때문에 이렇게만 하면 된다. 근데 뽑을 때 문제가 하나 있는데... 앞의 문제처럼 for문 줘도 된다. 줘도 되는데 print(i) 하면 튜플이 고대로 나와버린다. 그러면 어떻게 된다? 네 틀립니다.

 

for i in user_list:
    print(i[0],i[1])

그래서 튜플 인덱싱을 해야 한다.

 

import sys

N = int(sys.stdin.readline())
user_list = []

for i in range(N):
    age, name = sys.stdin.readline().split()
    user = (int(age), name)
    user_list.append(user)

user_list.sort(key=lambda x:x[0])

for i in user_list:
    print(i[0],i[1])

그래서 이게 전체 코드다.