[algorithm] 백준 10814 - 나이순 정렬

[algorithm] 백준 10814 - 나이순 정렬

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 10814번 문제 - 나이순 정렬 의 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다 함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 10814

 

백준 10814번 나이순 정렬 문제 보러가기

 

반응형

 

문제 해석

 

문제에서 원하는 정렬은 나이순이긴 하지만 같은 나이일 경우에는 먼저 입력된 요소를 우선적으로 하는 정렬을 

원합니다. 이렇게 순서를 신경 써주는 정렬을 안정 정렬 (stable sort)이라고 합니다.

대표적인 안정 정렬으로는 삽입 정렬, 버블 정렬, 병합 정렬이 있습니다.

정렬의 기준값이 같을 경우에 먼저 입력된 순서를 어떻게 유지해 줄지 생각해 보면서 문제를 풀어봅시다.

힌트 : 나이 별로 따로 생각해 보는 것도 하나의 방법입니다.

 

풀이 1 - 생각나는 대로 작성해 본 코드

 

# 10814 나이순 정렬

n = int(input())
user = []
for _ in range(201): # 나이의 최대값이 200 이므로
    user.append([])

for _ in range(n):
    i, name = input().split()
    user[int(i)].append(name)

for i in range(len(user)):
    if len(user[i]) != 0:
        for j in user[i]:
            print(i, j)

 

풀이 2 - lambda로 함수를 만들어 key의 기준으로 사용

 

# 10814 나이순 정렬

n = int(input())

user = []

for _ in range(n):
    age, name = input().split()
    user.append([int(age), name])    

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

for i in user:
    print(*i)

 

풀이 3 - 리스트를 만들 때 comprehension 방식을 사용하고 lambda로 함수를 만들어 key의 기준으로 사용

 

# 10814 나이순 정렬

n = int(input())

user = [list(input().split()) for _ in range(n)]

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

for i in user:
    print(*i)

 

풀이 해석 및 팁

 

3개의 풀이 중 1번 풀이가 메로리를 가장 적게 쓰지만 시간은 많이 소요가 됩니다.

그리고 풀이 2번과 3번은 시간은 줄어들지만 메모리를 많이 사용하게 됩니다.

그때그때 상황에 맞는 풀이 방법을 찾아서 적용하면 좋을 것 같습니다.

[algorithm] 백준 1181 - 단어 정렬

위 문제에서 리스트 매서드 sort의 옵션인 key를 사용하는 방식이 한 번 나왔는데 오늘은 더욱 고급스러운

방식으로 사용했습니다. lambda를 사용해 함수를 만들고 이를 key로 사용하는 방식입니다.

리스트를 만들 때 comprehension 방식에 익숙해지신다면 풀이 3번과 같이 작성할 수도 있습니다.

풀이 1과 풀이 3을 비교해 보면 코드의 길이가 확연하게 차이 나는 것을 볼 수 있습니다.

간단하게 작성할 수 있는 것은 최대한 간결하고 깔끔하게 작성해서 남이 보았을 때도 이해하기 쉽도록

코드를 작성해 보는 습관을 길러봅시다.

---

여기까지 백준 10814번 나이순 정렬 문제 풀이였습니다.

 

이번 문제의 정답률은 43% 정도입니다.

 

나이를 기준으로 정렬이 필요한데 중복의 경우 먼저 입력된 순서를 유지해줘야 하는 조건이 있어서

 

50% 밑의 정답률을 보이는 것 같습니다.

 

정렬과 관련된 문제라고 꼭 정해진 정렬방식을 사용해 문제를 풀어야 하는 것은 아닙니다.

 

생각을 전환시켜서 풀이법을 찾아내는 것 또한 문제 해결 능력이므로 다각도로 문제를 바라보는

 

능력치를 길러봅시다.

 

감사합니다.