04-3. 정렬 문제풀이

📝문제1. 백준 10825번(국영수)

- 문제

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

도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.

1. 국어 점수가 감소하는 순서로
2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)

입력

• 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다.
• 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다.
• 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
• 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다.

출력

• 문제에 나와있는 정렬 기준으로 정렬한 후 첫째 줄부터 N개의 줄에 걸쳐 각 학생의 이름을 출력한다.

예제 입력
12
Junkyu 50 60 100
Sangkeun 80 60 50
Sunyoung 80 70 100
Soong 50 60 90
Haebin 50 60 100
Kangsoo 60 80 100
Donghyuk 80 60 100
Sei 70 70 70
Wonseob 70 70 90
Sanghyun 70 70 80
nsj 80 80 80
Taewhan 50 60 90

예제 출력
Donghyuk
Sangkeun
Sunyoung
nsj
Wonseob
Sanghyun
Sei
Kangsoo
Haebin
Junkyu
Soong
Taewhan

- 나의 코드💻

n = int(input())
array = []
for i in range(n):
    array.append(list(input().split()))

array.sort(reverse=True, key=lambda x: x[1])

for i in range(0, n-1):
    if array[i][1] == array[i+1][1]:
        if array[i][2] > array[i+1][2]:
            array[i], array[i+1] = array[i+1], array[i]

    if array[i][1] == array[i+1][1] and array[i][2] == array[i+1][2]:
        if array[i][2] < array[i+1][2]:
            array[i], array[i+1] = array[i+1], array[i]

    if array[i][1] == array[i+1][1] and array[i][2] == array[i+1][2] and array[i][3] == array[i+1][3]:
        if ord(array[i][3]) > ord(array[i+1][3]):
            array[i], array[i + 1] = array[i + 1], array[i]


for i in array:
    print(i)

-> 실패

- 정답 코드💻

n = int(input())
array = []
for i in range(n):
    array.append(input().split())

'''
[정렬 기준]
1) 두 번째 원소를 기준으로 내림차순 정렬
2) 두 번째 원소가 같은 경우, 세 번째 원소를 기준으로 오름차순 정렬
3) 세 번째 원소가 같은 경우, 네 번째 원소를 기준으로 내림차순 정렬
4) 네 번째 원소가 같은 경우, 첫 번째 원소를 기준으로 오름차순 정렬
'''
array.sort(key=lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

for i in array:
    print(i[0])

- 비교 분석📖

파이썬에는 튜플을 원소로 하는 리스트가 있을 때, 그 리스트를 정렬하면 기본적으로 각 튜플을 구성하는 원소의 순서에 맞게 정렬된다는 특징이 있다.

예를 들어 튜플이 3개의 원소로 구성된다면 모든 원소가 첫 번째 원소의 순서에 맞게 정렬되고, 첫 번째 원소의 값이 같은 경우 두 번째 원소의 순서에 맞게 정렬되고, 거기에 두 번째 원소의 값까지 같은 경우 세 번째 원소의 순서에 맞게 정렬된다.

a = [(5, 1, 5), (3, 5, 5), (3, 1, 9), (3, 1, 1)]
a.sort()

print(a)
# [(3, 1, 1), (3, 1, 9), (3, 5, 5), (5, 1, 5)]

또한 리스트의 원소를 정렬할 때는 sort() 함수의 key 속성에 값을 대입하여 내가 원하는 '조건'에 맞게 튜플을 정렬시킬 수 있다. 위의 정답 코드를 보면 알 수 있다.

코드를 이상하고 비효율적으로 작성했고 심지어 그 과정이 너무 틀렸다.. 근데 정말 간단한 식으로 해결할 수 있어서 신기했다. 한 줄로 끝이 나네? 저 문법을 여기저기 잘 활용해봐야겠다.

---

📝문제2. 백준 18310번(안테나)

- 문제

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

일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다.

집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오.

예를 들어 N=4이고, 각 위치가 1, 5, 7, 9일 때를 가정하자.

이 경우 5의 위치에 설치했을 때, 안테나로부터 모든 집까지의 거리의 총 합이 (4+0+2+4)=10으로, 최소가 된다.

입력

• 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000)
• 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다.
  
  출력
• 첫째 줄에 안테나를 설치할 위치의 값을 출력한다. 단, 안테나를 설치할 수 있는 위치 값으로 여러 개의 값이 도출될 경우 가장 작은 값을 출력한다.

예제 입력 1
4
5 1 7 9

예제 출력 1
5

- 나의 코드💻

n = int(input())
home = [list(map(int, input().split()))]

target, m, cal = 0, 0, 0
for i in range(n):
    m += abs(home[0][0] - home[0][i])

for i in home[0]:
    for k in home[0]:
        cal += abs(i - k)
        if cal < m:
            m = cal
            target = i

print(target)

-> 시간 초과..

- 정답 코드💻

from sys import stdin
n = int(stdin.readline())
home = list(map(int, stdin.readline().split()))
home.sort()
print(home[(n-1)//2])

- 비교 분석📖

너무 복잡하게 생각했던 것 같다. 단순히 중간값을 찾으면 되는 문제이다.
풀이는 책에서 참고했고, 쉬운 문제지만 갑자기 이해가 안가는 지점이 생겨서 풀이를 찾아봤다.

참고 블로그!
https://on1ystar.github.io/algorithm/2021/02/22/Algorithm-10/

---

📝문제3. 백준 1181번(단어 정렬)

- 문제

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

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력
조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

예제 입력 1
13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

예제 출력 1
i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

- 나의 코드💻

처음 코드(맞기는 함)

n = int(input())
array = []
for i in range(n):
    array.append(input())

array.sort(key=lambda x: (len(x), x))

newarray = []
for i in array:
    if i not in newarray:
        newarray.append(i)
        print(i)

최종 코드(시간 단축, 인터넷 참고)

import sys
n = int(sys.stdin.readline())
array = []
for i in range(n):
    array.append(sys.stdin.readline().strip())

a = set(array)
array = list(a)

array.sort(key=lambda x: (len(x), x))

for i in array:
    print(i)

- 비교 분석📖

첫 번째 문제(국영수)랑 비슷한 것 같아서 같은 방법으로 풀었더니 해결할 수 있었다. 다만, 쉬운 문제 같은데 사소한 실수들 때문에 시간이 은근 많이 걸렸다..

블로그를 찾아보니 나보다 시간이 훨씬 적게 걸려서 나도 시간을 단축시켜보려고 이런저런 방법들을 사용해봤다. 그 결과 처음보다 시간이 훨씬 단축되어서 신기했다.

1. import sys 사용 -> 관련 문법을 더 찾아봐야겠다.
2. 처음에 입력받은 직후에 set으로 바꿔 중복을 미리 제거해주기 -> 이렇게 하니 시간이 훨씬 단축되었다.