Lv1_[가장 가까운 같은 글자, C++] 풀이 및 알고리즘 정리 - 프로그래머스

 

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

같은 알파벳이 현재 인덱스 이전에 몇번째 인덱스에 있었는지를 알면 두 알파벳 사이의 거리를 알 수 있습니다.

 

예시) banana에서 a의 인덱스를 보면

[0]	[1]	[2]	[3]	[4]	[5]
b	a	n	a	n	a

[1], [3], [5]에 a가 존재하고 서로의 거리는 (3-1) = 2, (5-3) = 2 가 된다.

예시) dashboard에서 a의 인덱스를 보면

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]
d	a	s	h	b	o	a	r	d

[1], [6]에 a가 존재하고 서로의 거리는 (6-1) = 5가 된다.

 

 

- 자료구조

• unordered_map<key, value>
  알파벳별로 인덱스를 저장하기 위해서 사용
  • <key:알파벳, value:인덱스>로 구성 
    • 이전에 알파벳이 있는지 판단가능
    • 인덱스의 크기 비교가 쉬움

map을 사용하지 않고 unordered_map을 사용한건 key이 작을때 검색에 조금 더 빠르기 때문이다.

 

 

알고리즘

 1) s를 인덱스 [0]부터 순차 접근
 2) 알파벳(key)과 인덱스(value)를 unordered_map에 저장하기
   2-1) key가 존재하지 않으면 저장, result는 -1
   2-2) key가 존재하면, 현재 인덱스와 저장된 인덱스의 차이만큼 result에 저장 후, value에 현재 인덱스 저장
 3) s가 end()까지 탐색 후 종료

 

#include <string>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
vector<int> solution(string s) {
    vector<int> answer;
    unordered_map<char, int> umap;
 
    for(int i = 0; i < s.length(); i++) {    // 1)
        if(umap.find(s[i]) != umap.end()) {    // 2-2)
            // 찾음
            int index = umap[s[i]];
            answer.push_back(i - index);
            umap[s[i]] = i;
        } else {                            // 2-1)
            // 못 찾음
            umap[s[i]] = i;
            answer.push_back(-1);
        }
    }
 
    return answer;
}

 

비교용 결과

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓