강의에서 말씀하신 방식으로 기업의 코딩테스트도 통과할수있나요?
416
6 câu hỏi đã được viết
이번에 다루신 문제에는 입력이 작았기 때문에 for문 내부에서 sort를 해도 문제가 없었다고 생각합니다.
그러나 코딩테스트 경험상, for문안에 sort()를 넣으면 대부분 시간 초과 오류가 났던 경험이 있는데요.
첫째, 입력이 더 큰 경우에 이 방식(매번 정렬)을 써도 되는지
둘째, 만약 시간 복잡도가 너무 커져서 시간초과가 날 가능성이 높다면 더 효율적인 방법은 없을까요?
Câu trả lời 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)기존에 윈도우 10으로 잘 써왔는데 윈도우 11로 바꾸고 나서 채점이 안됩니다.
1
98
2
스택에서 ')'을 만나는 경우
0
103
3
문제가 어디있나요?
0
84
2
변수 or 함수명
0
76
1
침몰하는 타이타닉 문제 질문입니다
0
70
1
AA.py 책점 에러
0
63
1
오늘 구매했는데 파이썬 자료구조 궁금한거 있으면 답변이 잘 될까요.
0
114
2
5.동전분배하기 문제 밑에코드도 정답이될까요?
0
114
1
아나그램 비교 코드
0
121
2
AA.PY파일 복사 후 채점 진행할때 오류 발생합니다.
0
163
2
문제 링크가있나여?
0
152
2
채점기 Time Limit Exceeded 오류 문의
1
175
2
동적계획법은 사용하는 문제
0
130
2
제 코드 좀 봐주세요
0
154
1
예외가 존재할 가능성?
0
99
1
3번이 안풀립니다
0
97
0
5번 틀림
0
121
0
오류원인?
0
103
0
리스트 선언
0
113
1
침몰하는 타이타닉(그리디) 문제 질문
0
114
1
알고리즘
0
71
1
코딩테스트
0
98
1
DFS 순서 질문드립니다.
0
133
2
left, right를 사용한 풀이법에 대한 질문입니다
0
93
1