파이썬 Python | 알고리즘 | 백준 나이순 정렬

⭕ 파이썬 Python | 알고리즘 | 백준 나이순 정렬

➡️ 문제링크

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

 

➡️ 문제 탐색하기

• 2차원 배열을 사용하여 0번째 인덱스에 나이(age)를, 1번째 인덱스에 이름(name)을 저장하고, 나이끼리 비교하면 될 것 같았다.
• 하지만, 분명 2차원 배열보다 더 좋은 방법이 있을 것 같다는 고민이 들었다. 찾지 못했다. ㅎㅎ 그렇지만 시간복잡도에 있어서 여유 있다고 생각된다.

 

➡️ 코드 설계하기

• 우선, 회원의 수를 정하기 위한 숫자를 input() 함수를 사용하여 입력받는다.
• 한 줄씩 나이와 이름을 입력받아 2차원 배열 [나이, 이름]에 저장하는 방식으로 설계했다.
• 나이순으로 정렬하는 방법을 고민했는데, sort 함수를 사용하면 어떨지 생각해 봤다. 람다를 이용해 나이를 기준으로 정렬하면 될 것 같았다. sort 함수의 시간 복잡도는 O(N log N)이므로, 100,000명의 회원이 있어도 문제없을 것(500,000 연산)이라 예상했다. LogN은 컴퓨터공학에서는 밑이 2이지만, 코딩테스트 문제 풀이 시 10으로 계산해도 무방하다. 이 문제에서 Log(100,000)은 약 5로 계산하면 되고, O(NlogN)은 5 * 100,000 = 500,000번의 연산으로 계산된다.

---

• 두 가지 조건을 모두 만족시키는 정렬이 필요하다. 나이가 증가하는 순, 나이가 같으면 먼저 가입한 순

 

➡️ 시도 회차 수정 사항 (Optional)

1회 차

• 시간 268ms
• lambda x: (x[0], x[1] … )에 들어가는 값들은 각각 정렬의 1순위 조건, 2순위 조건을 차례로 명시한다.
• 람다를 사용하지 않아도 key 인자를 정하지 않은 기본적인 sort 함수에서 튜플 순서대로 정렬된다는 사실을 알게 되었다.

# 회원의 수를 정하기 위한 숫자를 입력받습니다.
number = int(input())

# 2차원 배열을 생성합니다. 배열의 각 원소는 [나이, 이름] 형태입니다.
members = []

# 입력받은 수만큼 나이와 이름을 입력받아 배열에 추가합니다.
for i in range(number):
    age, name = input().split()
    age = int(age)
    members.append([age, name])

# 나이순으로 배열을 정렬합니다.
members.sort(key=lambda x: x[0])

# 정렬된 배열을 출력합니다.
for member in members:
    print(f"{member[0]} {member[1]}")

---

2회 차

• 틀렸다는 결과가 나왔다.
• 동일한 나이의 경우 입력된 순서대로가 아닌 알파벳순서로 정렬되는 문제를 발견했다. 일반적으로 정렬 함수에 아무런 조건을 지정하지 않고 다차원 배열을 정렬 할 경우 정렬 우선순위가 앞의 열부터 생긴다. 람다를 사용하는 방법이 최선인 것 같다.

# 회원의 수를 정하기 위한 숫자를 입력받습니다.
number = int(input())

# 2차원 배열을 생성합니다. 배열의 각 원소는 [나이, 이름] 형태입니다.
members = []

# 입력받은 수만큼 나이와 이름을 입력받아 배열에 추가합니다.
for i in range(number):
    age, name = input().split()
    age = int(age)
    members.append([age, name])

# 나이순으로 배열을 정렬합니다.
members.sort()

# 정렬된 배열을 출력합니다.
for member in members:
    print(f"{member[0]} {member[1]}")

 

 

➡️ 정답 코드

# 회원의 수를 정하기 위한 숫자를 입력받습니다.
number = int(input())

# 2차원 배열을 생성합니다. 배열의 각 원소는 [나이, 이름] 형태입니다.
members = []

# 입력받은 수만큼 나이와 이름을 입력받아 배열에 추가합니다.
for i in range(number):
    age, name = input().split()
    age = int(age)
    members.append([age, name])

# 나이순으로 배열을 정렬합니다.
members.sort(key=lambda x: x[0])

# 정렬된 배열을 출력합니다.
for member in members:
    print(f"{member[0]} {member[1]}")