[프로그래머스 1단계] 가장 가까운 같은 글자 -c++

[프로그래머스 1단계] 가장 가까운 같은 글자 -c++

처음에 10점 나왔는데 '='하나 추가하니깐 바로 100점 .. ㅜㅜ

 

풀이방법

일단 맨 처음은 무조건 -1이니깐 -1을 넣고 시작해준다.

그다음에 s 사이즈 만큼 돌리고 현재 위치에서 가장 가까운 원소의 인덱스가 얼마나 차이나는지 봐야하니깐 j를 i-1부터 시작해주었다.

즉 바로 앞에있는 것부터 검사 

그리고 j>=0 이부분이 중요한데 0일 때 까지고 검사해줘야한다.

만약 같으면 i-j를 push_back해주고 answer.size() <i+1 즉 이번 i 값에서 추가된 값이 없다면 -1을 추가하도록 해주었다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    answer.push_back(-1);
    for(int i=1; i<s.size(); i++){
        for(int j=i-1; j>=0; j--){
            if(s[i] == s[j]){
                answer.push_back(i-j);
                break;
            }
            else{
                continue;
            }
            
        }
        if(answer.size()<i+1){
            answer.push_back(-1);
        }
        
    }
    return answer;
}

 

개선점

map 을 이용하면 좀 더 간단하고 효율적인 코드가 될 것 같다.

가장 큰 장점은 시간 복잡도를 줄인다는 것이다.

다른 문제에서도 시간 복잡도가 큰 것들을 map이나 pair를 이용해 줬었는데 이 문제도 map을 이용해 준다면 for문 하나로도 해결가능하다.

map<char, int> mp;
if (mp.find(s[i]) != mp.end()) answer.push_back(i - mp[s[i]]);

(참고 : 프로그래머스 다른 사람 풀이 보기)

 

[프로그래머스/1단계] 가장 가까운 같은 글자 -c++

정답률 71%