강의에서 말씀하신 방식으로 기업의 코딩테스트도 통과할수있나요?

미해결질문
drather 프로필

이번에 다루신 문제에는 입력이 작았기 때문에 for문 내부에서 sort를 해도 문제가 없었다고 생각합니다. 

그러나 코딩테스트 경험상, for문안에 sort()를 넣으면 대부분 시간 초과 오류가 났던 경험이 있는데요. 

첫째, 입력이 더 큰 경우에 이 방식(매번 정렬)을 써도 되는지

둘째, 만약 시간 복잡도가 너무 커져서 시간초과가 날 가능성이 높다면 더 효율적인 방법은 없을까요?

김태원 프로필
김태원 1달 전

안녕하세요^^

섹션자체가 정렬을 이용하는게 컨셉이다 보니 그랬던 것 같습니다.

만약 이 문제가 입력중 창고 가로의 길이인 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)
drather 프로필
drather 1달 전

답변 감사합니다!! 덕분에 좋은 스킬 알았습니다. 

지식공유자 되기
많은 사람들에게 배움의 기회를 주고,
경제적 보상을 받아보세요.
지식공유참여
기업 교육을 위한 인프런
“인프런 비즈니스” 를 통해 모든 팀원이 인프런의 강의들을
자유롭게 학습하는 환경을 제공하세요.
인프런 비즈니스