* Do it 코딩테스트 책을 참고하였습니다.
투 포인터라는 개념을 이용하면 시간 복잡도를 줄일 수 있습니다. 투 포인터란 연속된 숫자의 양 끝점의 인덱스를 변수로 가지고, 두 점을 이용하여 배열을 이동해나가며 두 인덱스 사이의 값이 원하는 값이 되는지를 확인하며 탐색하는 방법이다.
두 끝점(i,j)가 있고, i <= j인 경우 i가 한 칸 움직이는 것은 arr[i]의 값을 빼준다는 의미가 되고, j가 한 칸 움직이는 것은 arr[j+1]의 값을 더해준다는 것이다.더해나가며 i와 j사이의 숫자의 합이 원하는 값과 일치하면 j의 값을 한칸 움직여 그 다음 경우의 수를 탐색해나가는 것이 이 함수의 구조이다.
void solution_006()
{
int start_index = 1;
int end_index = 1;
int sum = 1;
int N = 15;
int count = 1;
while (N != end_index)
{
if (sum > N)
{
sum -= start_index;
start_index++;
}
else if (sum < N)
{
end_index++;
sum += end_index;
}
else
{
count++;
end_index++;
sum += end_index;
}
}
cout << count;
}
'코딩테스트' 카테고리의 다른 글
슬라이딩 윈도우를 이용한 문제 풀이 - DNA 비밀번호 (0) | 2023.02.08 |
---|---|
투 포인터 개념을 이용한 문제 풀이 - '좋은 수' 구하기 (0) | 2023.02.04 |
투 포인터를 이용한 문제 풀이 - 주몽의 망령 (0) | 2023.02.04 |
합 배열을 이용한 나머지 합 구하기 (0) | 2023.02.02 |
BFS 문제 풀기 -> 미로 찾기 (0) | 2023.02.02 |
댓글