이 문제는 프로그래머스의 분류 실수이다 처음에는 그리디 문제로 계획을 했겠지만 후에 테스트케이스를 추가하면서 완전 탐색으로 풀게 변경되었다. 문제의 알고리즘이 변경되면 분류도 변경되어야 하지만 해당부분이 변경되지 않아 푸는데 많은시간을 소비하게 됬다
그리디로 풀었을 때의 코드는
#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;
}'백준(코테준비) > 증가수열&투포인터' 카테고리의 다른 글
| 백준 2473 / CPP / 투포인터 (0) | 2025.01.15 |
|---|---|
| 백준 2631 / C++ (0) | 2024.08.09 |
| 백준 14719 (0) | 2024.07.31 |
| 백준 1644 (0) | 2024.07.26 |
| 백준 2170 (0) | 2024.07.19 |
