투포인터
2개의 포인터로 알고리즘의 시간 복잡도를 최적화할 수 있음
2018
🐬접근
N의 최댓값이 10,000,000 이므로 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한시간 2초를 초과함. 따라서 O(n)의 시간 복잡도 알고리즘을 써야함.
연속된 자연수이므로 투포인터를 활용해 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현할 수 있음
시작 인덱스(s)를 1씩 증가시킨다(오른쪽으로 1칸 움직인다) = 연속된 자연수에서 왼쪽 값을 삭제
종료 인덱스(e)를 1씩 증가시킨다(오른쪽으로 1칸 움직인다) = 연속된 자연수 범위 확장
투포인터 이동 원칙
- sum > N : sum -= s ; s += 1;
- sum < N : e += 1; sum += e ;
- sum == N : e += 1, sum += e , cnt += 1;
풀이
import sys
input = sys.stdin.readline
N = int(input())
s,e = 1, 1 # 시작 인덱스, 종료 인덱스
cnt = 1 #정수 자기 자신포함시킨 상태로 초기화
sum = 1 #1부터 합 시작
while e != N : # 종료 인덱스가 N 자기 자신이 되기 전까지 수행
if sum == N :
# 합 성립
print(f'{N}달성 : {list(range(s,e+1))}')
cnt += 1
e += 1
sum += e
elif sum > N :
# N 초과할 경우 시작인덱스를 빼줌
print(f'{N}초과 : {list(range(s,e+1))}')
sum -= s
s+=1
else:
# 종료 인덱스를 늘려가며 sum 누적
print(f'{N}미만 : {list(range(s,e+1))}')
e += 1
sum += e
print(cnt)
## 출력예시
15
15미만 : [1]
15미만 : [1, 2]
15미만 : [1, 2, 3]
15미만 : [1, 2, 3, 4]
15달성 : [1, 2, 3, 4, 5]
15초과 : [1, 2, 3, 4, 5, 6]
15초과 : [2, 3, 4, 5, 6]
15초과 : [3, 4, 5, 6]
15달성 : [4, 5, 6]
15초과 : [4, 5, 6, 7]
15초과 : [5, 6, 7]
15미만 : [6, 7]
15초과 : [6, 7, 8]
15달성 : [7, 8]
15초과 : [7, 8, 9]
15초과 : [8, 9]
15미만 : [9]
15초과 : [9, 10]
15미만 : [10]
15초과 : [10, 11]
15미만 : [11]
15초과 : [11, 12]
15미만 : [12]
15초과 : [12, 13]
15미만 : [13]
15초과 : [13, 14]
15미만 : [14]
'🏷️CS > Algorithm' 카테고리의 다른 글
[백준] 1253 (좋다) (1) | 2023.03.01 |
---|---|
[백준] 1940 (주몽) (0) | 2023.03.01 |
[백준] 10986 (나머지 합) (0) | 2023.02.25 |
[백준] 11660(구간 합 구하기 5) (0) | 2023.02.25 |
[백준] 11659 (구간 합 구하기 1) (0) | 2023.02.25 |