Cộng đồng Hỏi & Đáp của Inflearn
câu hỏi đã được viết
강의에서 말씀하신 방식으로 기업의 코딩테스트도 통과할수있나요?
Viết
·
408
12
이번에 다루신 문제에는 입력이 작았기 때문에 for문 내부에서 sort를 해도 문제가 없었다고 생각합니다.
그러나 코딩테스트 경험상, for문안에 sort()를 넣으면 대부분 시간 초과 오류가 났던 경험이 있는데요.
첫째, 입력이 더 큰 경우에 이 방식(매번 정렬)을 써도 되는지
둘째, 만약 시간 복잡도가 너무 커져서 시간초과가 날 가능성이 높다면 더 효율적인 방법은 없을까요?
python코테 준비 같이 해요!
Quiz
58% người trả lời sai. Hãy thử ngay!
이분 검색 알고리즘을 사용하기 위한 필수 조건은 무엇일까요?
데이터의 총합이 일정해야 한다
데이터가 미리 정렬되어 있어야 한다
데이터의 개수가 짝수여야 한다
데이터가 모두 양수여야 한다
Câu trả lời 2
16
codingcamp
Người chia sẻ kiến thức
안녕하세요^^
섹션자체가 정렬을 이용하는게 컨셉이다 보니 그랬던 것 같습니다.
만약 이 문제가 입력중 창고 가로의 길이인 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
