#1. 문제
#2. 풀이
1. 투 포인터 알고리즘
[정의] : 투 포인터 알고리즘은 두 개의 포인터를 활용해 원하는 조건을 만족하는 부분 배열을 찾는 알고리즘입니다.
[특징] : 투 포인터 알고리즘은 일반적으로 정렬된 배열 혹은 리스트에서 활용합니다.
[동작 방식]
1. 배열의 시작 위치를 가리키는 포인터, 배열의 마지막 위치를 가리키는 포인터, 두 개의 포인터를 초기화
2. 두 포인터가 움직이며, 주어진 조건을 만족하는 부분 배열을 찾습니다.
3. 조건을 만족할 경우, 원하는 동작을 수행하고 마칩니다.
4. 조건을 만족하지 못할 경우, 두 포인터의 위치 변경을 시도합니다.
5. 원하는 해를 얻을 때까지, 2~4번 동작을 반복합니다.
2. set 컨테이너
[정의] : C++의 STL에서 제공하는 set 컨테이너는 중복을 허용하지 않고, 정렬된 상태를 유지하는 노드 기반의 연관 컨테이너입니다. set 컨테이너는 Key 값을 원소로 이루어진 집합입니다.
[특징] : set 컨테이너는 균형 이진트리로 구현되어, 내부적으로 정렬된 상태를 유지합니다.
[성능] : set 컨테이너의 탐색/삽입/삭제 연산의 최악 시간 복잡도는 O(log n)입니다.
3. Mod 연산으로 right 포인터의 위치를 설정하자!
- 배열의 시작 위치를 가리키는 포인터, 이를 기준으로 +1 씩 점점 증가하는 포인터를 통해 투 포인터 알고리즘을 시작합니다.
- 두 포인터가 가리키는 위치 사이에 존재하는 항목들의 누적 합을 계산하여 set 컨테이너에 삽입하고, 시작 위치를 가리키던 포인터와 부분 배열의 마지막 위치를 가리키던 포인터를 1씩 증가시키며 시작 위치를 가리키던 포인터가 배열의 끝 위치에 도달할 때까지 알고리즘을 수행합니다.
#3. 코드
#include <string>
#include <vector>
#include <set>
using namespace std;
int solution(vector<int> elements)
{
set<int> s;
for (int i = 1; i <= (int)elements.size(); ++i)
{
// 최소 연속 부분 수열 개수 = 1
int left = 0;
// 최대 연속 부분 수열 개수 = elements.size()
int right = left + i;
// 왼쪽 경계가 배열의 마지막 원소를 가리킬 때 까지 진행
while (left < elements.size())
{
int sum = 0;
for (int j = left; j < right; ++j)
{
sum += elements[(j % (int)elements.size())];
}
// set 컨테이너에 삽입(중복 불가)
s.insert(sum);
left++;
right++;
}
}
return s.size();
}
'문제 풀이 > Programmers 문제 풀이' 카테고리의 다른 글
[Programmers]#Level2_의상, 해시, unordered_map (0) | 2024.03.21 |
---|---|
[Programmers]#Level2_주식가격, 스택, 히스토그램 유형 (0) | 2024.03.21 |
[Programmers_C++]#Level2_멀리 뛰기, dp, 동적 프로그래밍 (0) | 2023.12.24 |
[Programmers_C++]#Level2_귤 고르기, map, priority_queue, 우선순위 큐 (0) | 2023.12.24 |
[Programmers_C++]#Level2_N개의 최소 공배수, 유클리드 호제법, 최대 공약수, 최소 공배수 (0) | 2023.12.24 |
#1. 문제
#2. 풀이
1. 투 포인터 알고리즘
[정의] : 투 포인터 알고리즘은 두 개의 포인터를 활용해 원하는 조건을 만족하는 부분 배열을 찾는 알고리즘입니다.
[특징] : 투 포인터 알고리즘은 일반적으로 정렬된 배열 혹은 리스트에서 활용합니다.
[동작 방식]
1. 배열의 시작 위치를 가리키는 포인터, 배열의 마지막 위치를 가리키는 포인터, 두 개의 포인터를 초기화
2. 두 포인터가 움직이며, 주어진 조건을 만족하는 부분 배열을 찾습니다.
3. 조건을 만족할 경우, 원하는 동작을 수행하고 마칩니다.
4. 조건을 만족하지 못할 경우, 두 포인터의 위치 변경을 시도합니다.
5. 원하는 해를 얻을 때까지, 2~4번 동작을 반복합니다.
2. set 컨테이너
[정의] : C++의 STL에서 제공하는 set 컨테이너는 중복을 허용하지 않고, 정렬된 상태를 유지하는 노드 기반의 연관 컨테이너입니다. set 컨테이너는 Key 값을 원소로 이루어진 집합입니다.
[특징] : set 컨테이너는 균형 이진트리로 구현되어, 내부적으로 정렬된 상태를 유지합니다.
[성능] : set 컨테이너의 탐색/삽입/삭제 연산의 최악 시간 복잡도는 O(log n)입니다.
3. Mod 연산으로 right 포인터의 위치를 설정하자!
- 배열의 시작 위치를 가리키는 포인터, 이를 기준으로 +1 씩 점점 증가하는 포인터를 통해 투 포인터 알고리즘을 시작합니다.
- 두 포인터가 가리키는 위치 사이에 존재하는 항목들의 누적 합을 계산하여 set 컨테이너에 삽입하고, 시작 위치를 가리키던 포인터와 부분 배열의 마지막 위치를 가리키던 포인터를 1씩 증가시키며 시작 위치를 가리키던 포인터가 배열의 끝 위치에 도달할 때까지 알고리즘을 수행합니다.
#3. 코드
#include <string>
#include <vector>
#include <set>
using namespace std;
int solution(vector<int> elements)
{
set<int> s;
for (int i = 1; i <= (int)elements.size(); ++i)
{
// 최소 연속 부분 수열 개수 = 1
int left = 0;
// 최대 연속 부분 수열 개수 = elements.size()
int right = left + i;
// 왼쪽 경계가 배열의 마지막 원소를 가리킬 때 까지 진행
while (left < elements.size())
{
int sum = 0;
for (int j = left; j < right; ++j)
{
sum += elements[(j % (int)elements.size())];
}
// set 컨테이너에 삽입(중복 불가)
s.insert(sum);
left++;
right++;
}
}
return s.size();
}
'문제 풀이 > Programmers 문제 풀이' 카테고리의 다른 글
[Programmers]#Level2_의상, 해시, unordered_map (0) | 2024.03.21 |
---|---|
[Programmers]#Level2_주식가격, 스택, 히스토그램 유형 (0) | 2024.03.21 |
[Programmers_C++]#Level2_멀리 뛰기, dp, 동적 프로그래밍 (0) | 2023.12.24 |
[Programmers_C++]#Level2_귤 고르기, map, priority_queue, 우선순위 큐 (0) | 2023.12.24 |
[Programmers_C++]#Level2_N개의 최소 공배수, 유클리드 호제법, 최대 공약수, 최소 공배수 (0) | 2023.12.24 |