Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 너비 우선 탐색
- Python
- SQL 고득점 KIT
- level 3
- dfs
- 파이썬
- javascript
- Lv. 0
- 자바스크립트
- SQL
- 동적계획법
- bfs
- select
- 오블완
- 티스토리챌린지
- Java
- 프로그래머스
- join
- softeer
- 소프티어
- Lv. 2
- DP
- C언어
- Lv. 1
- Lv. 3
- 깊이 우선 탐색
- group by
- programmers
- LEVEL 2
- Dynamic Programming
Archives
- Today
- Total
몸과 마음이 건전한 SW 개발자
코드트리 | Two Pointer / 가장 짧은 부분합 {언어 : Python} [다시 풀어 보기] 본문
문제 링크
https://www.codetree.ai/missions/8/problems/shortest-subtotal/submissions
내 코드
n, k = map(int, input().split())
nums = list(map(int, input().split()))
tot = nums[0]
answer = 100000
r = 0
for l in range(n):
while r + 1 < n and tot < k:
tot += nums[r+1]
r += 1
if tot >= k:
answer = min(answer, r - l + 1)
tot -= nums[l]
if answer == 100000:
print(-1)
else:
print(answer)
풀이 방법
- 두 포인터 초기화
- 배열의 시작 지점을 가리키는 왼쪽 포인터 l과 끝 지점을 가리키는 오른쪽 포인터 r을 설정한다.
- 처음에는 두 포인터가 배열의 첫 번째 원소를 가리킨다.
- 현재 부분 배열의 합을 저장하는 변수 tot를 초기화한다.
- 오른쪽 포인터 이동 (확장)
- 현재 부분 배열의 합 tot이 목표값 k보다 작으면, 오른쪽 포인터를 이동시켜 배열의 다음 원소를 포함한다.
- 새로운 원소를 tot에 추가하여 현재 합을 갱신한다.
- 조건 만족 시 최소 길이 계산
- 부분 배열의 합 tot이 k 이상이 되면, 현재 부분 배열의 길이를 계산한다.
- 길이는 (오른쪽 포인터 - 왼쪽 포인터 + 1)로 구한다.
- 계산한 길이를 기존의 최소 길이와 비교하여 더 짧은 값을 갱신한다.
- 부분 배열의 합 tot이 k 이상이 되면, 현재 부분 배열의 길이를 계산한다.
- 왼쪽 포인터 이동 (축소)
- 왼쪽 포인터를 이동하여 현재 부분 배열의 시작점을 변경한다.
- 이때, 시작점이 빠지므로 tot에서 해당 값을 빼서 갱신한다.
- 이렇게 하면 부분 배열의 길이를 줄이면서도 조건을 만족하는지 확인할 수 있다.
- 반복
- 왼쪽 포인터를 배열의 끝까지 이동시키면서 위의 과정을 반복한다.
- 오른쪽 포인터는 조건에 따라 계속 확장하거나 유지되므로, 배열 전체를 완전히 탐색할 필요 없이 효율적으로 작업이 이루어진다.
- 결과 출력
- 만약 k 이상의 합을 가지는 부분 배열이 한 번도 없다면, 결과로 -1을 출력한다.
- 그렇지 않다면, 최소 길이를 출력한다.
작동 예제
예제 배열
- 배열: [5, 1, 3, 5, 10, 7, 4, 9, 2, 8]
- 목표값: k = 15
과정
- 초기 상태: tot = 5, l = 0, r = 0.
- 오른쪽 포인터 이동: tot = 5 + 1 + 3 + 5 = 14, 조건 미충족.
- 계속 이동: tot = 14 + 10 = 24, 조건 충족 → 길이 계산 → 최소 길이 = 5.
- 왼쪽 포인터 이동: tot = 24 - 5 = 19, 조건 충족 → 길이 갱신 → 최소 길이 = 4.
- 반복: 최단 길이 = 2까지 갱신.
출력
- 조건을 만족하는 부분 배열의 최소 길이: 2.
느낀점
- 이렇게 계산한다는 것을 이제 알았다...
- 아직 갈 길이 멀다.
'알고리즘 > 다시 풀어 보기' 카테고리의 다른 글
프로그래머스 [Lv. 4] 올바른 괄호의 갯수 {언어 : Python} [다시 풀어 보기] (0) | 2024.11.26 |
---|---|
프로그래머스 [Lv. 4] 무지의 먹방 라이브 {언어 : JavaScript} [다시 풀어 보기, 힙X] (0) | 2024.11.25 |
프로그래머스 [Lv. 3] 아방가르드 타일링 {언어 : JavaScript} [다시 풀어 보기] (1) | 2024.11.14 |
프로그래머스 [Lv. 3] 에어컨 {언어 : JavaScript} [다시 풀어 보기] (0) | 2024.11.11 |
프로그래머스 [Lv. 3] 사라지는 발판 {언어 : Python} [다시 풀어 보기] (0) | 2024.11.06 |