https://school.programmers.co.kr/learn/courses/30/lessons/178870#
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
처음에는 이중 for문으로 풀었다. 테스트 코드는 통과하였으나
시간 초과가 났다.
어떻게 애들을 더해서 k를 비교할까 고민하다가
처음에 이중for문으로 생각한 방법은 이렇게 시작 인덱스를 줄여서 더해가다가 k 값과 비교해서 해야지~였다.
def solution(sequence, k):
answer = []
min_difference = float('inf')
selected_numbers =None
for i in range(len(sequence)):
total_sum =0
for j in range(i, len(sequence)):
total_sum+= sequence[j]
if total_sum ==k:
if (abs(j-i) < min_difference):
min_difference = abs(j-i)
selected_numbers = (i,j)
break
return selected_numbers
문제는 조회하는 배열의 최대 길이가
5 ≤ sequence의 길이 ≤ 1,000,000
였기에 이중포문을 하면 이차시간으로 계산되어 제곱이 되어 초과된다.
시간복잡도 참고)
그다음에 for문을 사용하지 않고 어떻게 맨앞자리 인덱스를 줄일지 고민했다.
여기서 오래 막혔다.
시간초과 없애려고 이중포문 없애고 해봤는데
i부터 j까지 계속 더해지는거 i를 조작못했다.
2차 시도 (사실 2차는 아니긴한데..)
index = 0
start = 1
for i in range(start, len(sequence)):
sequence[index] += sequence[i]
print("sequence[index]:",sequence[index])
if i == len(sequence)-1:
index += 1
start +=1
return selected_numbers이 코드는 그저 처음부터 끝까지 더하기만 한다.
처음에 포인터로 시작과 끝을 가리키는 방법을 쓰려했는데 for문으로 어차피 다 조회하니까 시작만
가리키면 되겠다고 생각해서 반복문에 집착한 것이 나의 실수였다..결국 한참 헤매다가 답지를 봤다.
최종 코드
def solution(sequence, k):
answer =[]
start = 0
end =0
min = 1000000000
total = sequence[0]
while (start <= end < len(sequence)):
if (total == k):
if min > end- start+1:
min = end - start+1
answer =[start, end]
total -= sequence[start]
start += 1
elif (total < k):
end+= 1
if end< len(sequence):
total += sequence[end]
elif (total > k):
total -= sequence[start]
start += 1
return answer1. start end 시작과 끝 두 포인터의 관계 설정이 중요
start <= end
시작포인터와 끝포인터는 같은 곳에서 시작하고 만나서 같을 수는 있어도 넘어서는 안된다.
나는 계속 전체 배열의 길이만 넘지 말라고 맞춰서 리스트에서 벗어나는 에러가 발생했다.
2. 전체 배열의 값을 더하는 total을 어떻게 처리할지
total 정의할 때 sequence[0] 첫번째 값을 할당하고 시작하면 된다.
total은 구하고자 하는 k값을 기준으로 나뉜다.
<바로 생각하기 힘들었던 부분>
1. total == k일 때 시작과 끝 두사이 거리가 최소인 값을 찾고 나서
배열 끝까지 다시 시작과 끝을 움직여야 하는데
end를 움직여도 될거라 생각했다.
그렇게 한 결과 end값이 먼저 배열범위보다 커져버려서 테스트 통과를 못했다.
전체에서 start인덱스의 값을 빼주고 start인덱스를 옮기는 것으로 수정했다.
2. while범위에서 배열의 범위만큼 돌라고 했으니 문제 없을거라 생각했지만
end를 하나씩 추가하고 그 값을 sequence의 인덱스로 넣기 위해 조건을 안 걸면 저렇게 에러가 났다.
결론 반복문에 그만 집착하고 효율적인 풀이를 생각해보자
컴퓨터가 우리 뇌구조랑 비슷하겠다는 생각을 했다. 생각한게 맞을 수도 있으니 포기말고 구현해봐라
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
| 프로그래머스 Lv.3 최고의 집합 (1) | 2023.09.07 |
|---|
