728x90
https://school.programmers.co.kr/learn/courses/30/lessons/68646
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
분석
- 배열의 양쪽의 최솟값 중 하나라도 자신보다 클 경우 끝까지 남을 수 있음
- 배열 인덱스 값마다 최솟값을 일일히 계산하면 시간초과
풀이
1. stack
Time: 135.97 ms
def solution(a):
stack = []
for x in a:
if len(stack) < 2:
stack.append(x)
else:
while(len(stack) >= 2 and stack[-2] < stack[-1] > x):
stack.pop(-1)
stack.append(x)
return len(stack)
2. 최솟값 비교
Time: 328.18 ms
def solution(a):
answer = 1
M = min(a)
for _ in range(2):
m = a[0]
i = 1
while m != M:
if m >= a[i]:
m = a[i]
answer += 1
i += 1
a.reverse()
return answer
3. 최솟값 memoization
Time: 642.23 ms
# 양쪽의 최솟값 중 하나라도 자신보다 클 경우 끝까지 남을 수 있음
def solution(a):
if len(a)==1: return 1
answer=2 # 양쪽 끝
n=len(a)
lm=[a[0]]
rm=[a[-1]]
for i in range(1, n):
# 왼쪽 최솟값 저장
if a[i]<lm[-1]:
lm.append(a[i]) # 최솟값 추가
else:
lm.append(lm[-1]) # 기존값 추가
# 오른쪽 최솟값 저장
if a[-1-i]<rm[-1]:
rm.append(a[-1-i]) # 최솟값 추가
else:
rm.append(rm[-1]) # 기존값 추가
rm.reverse()
for i in range(1, n-1):
if lm[i-1]>a[i] or rm[i+1]>a[i]:
answer+=1
return answer
월간코드챌린지
728x90