프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/178870
⌛ 54분
def solution(sequence, k):
answer = [len(sequence),0,len(sequence)-1]
front = 0
rear = 0
tmp = sum(sequence[front:rear+1])
len_seq = len(sequence)
sequence += [0]
while front<=rear and front>=0 and rear<=len_seq-1:
if tmp==k:
length = rear-front+1
if length < answer[0]:
answer = [length,front,rear]
elif length == answer[0] and front<answer[1]:
answer = [length,front,rear]
rear += 1
tmp += sequence[rear]
elif tmp<k:
rear += 1
tmp += sequence[rear]
else:
tmp -= sequence[front]
front += 1
return answer[1:]
비내림차순(오름차순, 중복O)의 수열(sequence)이 주어질 때, 연속된 구간의 합이 k인 구간 중 길이가 가장 짧으며 시작 인덱스가 가장 앞에 있는 구간을 구하는 문제입니다.🐍🐍🐍
전형적인 투 포인터 알고리즘 문제입니다.
이를 구현하기 위해 시작 인덱스(front)와 끝 인덱스(rear)를 0,0으로 초기화한 뒤, 현재 구간의 합이 작다면 rear를 늘리고 크거나 같다면 front를 늘리는 방식으로 구현하였습니다.
이때 구간의 합이 k를 만족한다면, 구간의 길이와 시작 인덱스를 고려하여 답을 초기화하였습니다.
[다른 사람의 풀이1]
def solution(sequence, k):
answers = []
sum = 0
l = 0
r = -1
while True:
if sum < k:
r += 1
if r >= len(sequence):
break
sum += sequence[r]
else:
sum -= sequence[l]
if l >= len(sequence):
break
l += 1
if sum == k:
answers.append([l, r])
answers.sort(key=lambda x: (x[1]-x[0], x[0]))
return answers[0]
'나의 풀이'와 같이 현재 구간의 합이 크다면 끝 인덱스(r)를 늘리고 같거나 작다면(l) 인덱스를 늘린 방식입니다.🐥🐥🐥
이후, lambda식을 통해 구간의 길이/시작 인덱스를 기준으로 정렬하여 답을 도출하였습니다.
[다른 사람의 풀이2]
def solution(sequence, k):
answer = []
start, end = 0,0
temp = sequence[0]
min_len = 1000001
while start <= end < len(sequence):
if temp == k :
if end - start + 1 < min_len :
min_len = end - start + 1
answer = [start, end]
temp -= sequence[start]
start += 1
elif temp < k :
end += 1
if end < len(sequence) :
temp += sequence[end]
elif temp > k :
temp -= sequence[start]
start += 1
return answer
이외 다른 풀이들도 투 포인터 알고리즘을 활요한 방식이였습니다.
감사합니다.