[프로그래머스][C++] 가장 가까운 같은 글자
가장 가까운 같은 글자
문제 링크
분석
문자열에서 자신의 앞에 가장 가까운 글자를 찾아 값을 저장하고 반환하는 문제입니다.
중첩 반복문으로 문자열의 이전 등장 위치를 탐색하고, 이를 기반으로 거리를 계산하는 방법이 있습니다.
맵을 사용해서 각 문자의 마지막 등장 위치를 저장하고, 이를 기반으로 거리를 계산하는 방법이 있습니다.
풀이
중첩 반복문을 사용한 방법입니다.
#include <string>
#include <vector>
using namespace std;
vector<int> solution(string s) {
vector<int> answer;
for (int i = 0; i < s.length(); ++i)
{
for (int j = answer.size(); j >= 0; --j)
{
if (0 == j)
{
answer.push_back(-1);
}
else if (s[j - 1] == s[i])
{
answer.push_back(i - (j - 1));
break;
}
}
}
return answer;
}
첫 반복문에서는 문자열 s에 대해 순회합니다.
두 번째 반복문에서는 현재 문자의 이전 등장 위치를 찾으며, answer의 크기만큼 역순으로 순회합니다.
각 조건에서 문자를 처리합니다.
(s[j - 1] == s[i])의 경우 j - 1은 size()가 1부터 시작하므로 -1 해줍니다.
조건은 이전에 있던 문자와 현재 문자가 동일하다면입니다.
만약 조건이 참이라면 현재 위치(i)에서 앞에있는 가장 가까운 문자의 위치까지 거리를 계산해서 추가합니다.
가장 가까운 문자의 위치까지의 값을 구할 때 j는 1부터 시작하므로 값을 1 빼줍니다.
맵을 사용한 방법입니다.
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> solution(string s) {
vector<int> answer(s.size(), -1);
unordered_map<char, int> lastIndex;
for (int i = 0; i < s.length(); ++i)
{
char curChar = s[i];
if (lastIndex.find(curChar) != lastIndex.end())
{
answer[i] = i - lastIndex[curChar];
}
lastIndex[curChar] = i;
}
return answer;
}
s를 순회하면서 이전에 있던 문자라면 현재 위치(i)부터 이전 위치까지의 거리를 구해 저장합니다.
std::unordered_map은 키 값은 중복되지 않으므로 같은 문자에 대해 마지막으로 등장한 위치 값이 갱신됩니다.
성능 요약
중첩 반복문을 사용한 성능입니다.
테스트 1 〉 통과 (0.01ms, 4.22MB)
테스트 2 〉 통과 (0.03ms, 4.14MB)
테스트 3 〉 통과 (0.05ms, 4.14MB)
테스트 4 〉 통과 (0.22ms, 4.14MB)
테스트 5 〉 통과 (4.10ms, 5.28MB)
테스트 6 〉 통과 (1.47ms, 4.42MB)
테스트 7 〉 통과 (2.53ms, 5.24MB)
테스트 8 〉 통과 (0.73ms, 4.32MB)
테스트 9 〉 통과 (2.61ms, 5.02MB)
테스트 10 〉 통과 (0.44ms, 4.2MB)
테스트 11 〉 통과 (2.37ms, 4.93MB)
테스트 12 〉 통과 (0.01ms, 4.16MB)
테스트 13 〉 통과 (0.01ms, 4.02MB)
테스트 14 〉 통과 (0.11ms, 4.28MB)
테스트 15 〉 통과 (0.01ms, 4.2MB)
테스트 16 〉 통과 (0.01ms, 4.16MB)
테스트 17 〉 통과 (0.02ms, 4.21MB)
테스트 18 〉 통과 (0.74ms, 4.13MB)
테스트 19 〉 통과 (0.51ms, 4.16MB)
테스트 20 〉 통과 (0.09ms, 3.79MB)
테스트 21 〉 통과 (0.02ms, 4.02MB)
테스트 22 〉 통과 (1.21ms, 4.58MB)
테스트 23 〉 통과 (0.10ms, 3.74MB)
테스트 24 〉 통과 (0.13ms, 4.21MB)
테스트 25 〉 통과 (0.21ms, 4.43MB)
테스트 26 〉 통과 (0.04ms, 4.2MB)
테스트 27 〉 통과 (0.16ms, 4.2MB)
테스트 28 〉 통과 (0.16ms, 4.2MB)
테스트 29 〉 통과 (0.01ms, 3.69MB)
테스트 30 〉 통과 (2.95ms, 5.27MB)
std::unordered_map을 사용한 방법입니다.
테스트 1 〉 통과 (0.01ms, 4.15MB)
테스트 2 〉 통과 (0.04ms, 4.21MB)
테스트 3 〉 통과 (0.03ms, 4.22MB)
테스트 4 〉 통과 (0.21ms, 4.18MB)
테스트 5 〉 통과 (4.26ms, 5.75MB)
테스트 6 〉 통과 (0.89ms, 4.41MB)
테스트 7 〉 통과 (2.33ms, 5.73MB)
테스트 8 〉 통과 (0.69ms, 4.24MB)
테스트 9 〉 통과 (2.10ms, 5.51MB)
테스트 10 〉 통과 (0.68ms, 4.22MB)
테스트 11 〉 통과 (2.14ms, 5.49MB)
테스트 12 〉 통과 (0.01ms, 3.72MB)
테스트 13 〉 통과 (0.01ms, 3.64MB)
테스트 14 〉 통과 (0.10ms, 4.23MB)
테스트 15 〉 통과 (0.01ms, 4.21MB)
테스트 16 〉 통과 (0.02ms, 4.15MB)
테스트 17 〉 통과 (0.02ms, 4.16MB)
테스트 18 〉 통과 (0.36ms, 4.14MB)
테스트 19 〉 통과 (0.44ms, 4.16MB)
테스트 20 〉 통과 (0.09ms, 4.11MB)
테스트 21 〉 통과 (0.03ms, 4.14MB)
테스트 22 〉 통과 (1.01ms, 4.6MB)
테스트 23 〉 통과 (0.09ms, 4.02MB)
테스트 24 〉 통과 (0.13ms, 4.18MB)
테스트 25 〉 통과 (0.16ms, 3.73MB)
테스트 26 〉 통과 (0.04ms, 4.13MB)
테스트 27 〉 통과 (0.15ms, 4.15MB)
테스트 28 〉 통과 (0.13ms, 3.83MB)
테스트 29 〉 통과 (0.01ms, 3.69MB)
테스트 30 〉 통과 (2.45ms, 5.75MB)
댓글남기기