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

상어 키우기 성공

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1.5 초 1024 MB 1314 382 299 32.013%
문제

인천대학교의 앞바다에는
$N$마리의 상어가 살고 있다고 한다. 각각의 상어는 서로 같거나 다른 크기의 몸집
$A_i$를 가지고 있다. 상어의 세계는 완전한 약육강식의 세계로, 상어 자신의 크기보다 작은 상어는 전부 먹을 수 있다. 이때, 상어의 크기는 잡아먹힌 상어의 크기만큼 커지게 된다. 반면, 자신의 크기 이상인 상어는 전혀 잡아먹지 못한다.

어느 날 크기가
$T$인 샼이라는 이름의 아기 상어는 인천대학교 앞바다에 존재하는
$N$마리 상어들의 크기 정보를 모두 입수했다. 똑똑한 아기 상어 샼은 인천대학교 앞바다에 있는 상어들을 최대
$K$마리까지 적절한 순서로 잡아먹고, 자신의 몸집을 최대로 키울 계획을 하고 있다.

샼이 최선의 선택으로 최대
$K$마리의 상어를 적절한 순서로 잡아먹었을 때, 몸집이 최대 얼마까지 커질 수 있는지 구해보자.

입력
첫째 줄에 인천대학교 앞바다에 존재하는 상어의 마릿수
$N$과, 샼이 먹을 수 있는 상어의 최대 마릿수
$K$, 샼의 최초 크기를 나타내는 정수
$T$가 공백으로 구분되어 주어진다.
$(1\le K \leq N \le 200,000, \space 1 \le T \le 10^9)$ 

둘째 줄에는 인천대학교 앞바다에 존재하는
$N$마리의 상어 크기를 나타내는 정수
$A_i$가 각각 공백으로 구분되어 주어진다.
$(1 \le A_i \le 10^9)$ 

출력
샼이 최선의 선택으로 최대
$K$마리의 상어를 적절한 순서로 잡아먹었을 때, 몸집이 최대 얼마까지 커질 수 있는지 출력하시오.

정답은 32비트 정수 변수(int) 범위를 초과할 수 있기 때문에 64비트 정수 변수(C/C++ : long long, JAVA : long)를 사용해야 한다.

del/remove 시간 차이

문제를 풀다보면 가끔 자신이 참 부끄러워지는 문제가 몇개 있다.
그게 바로 이 문제이다.

처음에 binary search를 한 후
슬라이싱으로 요소를 빼려고 했다가 당연하게 시간초과
remove()를 사용했다가 한번더 시간초과
이후 긴장이 되면서 먹은 상어를 채크 후 먹지 않은 상어를 큰 상어부터 채크

했으나 예외케이스를 발견 못해서 틀림 x2
곰곰히 생각해보다가 내가 잘못생각한건가 싶어서
리스트 요소 제거를 다시 생각해봄

import bisect
from sys import stdin

def find_shark(T, shark):
    cal = bisect.bisect_left(shark, T)
    return cal

N, K, T = map(int, stdin.readline().split())
shark = list(map(int, stdin.readline().split()))

shark.sort()

count = 0

for i in range(K):
    position = find_shark(T, shark)
    
    if position > 0:
        T += shark[position - 1] 
        count += 1
        del shark[position - 1] 
    else:
        break  

print(T)

그래서 나온 코드가 위의 코드이다.
단순하게 del을 쓰면 되는 것이었다...
del은 위치의 요소를 바로 지우고
슬라이싱은 새로운 리스트를 만드는것이라 비교 불가,
remove는 특정 값을 서칭하는데 시간이 오래걸린다는것을 까먹었다.

하지만 감이 잘 잡히지 않아서 테스트를 해 보았다.

먼저 del을 사용했을때는 0.77초가 걸렸다.

remove를 사용해도 시간초 차이가 거의 나지 않는 모습..
그래서 함수를 바꿨다.

일부러 서칭을 하게 만든 것이었다.
결과는 약 15배 가까이 시간이 오래 걸리게 되었다....
배움은 끝이 없는거 같다...

stack/binary search

그리고 내가 이 글을 쓰게 된 이유이다.
이번 문제의 최악의 케이스는 20만개 중 20만개를 선택해야 한다.
즉, binary search를 했을때 각 시행마다 최대 18번까지 연산해야 하고, (2^18 = 약 26만)
그걸 매번 연산마다 해야 하기 때문에 최악의 경우 서칭만 500만번 이상 해야되는 경우가 생긴다.

많은 사람들이 백준 서버를 돌릴때 1초 = 2000만번 정도의 연산을 잡는다.
그럼 리스트 돌리고 찾고 계산하고 등등을 생각했을때 가볍게 2000만번은 넘겠다 라는 생각이 드는 것이다.

그러니 pop/append를 쓰면 적게는 먹는 숫자만큼,
대충 생각해도 무조건 연산이 40만번 이하가 될 것이라는 판단이 든다.
왜냐? 상어가 20만마리 밖에 없는데 한번씩 다 넣고 다시 다 빼도 40만번이다.

binary search로 풀어도 풀린다.

풀어보니까 풀렸다.
하지만 재출한사람들 보니 내 시간의 반토막 난 사람들이 있어서 코드를 확인했고,
곰곰히 생각해보다가 나의 공부에 대한 반성이 필요하다고 느꼈다.

https://velog.io/@kts5927/계산량을-어떻게-추측할까
이전에도 한번 썼는데, 주어진 데이터의 크기에 맞게 알고리즘을 잘 선택하는것도
엄청나게 중요한것이라는걸 다시한번 깨닫게 되었다.