인프런 커뮤니티 질문&답변
작성한 질문수
강의에서 말씀하신 방식으로 기업의 코딩테스트도 통과할수있나요?
작성
·
324
12
이번에 다루신 문제에는 입력이 작았기 때문에 for문 내부에서 sort를 해도 문제가 없었다고 생각합니다.
그러나 코딩테스트 경험상, for문안에 sort()를 넣으면 대부분 시간 초과 오류가 났던 경험이 있는데요.
첫째, 입력이 더 큰 경우에 이 방식(매번 정렬)을 써도 되는지
둘째, 만약 시간 복잡도가 너무 커져서 시간초과가 날 가능성이 높다면 더 효율적인 방법은 없을까요?
답변 2
16
김태원
지식공유자
안녕하세요^^
섹션자체가 정렬을 이용하는게 컨셉이다 보니 그랬던 것 같습니다.
만약 이 문제가 입력중 창고 가로의 길이인 L값과 높이 조정 횟수인 M값이 커진다면 매번 sort하는 코드로는 시간초과가 날겁니다. 이때는 리스트를 이용한 해쉬방법을 사용하면 좋습니다. 아래 코드를 분석해보세요.(입력크기는 본래 문제와 같다고 생각하고 짠 것입니다)
L=int(input())
arr=list(map(int, input().split()))
m=int(input())
cnt=[0]*101
maxH=float('-inf')
minH=float('inf')
for x in arr:
cnt[x]+=1
if x>maxH: maxH=x
if x<minH: minH=x
for _ in range(m):
if cnt[maxH]==1:
cnt[maxH]-=1
maxH-=1
cnt[maxH]+=1
else:
cnt[maxH]-=1
cnt[maxH-1]+=1
if cnt[minH]==1:
cnt[minH]-=1
minH+=1
cnt[minH]+=1
else:
cnt[minH]-=1
cnt[minH+1]+=1
print(maxH-minH)0
