이 문제는 3개를 어떻게 할까 고민하다가 그냥 1개를 정해놓고 0의 가장 가까운 투포인터를 하면 되겠다는 생각을 했다 즉 하나의수는 고정인 상태에서 0보다크면 혹은 작으면 에 대해서 m값과 r값을 바꿔주면서 최솟값을 저장하는 방식으로 진행했다
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
using namespace std;
int n;
vector<long long> inputData;
long long result = 3000000001;
long long ans[3];
int main() {
cin >> n;
long long tmp;
for (int i = 0; i < n; i++) {
cin >> tmp;
inputData.push_back(tmp);
}
sort(inputData.begin(), inputData.end());
int l, m, r;
for (int l = 0; l < n - 2; l++) {
m = l + 1;
r = n - 1;
while (m < r) {
long long val = inputData[l] + inputData[m] + inputData[r];
if (abs(val) < result) {
result = abs(val);
ans[0] = inputData[l];
ans[1] = inputData[m];
ans[2] = inputData[r];
}
if (val < 0) {
m++;
}
else {
r--;
}
}
}
for (int i = 0; i < 3; i++) {
cout << ans[i] << " ";
}
}
이 문제는 프로그래머스의 분류 실수이다 처음에는 그리디 문제로 계획을 했겠지만 후에 테스트케이스를 추가하면서 완전 탐색으로 풀게 변경되었다. 문제의 알고리즘이 변경되면 분류도 변경되어야 하지만 해당부분이 변경되지 않아 푸는데 많은시간을 소비하게 됬다
그리디로 풀었을 때의 코드는
#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
bool isVisited[20] = { 0, };
int nextIdx(int idx) {
if (idx + 1 == n) {
return 0;
}
else
return idx + 1;
}
int beforeIdx(int idx) {
if (idx - 1 == -1) {
return n - 1;
}
else {
return idx - 1;
}
}
int solution(string name) {
int idx = 0;
int beforeDif = 1;
string alphaAs = "";
int nIdx;
int bIdx;
n = name.size();
for (int i = 0; i < n; i++) {
alphaAs += 'A';
}
int answer = 0;
while (name.compare(alphaAs) != 0) {
isVisited[idx] = true;
answer += min(name[idx] - 'A', 'Z' - name[idx] + 1);
name[idx] = 'A';
int left_idx = idx;
int right_idx = idx;
int leftCnt = 0;
int rightCnt = 0;
while (name[left_idx] == 'A' && leftCnt<n) {
if (name.compare(alphaAs) == 0) {
return answer;
}
left_idx = beforeIdx(left_idx);
leftCnt++;
}
while (name[right_idx] == 'A' && rightCnt<n) {
if (name.compare(alphaAs) == 0) {
return answer;
}
right_idx = nextIdx(right_idx);
rightCnt++;
}
if (leftCnt < rightCnt) {
answer += leftCnt;
idx = left_idx;
}
else {
answer += rightCnt;
idx = right_idx;
}
}
return answer;
}
이렇게 되지만 해당 부분이 정답이 아니었다. 이에 프로그래머스 커뮤니티를 찾아보니 그리디로 풀리지 않는다고 나왔다. 이 문제는 어떻게 보면 투포인터 혹은 탐색문제의 가깝다
이 문제의 알파벳 탐색 방향은 총 4가지다
1. 오른쪽으로 쭉 탐색하기 2. 왼쪽으로 쭉 탐색하기 3. 왼쪽으로 갔다가 오른쪽으로 가기 4. 오른쪽으로 갔다가 왼쪽으로 가기 즉 1번어떠한 지점까지 갔다가 다시되돌아오면서 탐색하는 거 까지가 이 문제의 진행 방향이다 여러번되면 최소인 1번과 2번의 횟수보다 많아지기에 해당 로직은 검사하지 않는다
예시로 JAZAAAP 라는 문자가 있다고 생각하자
일단 우리는 방향을 바꿀 지점이 필요하고 방향을 바꾸고 어디까지 탐색할지에 대한 지점이 필요하다
자 이 문제를 우리가 해결하기 위해서는 처음 받은 문자열에서 가장 긴 문자열을 탐색 하지 않아야 한다 이에 우리가 이문제를 풀기 위해서는 가장 긴 AAA가 나오는 부분을 건너지 말아야하므로 해당 영역의 시작점 X와 Y를 구해야한다
해당 예시에서 구해지면 이렇게 된다. 즉 이렇게 우리가 구간을 나눴을 때 우리는 방향을 바꿔서 원점에서 -> y -> x 와 원점에서 ->x->y 에서의 최솟값을 구해야 한다.
원점에서 왼쪽으로 y를 탐색하고 x를 탐색하는 것의 식은 (n-y)+(n-y)+x 이고 원점에서 오른쪽으로 x를 탐색하고 y를 탐색하는 것의 식은 x+x+(n-y)이다
이에 우리는 특정 x를 기준으로 가장 긴 A가 만들어지는 Y를 찾으면 되는 문제이다 그후 두영역에서 방향을 바꾼다고 가정할 때의 최솟값이 커서의 이동의 최소 횟수 임으로 해당 횟수 + 문자를 A로 바꾸는횟수를 더해주면 된다
#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int solution(string name) {
int upDownMove[26] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,12,11,10,9,8,7,6,5,4,3,2,1 };
int ans = 0, n = name.size();
int leftRightMove = n - 1;
for (int x = 0; x < n; x++) {
ans += upDownMove[name[x] - 'A'];
int y = x + 1;
while (y < n && name[y] == 'A') y++;
leftRightMove = min(leftRightMove, min(x + x + (n - y), x + (n - y) + (n - y)));
}
ans += leftRightMove;
return ans;
}
이 문제는 내가 완전 감을 잘못 잡고 풀고 있었다. 이 문제를 증가수열 비슷하게 풀려고 했었다 하지만 이렇게 풀면 로직이 꼬였는데 테스트케이스 몇개는 잘나왔으나 몇개는 매우 잘 나오지 않았다.
이 문제의 로직은 현재 나를 기준으로 내왼쪽에서의 최대높이와 내오른 쪽의 최대높이를 비교해서 낮은 높이를 선택 해주는 문제 였다 단 오른쪽 과 왼쪽의 최대높이가 나보다는 클때만 빗물이 받아지니 해당 상황일때만 계산하도록 코드를 작성한다 그림으로 나타내면 대충 아래와 같다
해당 로직에 대한 코드는 아래 와 같다
#include <iostream>
#include<algorithm>
using namespace std;
int h, w;
int arr[500];
int main() {
cin >> h >> w;
int result = 0;
for (int i = 0; i < w; i++) {
cin >> arr[i];
}
for (int i = 1; i < w - 1; i++) {
int lmax = 0;
int rmax = 0;
for (int j = 0; j < i; j++) {
if (lmax < arr[j] && arr[j]>arr[i])
lmax = arr[j];
}
for (int j = i + 1; j < w; j++) {
if (rmax < arr[j] && arr[j]>arr[i])
rmax = arr[j];
}
if (lmax != 0 && rmax != 0)
result += min(lmax, rmax) - arr[i];
}
cout << result;
}
이 문제는 투 포인터 문제이다 이중 포문으로도 구현이 가능하나 해당 방식으로 할경우 시간 복잡도가 커진다 이에 루프문 한개로 해당 문제를 해결하는 게 핵심이다
이 문제의 로직은 일단 이어지는 선들을 최대한 길게 이어진 후 끊어졌을 때 부터 선을 다시 쭉 길게 이어서 이 선 2개의 길이의 합을 구하는 것이다
주어진 테스트 케이스를 v1.first를 기준으로 정렬하면 해당 그림 처럼 된다. 아래칸은 시작점 위에 칸은 끝나는 점을 의미한다. 이 리스트는 오름차순 정렬을 했다고 가정했기에 첫번째로 나오는 선은 1부터 시작해서 길게 늘일 것이다 즉 첫번째 상태일때
이렇게 된다 그후에 2부터 5까지를 비교했을 때 이 두선은 이어짐으로 start는 그대로 두고 end를 5로 바꿔준다
그 다음 3부터 5까지도 이 선과 끝점은 같지만 시작점이 다름으로 기존에 있던 선임으로 포함을 시키지 않는다 아직도 start는 1 end 는 5이다 그 후 6과 7을 만났을때는 아래그림처럼 된다
6과 7을 만났을 때는 새 선임으로 기존에 있던 선의 길이를 일단 값을 누적시켜준후 리스틀 끝나지 탐색한후 해당 start와 end값을 다시 더해준다
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
int sum = 0;
cin >> n;
vector<pair<int, int>> v;
for (int i = 0; i < n; i++) {
int n1, n2;
cin >> n1>>n2;
v.push_back({ n1,n2 });
}
sort(v.begin(), v.end());
int start = v[0].first;
int end = v[0].second;
for (int i = 1; i < n; i++) {
if (end > v[i].first) {
end = max(v[i].second, end);
}
else {
sum += end - start;
start = v[i].first;
end = v[i].second;
}
}
sum += end - start;
cout << sum;
}
