랩실에서 코딩테스트 스터디를 시작했다. 일찍 준비하면 좋지 않을까 ~ 해서 같이 하기로 했는데 평소 내가 풀던 레벨에서 한 1단계는 올라간 느낌이랄까... 맨날 풀면서 나는 취업할 수 있으려나 ~ 이러면서 푼다 ^^... 저번 주에는 일이 있어서 참석 못하고, 이번 주부터 시작! 일단 첫 번째 문제부터 정리를 시작해보쟈.
1. 문제
첫 번째 문제는 LeetCode 문제이다.
https://leetcode.com/problems/daily-temperatures/
Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1,1,4,2,1,1,0,0]
위와 같이 데이터가 주어졌을 때, 해당 날짜 (인덱스)로부터 얼마나 더 기다려야 더 따뜻한 날이 오는지 세어 날짜를 반환해주는 문제이다.
2. 풀이
1. 첫 번째 풀이: 실패
temperatures = [30, 60, 90]
cnt = 0
result = []
for i in range(len(temperatures)):
for j in range(i+1, len(temperatures)):
if temperatures[i] != max(temperatures[i:]):
if temperatures[i] < temperatures[j]:
cnt += 1
break
else:
cnt += 1
else:
cnt = 0
print(temperatures[i], temperatures[j], cnt, max( temperatures[i:] ))
result.append(cnt)
cnt = 0
print(result)참고로 나는 모든 풀이는 VSC에서 진행하였다.
첫 번째 풀이는 장렬히 실패했다. 그도 그럴 것이, 시간복잡도 하나도 고려 안하고 ~ 심지어 cnt로 숫자를 날짜를 하루씩 올려서 계산 비용이 더 들었기 때문이다. 중첩반복문은 정말... 쓸 때 신중해야겠구나를 또 한 번 느꼈다. (매번 느끼고 매번 고치질 못함)
일단 풀이를 설명하자면,
cnt = 0
result = []날짜를 셀 cnt, 해당 cnt를 추가해줄 result 리스트 선언했다.
for i in range(len(temperatures)):
for j in range(i+1, len(temperatures)):
if temperatures[i] != max(temperatures[i+1:]):
if temperatures[i] < temperatures[j]:
cnt += 1
break
else:
cnt += 1
else:
cnt = 0
print(temperatures[i], temperatures[j], cnt, max( temperatures[i:] ))
result.append(cnt)
cnt = 0
print(result)다음으로 중첩반복문(^^)을 사용해 빙글뱅글 돌려준다. 위의 예시를 들어 설명하면, 현재 73도 (물론 화씨다...) 일 때 j는 [74, 75, 71, 69, 72, 76, 73]의 값을 가진다. 어짜피 과거의 온도는 볼 필요 없으니까 뒤에 것만 슬라이싱 해오는 것이다.
그 후 만약 j의 리스트에서의 max 값이 i의 값과 동일하지 않다면 아무리 기다려도 해당 날짜보다 따뜻해지는 날은 없다는 뜻이 된다. 그러므로 바로 cnt를 0으로 준다. 하지만 max 값과 다르다면? 두 가지 경우로 나뉜다.
- i와 j의 온도를 비교했을 때, j의 온도가 높다면 cnt에 1을 더해주고 break를 이용해 바로 빠져나온다.
- i와 j의 온도를 비교했을 때, 둘이 같거나 i의 온도가 더 크다면 j 리스트의 다음 값을 탐색해야한다. 그러므로 cnt에 1을 더해주고 계속해서 반복문을 돈다.
리트코드에서 보는 첫 번째 submission 결과가 시간 초과라니... 여튼 그 후에 어떻게 풀 수 있을까 ~ 고민하다가
- index끼리 빼도 날짜를 받을 수 있잖아 ?!
- 마침 오늘 아침 백준에서 비슷한 문제를 풀었음 (stack)
를 통해,
값진 Accepted를 얻어냈다 ^^
2. 두 번째 풀이: 성공
temperatures = [30, 60, 90]
def dailyTemperatures(temperatures):
stack = []
result = [0]*len(temperatures)
for i, current in enumerate(temperatures):
while stack and current > temperatures[stack[-1]]:
index = stack.pop()
result[index] = i-index
stack.append(i)
return result
print(dailyTemperatures(temperatures))중첩 반복문을 이용하니 아무래도 시간복잡도가 너무 커져서... 반복문 이용은 필수니까 두 번 쓰지는 말자...! 라고 생각했다. 근데 또 이렇게 보니까 어짜피 while 문 써서 또 반복문 쓰는 게 맞는 거 같기도 하고...? 일단 하나하나 분석해보자.
stack = []
result = [0]*len(temperatures)일단 stack을 쌓을 리스트와 result에 애초부터! 0으로 초기화하여 len(temperatures) 만큼 배열을 만들어준다. 이렇게 하면 append 하는 (cnt) 계산이 사라져 조금은! 메모리 및 시간을 아낄 수 있다.
for i, current in enumerate(temperatures):
while stack and current > temperatures[stack[-1]]:
index = stack.pop()
result[index] = i-index
stack.append(i)
return result일단 temperatures를 enumerate를 씌워서 인덱스 값과 현재 기온값을 받아온다. 그리고 만약 stack이 빈 리스트면 이 인덱스 값(i)를 stack에 추가한다. 즉 stack은 현재 기온의 값을 저장하고 있는 것이다.
자, 그럼 지금부터 stack은 빈 리스트가 아니므로 while의 첫 번째 조건은 만족한다. 그럼 두 번째 조건을 보자. 두 번째 조건은 현재 기온과 stack의 마지막 값, 즉 현재 기온의 바로 전 인덱스 값의 temperature과 current 값을 비교한다. 이 부분은 첫 번째 풀이의,
if temperatures[i] < temperatures[j]:이 부분과 동일하다고 볼 수 있다. 저 때의 i와 지금 풀이의 stack[-1]이 동일한 값이다.
그래서 만약 current 값이 더 크면, 더 따뜻해지길 기다릴 필요가 없다! 그냥 바로 break 하는 거임.
그래서 stack에서 가장 마지막에 있는 값을 index로 뽑고 이 값을 result에 넣어 i와 index 값의 차이를 result[index]로 넣는 것이다.
stack에서 가장 마지막에 있는 값은 기준 값, 즉 현재값과 바로 비교하고 있는 그 인덱스이며, 이 인덱스와 연결된 result의 인덱스가 바로 기다려야 하는 날짜 수이다. 그래서 i와 index 값의 차이를 알아내면 끝이다.
여기서 기억해야 할 부분은
- 중첩반복문은 일단 돌리기라도 하자라는 마인드 아니면 쓰지 말자.
- stack은 뺐다 꺼냈다가 아주 자유롭다! 한 쪽 방향으로만 꺼낼 수 있을 뿐...
이상 오늘의 코드 분석 끝!
