1205. 등수 구하기
접근 방식
이 문제로 블로그를 작성하는 이유는,
1차 풀이 때 맞추었지만 이후 다른 정답 코드들을 보니까 상당히 꼬아서 생각했다는 느낌이 들어서 내 풀이와 다른 사람의 풀이를 비교해보기 위함이다!
먼저 내가 풀이한 방식이다.
접근 방식(본인 풀이)
파이썬의 라이브러리 중 분할 이분 탐색이 가능한 bisect의 사용을 가장 먼저 떠올렸다.
본인이 고려해주었던 조건은
1. 랭킹 리스트가 꽉 차지 않은 경우
2. 랭킹 리스트가 꽉 찼으나, 새 점수가 이전 점수보다 더 좋아 삽입이 가능한 경우위 두가지이다.
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
N, Taesu, P = map(int, input().rstrip().split())
arr = []
if N > 0:
arr = list(map(int, input().rstrip().split()))
arr.sort()bisect는 정렬이 되어있는 상태에서 bisect_left() 또는 bisect_right()를 통해 왼쪽 또는 오른쪽에 삽입 가능한 인덱스를 반환한다.
예제 3에서 0 0 50이 입력되었을 경우, N이 0일 때에는 점수 리스트를 입력값으로 주지 않기에, N > 0의 조건에서만 arr을 입력받도록 구현했다.
여기서 의문이 들었던 것은, 문제에서 내림차순 정렬이 이미 되어있는 형태로 점수 리스트를 제공하는데! 이 배열을 바탕으로 bisect를 사용하려니 인덱스를 제대로 반환하지 않는 것을 발견했다.
그래서 bisect를 최대한 활용해 문제를 풀이하고자 오름차순 정렬을 1회 해줬다.
1️⃣ 랭킹 리스트가 꽉 차지 않은 경우
if len(arr) < P: # 랭킹 리스트가 꽉 차지 않은 경우
idx = bisect_left(arr, Taesu)
arr.insert(idx, Taesu)
score = len(arr) - bisect_right(arr, Taesu) + 1
print(score)랭킹 리스트가 꽉 차지 않은 경우의 코드다.
bisect_left()를 사용해 태수의 점수가 들어갈 인덱스 번호를 반환받았고,
리스트에 insert()로 해당 인덱스의 점수를 넣어줬다.
이 때 등수는, 현재 점수가 오름차순으로 되어있으므로 리스트의 길이에서 태수의 점수가 오른쪽에서 삽입될 때 위치 + 1을 해줬다.
2️⃣ 랭킹 리스트가 꽉 찼으나, 새 점수가 이전 점수보다 더 좋아 삽입이 가능한 경우
elif min(arr) < Taesu: # 랭킹 리스트가 꽉 찼지만, 새 점수가 이전 점수보다 더 좋은 경우
arr[arr.index(min(arr))] = Taesu
score = len(arr) - bisect_right(arr, Taesu) + 1
print(score)
else:
print(-1)랭킹 리스트가 꽉 찬 경우의 코드다.
이 때에는 새 점수가 이전 점수보다 더 좋을 때에만 랭킹 리스트에 추가가 가능하기 때문에
태수의 점수가 arr의 최솟값보다 클 때, 최솟값의 인덱스 위치와 맞바꿔주도록 코드를 작성했다.
3️⃣ 태수의 점수가 랭킹에 오르지 못하는 경우
else:
print(-1)위 두 조건을 모두 만족하지 못하는 경우는 태수의 점수가 랭킹에 오르지 못하는 경우이므로,
문제에 명시된 -1을 출력해줬다.
최종 코드
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
N, Taesu, P = map(int, input().rstrip().split())
arr = []
if N > 0:
arr = list(map(int, input().rstrip().split()))
arr.sort()
if len(arr) < P: # 랭킹 리스트가 꽉 차지 않은 경우
idx = bisect_left(arr, Taesu)
arr.insert(idx, Taesu)
score = len(arr) - bisect_right(arr, Taesu) + 1
print(score)
elif min(arr) < Taesu: # 랭킹 리스트가 꽉 찼지만, 새 점수가 이전 점수보다 더 좋은 경우
arr[arr.index(min(arr))] = Taesu
score = len(arr) - bisect_right(arr, Taesu) + 1
print(score)
else:
print(-1)
다른 풀이
import sys
input = sys.stdin.readline
N, Taesu, P = map(int, input().rstrip().split())
if N:
arr = list(map(int, input().rstrip().split()))
arr.append(Taesu) # 태수 점수 추가
arr.sort(reverse=True) # 내림차순 정렬
idx = arr.index(Taesu) + 1
if idx > P: # idx가 P보다 큰 경우(랭킹 리스트에 올라가지 못하는 경우)
print(-1)
else:
if N == P and Taesu == arr[-1]: # 현재 리스트와 랭킹에 오를 수 있는 리스트의 수가 같음 + 태수가 꼴등의 점수인 경우
print(-1)
else:
print(idx)
else:
print(1)내가 꼬아서 생각해도 한참을 꼬아서 생각했다고 느끼게 된 풀이다...
특히 이분 탐색을 여기서 선택하는 것이 풀이 방법을 생각하고 코드로 옮기는 데에 더 많은 시간을 잡아먹었고, bisect를 사용하기에 오름차순으로 정렬을 다시 해줬으므로 등수를 표시하기 위한 연산도 직관적이지 못했던 것 같다.
메모리나 소요 시간의 경우 이 풀이나 나의 풀이나 비슷하지만,
조금 더 단순하게 접근해서 스스로 만든 복잡함에 꼬이지 않도록 하는 연습을 해야겠다!
배운점
▶️ bisect는 정렬된 상태에서 사용이 가능함
▶️ ⭐️ 쉽게 접근하는 능력 기르기
▶️ 문제 예외조건 잘 체크하기
▶️ 꼬아서 생각했을 땐 더 쉽게 풀이할 수 있는 방법으로 우회하는 것에 겁먹지 않기
