-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
강의에서 말씀하신 방식으로 기업의 코딩테스트도 통과할수있나요?
20.07.27 15:40 작성 조회수 238
12
이번에 다루신 문제에는 입력이 작았기 때문에 for문 내부에서 sort를 해도 문제가 없었다고 생각합니다.
그러나 코딩테스트 경험상, for문안에 sort()를 넣으면 대부분 시간 초과 오류가 났던 경험이 있는데요.
첫째, 입력이 더 큰 경우에 이 방식(매번 정렬)을 써도 되는지
둘째, 만약 시간 복잡도가 너무 커져서 시간초과가 날 가능성이 높다면 더 효율적인 방법은 없을까요?
답변을 작성해보세요.
16
김태원
지식공유자2020.07.28
안녕하세요^^
섹션자체가 정렬을 이용하는게 컨셉이다 보니 그랬던 것 같습니다.
만약 이 문제가 입력중 창고 가로의 길이인 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
답변 2