문제 링크
문제 요약
Lesson 4의 Counting Elements 에 해당한다.정수 N과 배열 A가 input으로 들어온다. 이때, 배열 A에 들어있는 숫자에따라 연산 방법이 달라진다.
- A[K]의 숫자가 1 ≤ X ≤ N 이라면, K 인덱스에 위치한 값을 1 증가
- A[K]의 숫자가 N+1이라면, max counter 연산이 실행
- Max Counter 연산이란, 현재 연산된 값들 중 가장 큰 값으로 모든 배열의 값들을 초기화
더 자세한 내용들은 위의 링크로 이동하여 확인해보길 바란다.
문제 풀이 #1 - 시간 복잡도 O(n*m) 66%
def solution(N, A):
# Implement your solution here
answer = [0]*N # 정답 길이만큼 초기화
for i in range(0, len(A)):
if A[i] <= N:
answer[A[i]-1] +=1
#print(answer)
elif A[i] > N:
max_num = max(answer)
tmp = [max_num] *N
answer = tmp
#print(answer)
return answer문제 풀이 #2 - 시간 복잡도 O(n+m) ✅정답
def solution(N, A):
# Implement your solution here
answer = [0] *N
max_counter = N +1
temp = 0
curr_max = 0
for i in A:
if i < max_counter: #그냥 더하기
if answer[i-1] < temp:
#만약 max counter 발생 후에 temp에 저장된 값보다 작다면
#max counter 발생 전에 최대값보다 작았다.
answer[i-1] = temp +1
else:
answer[i-1] += 1
if answer[i-1] > curr_max:
#계속해서 현재 최대값 update
curr_max = answer[i-1]
else:
# Max counter 발생!
temp = curr_max #temp 변수에 현재 max_val 값을 저장
for idx in range(N):
if answer[idx] < temp:
answer[idx] =temp
return answer📌 고려해야할 점
-
1번 풀이가 가장 생각하기 쉬운 풀이지만, 큰 숫자들이 들어왔을 때, answer의 배열이 계속 update 되기 때문에 시간 복잡도가 증가할 수 밖에 없다.
-
따라서, 정답 배열을 바로 바로 update를 해주지 않고, for문을 돌면서 현재 정답 배열에서의 최대값을 저장하고 비교하고 업데이트 방식을 택한다.
-
만약, max counter가 실행되었고 그 다음 연산은 그냥 더하기 연산이라면, 배열 전체를 update하지 않고 temp 변수에 저장된 값에 1을 더하는 것으로 진행한다.
즉, temp에 저장된 변수는 가장 최근에 max counter가 발생 시 해당 값으로 update 될 값이다.
🙄 느낀 점
처음에 이 문제를 접했을 때는 10분만에 풀고 뭐야 쉬운데? 라고 생각했지만 나의 큰 착각이었다. 코딜리티에서 푸는 문제들은 테스트 케이스를 적게 보여주고 얼마나 효율적으로 코드를 짰는지 평가하는 기분이 든다.
특히, 이 문제 같은 경우에는 시간 복잡도를 생각하며 문제를 해결하면 생각보다 문제 난이도가 올라간다고 생각한다. 다른 사람들의 풀이를 보고 이해하고 다시 코드를 짜보는데 꽤 오랜 시간이 필요했다. 내가 만약 이 문제를 시험장에서 만났다면, 시간 안에 시간 복잡도까지 고려한 문제를 풀 수 있었을지는 조금 의문이 든다. 아직 많이 부족하다,, ㅎㅎ :[
