문제 정보
https://www.acmicpc.net/problem/8979
문제
올림픽은 참가에 의의가 있기에 공식적으로는 국가간 순위를 정하지 않는다. 그러나, 많은 사람들이 자신의 국가가 얼마나 잘 하는지에 관심이 많기 때문에 비공식적으로는 국가간 순위를 정하고 있다. 두 나라가 각각 얻은 금, 은, 동메달 수가 주어지면, 보통 다음 규칙을 따라 어느 나라가 더 잘했는지 결정한다.
- 금메달 수가 더 많은 나라
- 금메달 수가 같으면, 은메달 수가 더 많은 나라
- 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라
각 국가는 1부터 N 사이의 정수로 표현된다. 한 국가의 등수는 (자신보다 더 잘한 나라 수) + 1로 정의된다. 만약 두 나라가 금, 은, 동메달 수가 모두 같다면 두 나라의 등수는 같다. 예를 들어, 1번 국가가 금메달 1개, 은메달 1개를 얻었고, 2번 국가와 3번 국가가 모두 은메달 1개를 얻었으며, 4번 국가는 메달을 얻지 못하였다면, 1번 국가가 1등, 2번 국가와 3번 국가가 공동 2등, 4번 국가가 4등이 된다. 이 경우 3등은 없다.
각 국가의 금, 은, 동메달 정보를 입력받아서, 어느 국가가 몇 등을 했는지 알려주는 프로그램을 작성하시오.
입력
입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 국가를 나타내는 정수와 이 국가가 얻은 금, 은, 동메달의 수가 빈칸을 사이에 두고 주어진다. 전체 메달 수의 총합은 1,000,000 이하이다.
출력
출력은 단 한 줄이며, 입력받은 국가 K의 등수를 하나의 정수로 출력한다. 등수는 반드시 문제에서 정의된 방식을 따라야 한다.
서브태스크
1 | 8 | 예제 입력, 출력 |
2 | 12 | N = 2 |
3 | 20 | 모든 국가의 은메달 및 동메달 획득 수는 0 |
4 | 25 | N ≤ 500 |
5 | 35 | 추가적인 제약 조건은 없다. |
접근방법
lamda 함수 사용
메달 기준으로 순위가 정해지기 때문에 그냥 sort 나 sorted 를 쓰면 국가번호 기준으로
정렬이 이루어지기 때문에 순위를 찾아낼 수 없다.
금,은,동 메달 갯수 비교
문제에서 주어진 기준에 따라서 구현하기만 하면 된다.
내 풀이
N, T = map(int, input().split())
# 타겟 국가
TC = []
# 나머지 국가
EC = []
for i in range(N):
c, g, s, b = map(int, input().split())
if c == T:
TC.append([c, g, s, b])
else:
EC.append([c, g, s, b])
# 금메달 기준 정렬
EC = sorted(EC, key=lambda x: x[1], reverse=True)
rank = 1
for i in range(len(EC)):
# 금 금이 타겟 국가 보다 크면 타겟 국가의 랭크는 떨어짐
if EC[i][1] > TC[0][1]:
rank += 1
# 금 갯수가 동일 하면
elif EC[i][1] == TC[0][1]:
# 은 비교
if EC[i][2] > TC[0][2]:
rank += 1
elif EC[i][2] == TC[0][2]:
# 동 비교
if EC[i][3] > TC[0][3]:
rank += 1
print(rank)
국가를 나눠서 리스트에 넣어준다.
TC = 순위를 찾고싶은 국가의 정보
EC = 그 외 나머지 국가의 정보
(여기서는 국가 번호까지 같이 리스트에 넣어줬지만 굳이 넣어 줄 필요는 없을 것 같다)
rank 는 1로 설정해준다.
등수 = 자신보다 잘하는 나라 + 1 이기 때문에
1등 = 0 + 1 이기 때문이다.
금메달을 기준으로 정렬해주고 각 국가들을 비교해준다.
1. 타겟 국가보다 금메달이 많으면 더이상 비교할 것 없이 타겟 국가의 순위가 한순위 떨어진다.
2. 금메달 갯수가 동일하다면 은메달의 갯수를 비교하고, 은메달이 적으면 타겟 국가의 순위가 한순위 떨어진다.
3. 은메달 갯수가 동일하다면 동메달의 갯수를 비교하고, 동메달이 적으면 타겟 국가의 순위가 한순위 떨어진다.
다른사람 풀이
N, T = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
# 금 은 동 순서대로 정렬
# arr 는 이미 메달 순으로 정렬돼 있음
arr = sorted(arr, key=lambda x: (x[1], x[2], x[3]), reverse=True)
idx = 0
rank = 1
if arr[0][0] != T:
for i in range(1,N):
if arr[i][0] == T:
idx = i
# idx 의 위치까지 비교하면 됨 그 뒤는 어차피 볼것도 없이 순위가 낮음
for j in range(idx):
# 국가 번호 제외하고 금, 은, 동 이 같지 않으면 나보다 타겟 국가보다 윗 순위
if arr[j][1:] != arr[idx][1:]:
rank += 1
print(rank)
금, 은, 동 순서로 국가를 정렬해준다.
이렇게 되면 메달순으로 국가가 정렬돼 있다.
타겟으로 삼은 국가의 위치를 찾아줄 idx 와 순위를 찾아줄 rank 변수를 만들어준다.
가장 앞에있는 국가가 타겟 국가가 아닐 경우에 for 문을 돌면서 타겟 국가를 찾고
타겟 국가가 위치해있는 인덱스 번호를 idx 변수에 담아준다.
다시 for 문을 돌되 타겟 국가가 있는 위치까지만 순회한다.
어차피 타겟국가보다 인덱스 번호가 큰 나라들은
타겟 국가보다 후 순위이기 때문이다.
슬라이싱을 통해서 국가 번호를 제외한 금, 은, 동 메달의 갯수가 동일한지 비교해준다.
동일하지 않다면 타겟 국가보다 선순위 이기 때문에 rank 를 1 더해준다.
느낀점
람다 함수를 사용해야 한다. 라는건 바로 떠올랐지만
어떻게 해야 타겟으로 하는 국가의 순위를 찾을 수 있을지 고민이 많이 됐다.
해설을 살~짝 봤고 그냥 그대로 구현하면 된다는 글을 보고 바로 문제에 주어진 조건대로 구현했다.
코드를 제출하고 다른사람의 코드를 보면서 정말 많이 놀랐다.
코드 자체는 나도 충분히 이해 가능했지만 어떻게 이런 풀이를 생각했을까?
슬라이싱을 자주 안쓰다 보니까 점점 더 안쓰는 것 같은데 사용할 수 있는 상황이 오면 종종 사용해보자
늘 느끼지만 한끗이 부족해서 문제를 못푸는 경우가 너무 많다.
문제를 많이 풀어보지 못해서 그런 것 같기는 한데...
언제쯤이면 간단한 문제의 해결책을 바로 떠올릴 수 있을까
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 1197 최소 스패닝 트리 (파이썬) (0) | 2022.10.28 |
---|---|
백준 5014 스타트 링크 (파이썬) (0) | 2022.10.13 |
백준 10971 외판원 순회 2 (파이썬) (조합 생성방법) (0) | 2022.09.24 |
백준 1182 부분수열의 합 (파이썬) (부분 집합 생성 방법) (0) | 2022.09.24 |
백준 1967 트리의 지름 (파이썬) (0) | 2022.09.21 |