[프로그래머스] Lv.1 가장 가까운 같은 글자 c++

https://school.programmers.co.kr/learn/courses/30/lessons/142086

프로그래머스

 

문자열 s가 주어졌을때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶다.

예를 들어, s="banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있다.

 

s[0] = b 처음 나왔으므로 -1

s[1] = a 처음 나왔으므로 -1

s[2] = n 처음 나왔으므로 -1

s[3] = a 두칸 앞에서 이미 나왔으므로 3-1 = 2

s[4] = n 두칸 앞에서 이미 나왔으므로 4-2 = 2

s[5] = a 가장 가까운 a는 두칸 앞의 a므로 5-3 = 2

 

즉, 답은 [-1, -1, -1, 2, 2, 2]

 

문자열 s가 주어졌을때 답을 구해라.

 

풀이 방법

문제는 이전에 등장한 위치를 효율적으로 기록하면서, 가장 가까운 위치를 빠르게 찾는 것이 핵심이다.

이를 위해 HashMap (unordered_map) 자료구조를 사용했다. (사실 최대 26밖에 안되어서 꼭 HashMap을 쓸 필요는 없다..)

1. 문자의 위치 기록:
   • unordered_map<char, int>를 사용하여 각 문자의 마지막 위치를 저장한다.
2. 문자 탐색:
   • 문자열을 처음부터 끝까지 탐색하며, 만약 문자가 처음 등장한 경우 -1을 저장한다.
   • 이미 등장한 경우, 현재 위치에서 저장된 위치를 뺀 값을 저장한다.
3. 위치 갱신:
   • 현재 문자의 위치를 unordered_map에 갱신하여 이후의 탐색에서 사용할 수 있도록 한다.

 

풀이 코드

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

unordered_map<char,int> map;
vector<int> solution(string s) {
    vector<int> answer;
    for(int i=0; i<s.size(); i++){
        if(map.find(s[i]) == map.end()){
            map[s[i]] = i;
            answer.push_back(-1);
        }
        else{
            int position = map[s[i]];
            answer.push_back(i-position);
            map[s[i]] = i;
        }
    }
    return answer;
}