[백준] 10814 나이순 정렬 python 알고리즘

문제 10814. 나이순 정렬

1. 나의 코드와 발상 과정

# 정답 (4092ms)
n = int(input())
member_list = []
for i in range(n):
    member_list.append(list(input().split()))

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

for i in range(n):
    print(member_list[i][0], member_list[i][1])
    
# 런타임 에러(IndexError)
n = int(input())
member_list = {}
for i in range(n):
    age, name = list(map(str, input().split()))
    member_list[name] = int(age)

s1 = sorted(member_list.items(), key = lambda x: x[1])
print(s1)
for i in range(n):
    print(s1[i][1], s1[i][0])


# 시간 초과
n = int(input())
member_list = []

for i in range(n):
    age, name = list(map(str, input().split()))
    member_list.append([age, name])

for i in range(n):
    for j in range(n):
        if int(member_list[i][0]) < int(member_list[j][0]):
          member_list[i], member_list[j] = member_list[j], member_list[i]
    
for i in range(n):
    print(member_list[i][0], member_list[i][1])

맨 아래의 코드 블럭이 나의 대략적인 의도였다.

이차원 배열을 만들어서 이차원 배열 내에 있는 나이들을 비교하고, 2중 for문을 활용해서 member_list 내의 요소들을 비교하여 재정렬 한다. 그렇지만, n이 10만이기 때문에 시간적인 면에서 실패할 수 밖에 없었다.

 

그래서 두 번째 문단에 있는 #런타임 에러 코드에서 구현했듯 딕셔너리를 활용해 보기로 했다.

vaule를 기준으로 정렬할 수 있기 때문에, key를 name으로, value를 age로 해서 배열 정리를 했지만, IndexError가 일어나 실패했다.

 

마지막으로 정렬 시간을 줄여보고자, 시간복잡도가 NlogN인 sort()를 써보았다.

람다함수를 활용해 오름차순 정렬을 시도하니 정답이 되었다.

 

딕셔너리를 활용한 것이 왜 틀렸는지에 대해 의문이었는데, 여러 가지로 알아보니, '동명이인'의 케이스에서 틀릴 수 밖에 없다는 사실을 알 수 있었다.

딕셔너리는 key가 하나밖에 존재할 수 없다. 중복된 key값을 가진 새로운 value가 들어가면 기존의 key:value 쌍에는 새로운 value값이 투입되어 교체되는 구조이기 때문에, 같은 key값을 가진 여러 가지의 value가 사용될 수 없다. 특성 자체를 잘못 활용하였고, IndexError의 이유는 하단의 반복 출력문에서 일어나는데, s1 자체가 동명이인이 생겨버리면 원래 있는 n값 보다 리스트의 길이가 줄어들어 버리게 된다. 그렇기에 IndexError가 일어나는 것이다.

 

 

2. 아쉬운 점

더 빠르게 처리할 수 있는 코드에 대해 생각해볼 필요가 있다.