99클럽 코테 스터디 13일차 TIL - 정렬

[Silver IV] 선택의 기로 - 30970

문제 링크

성능 요약

메모리: 122996 KB, 시간: 556 ms

분류

정렬

제출 일자

2024년 4월 23일 23:45:47

문제 설명

[사진]

촉석루

품질이냐 가격이냐, 그것이 문제로다..

진주 나들이를 온 보선이는 기념품으로 촉석루 미니어처를 사기로 했다. 촉석루는 진주성에 있는 누각이며 경상남도 유형문화재 중 하나로, 진주성의 남쪽 지휘대로 사용됨과 동시에 논개가 촉석루 앞 의암에서 순국한 것으로 알려져 유명한 곳이다.

촉석루 미니어처를 사기 위해 기념품 가게에 들른 보선이는 놀라움을 금치 못했다. 왜냐하면, 가게에는 각양각색의 촉석루 미니어처가 진열되어 있었기 때문이다. 그리고 모든 촉석루 미니어처는 장인이 한 땀 한 땀 심혈을 기울여서 만들어서 그런지 품질과 가격이 천차만별이었고, 품질과 가격이 전부 동일한 두 촉석루 미니어처는 없었다. 각양각색의 촉석루 미니어처를 본 보선이는 물욕이 폭발할 뻔했지만 가까스로 마음을 진정시키고, 촉석루 미니어처를 두 개만 사기로 했다. 보선이는 두 가지 방법으로 촉석루 미니어처를 골라보기로 했는데, 이는 다음과 같다.

• 진열되어 있는 촉석루 미니어처 중에서 품질이 가장 높은 촉석루 미니어처를 골라 가져온다. 만약 그런 미니어처가 여러 개라면 가격이 가장 낮은 것을 골라 가져온다. 이 과정을 두 번 반복하는 것이 첫 번째 방법이다.
• 진열되어 있는 촉석루 미니어처 중에서 가격이 가장 낮은 촉석루 미니어처를 골라 가져온다. 만약 그런 미니어처가 여러 개라면 품질이 가장 높은 것을 골라 가져온다. 이 과정을 두 번 반복하는 것이 두 번째 방법이다.

보선이가 각 방법에 따라 촉석루 미니어처들을 고르게 될 때 어떤 촉석루 미니어처들을 고르게 되는지 알아보자.

입력

첫 번째 줄에는 기념품 가게에 진열되어 있는 촉석루 미니어처의 개수 N$N$이 주어진다. (2≤N≤100000)$(2 ≤ N ≤ 100\,000)$ 

두 번째 줄부터 N$N$개의 줄에 걸쳐 가게에 진열되어 있는 i$i$번째 촉석루 미니어처 종류의 품질 Qi$Q_i$, 가격 Pi$P_i$가 공백으로 구분되어 주어진다. (1≤Qi,Pi≤10000)$(1 ≤ Q_i, P_i ≤ 10\,000)$ 

입력으로 주어지는 모든 수는 정수이다.

출력

첫 번째 줄에는 첫 번째 방법을 선택했을 때의 첫 번째로 고른 촉석루 미니어처의 품질과 가격, 두 번째로 고른 촉석루 미니어처의 품질과 가격을 공백으로 구분하여 순서대로 출력한다.

두 번째 줄에는 두 번째 방법을 선택했을 때의 첫 번째로 고른 촉석루 미니어처의 품질과 가격, 두 번째로 고른 촉석루 미니어처의 품질과 가격을 공백으로 구분하여 순서대로 출력한다.

첫 번째 방법의 결과가 두 번째 방법의 결과에 영향을 미치지 않는다.

 

풀이

N = int(input())
first = []  # 첫 번째 방법에 따라 정렬
second = [] # 두 번째 방법에 따라 정렬

for _ in range(N) :
    a, b = map(int, input().split())
    first.append((-a, b))   # 품질을 음수로 변환하여 정렬 시 높은 품질이 앞에 오도록 함
    second.append((b, -a))  # 가격은 그대로, 품질은 음수로 변환하여 정렬 시 낮은 가격이 앞에 오고, 같은 가격일 경우 높은 품질이 앞에 오도록 함

first.sort()
second.sort()

print(-first[0][0], first[0][1], -first[1][0], first[1][1])
print(-second[0][1], second[0][0], -second[1][1], second[1][0])

첫 번째 줄에는 P1, Q1, P2, Q2 

두 번째 줄에는 Q1, P1, Q2, P2

를 출력하는 문제이다.

 

first와 second 배열을 살펴보면,

first =       [(-3, 1), (-2, 2), (-2, 3), (-1, 1)]
second = [(1, -3), (1, -1), (2, -2), (3, -2)]

 

품질이 높은 것을 먼저 뽑을 시에는 품질이 높은 것 부터 출력을 하기 때문에, 앞에 오기 위해서는 음수로 정렬.

가격이 낮은 것을 먼저 뽑을 시에는 가격이 낮은 것 부터 출력을 하기 때문에, 앞에 오기 위해서는 양수로 정렬.

 

기본적으로 정렬은 작은 수부터 앞에 오기 때문에, 정렬의 특성을 사용하기 위해서 위의 방식을 채택하였다.