20.02.12 코딩테스트

꾸준히 풀어오긴했지만 점점 어려워지면서 기록하고 복습할 필요가 있을듯

 

문제는 위와 같음

 

답은 다음과 같이 제출

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

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;
    unordered_map<char, int> last_seen; 

    for (int i = 0; i < s.size(); i++) {
        char c = s[i];

        if (last_seen.find(c) != last_seen.end()) {
            answer.push_back(i - last_seen[c]); 
        } else {
            answer.push_back(-1); 
        }

        last_seen[c] = i; 
    }

    return answer;
}

 

해설에 대한 풀이는 다음과 같음

 

vector<int> solution(string s) {
    vector<int> answer;
    unordered_map<char, int> last_seen;

• answer는 최종 결과를 저장하는 리스트입니다.
• last_seen은 각 문자들이 마지막으로 등장한 위치를 저장하는 자료구조입니다. (딕셔너리처럼 작동)

반복문을 사용하여 문자열을 처리

    for (int i = 0; i < s.size(); i++) {
        char c = s[i];

 

• 문자열 s를 첫 번째 문자부터 마지막 문자까지 하나씩 확인하는 for 문입니다.
• c = s[i]는 s의 i번째 문자를 c라는 변수에 저장하는 코드입니다.

이전 등장 여부 확인

        if (last_seen.find(c) != last_seen.end()) {
            answer.push_back(i - last_seen[c]);
        } else {
            answer.push_back(-1);
        }

 

last_seen.find(c) != last_seen.end()

• c라는 문자가 last_seen에 저장되어 있는지 확인하는 코드입니다.
• 만약 존재하면 → 그 문자가 마지막으로 등장한 위치(last_seen[c])와 현재 위치(i)의 차이를 계산해서 answer에 추가합니다.
• 존재하지 않으면(처음 등장한 문자라면) → -1을 answer에 추가합니다.

현재 문자의 위치 업데이트

        last_seen[c] = i;

 

• last_seen[c] = i; → 현재 문자가 등장한 위치(i)를 last_seen에 저장합니다.
• 이후에 같은 문자가 등장하면, 가장 마지막으로 등장했던 위치와 비교할 수 있습니다.

 

예시로 살펴보겠음

예제 실행 과정 ("banana")

1. 첫 번째 문자 'b'
   • last_seen에 'b'가 없음 → -1 추가
   • last_seen['b'] = 0
   • answer = [-1]
2. 두 번째 문자 'a'
   • last_seen에 'a'가 없음 → -1 추가
   • last_seen['a'] = 1
   • answer = [-1, -1]
3. 세 번째 문자 'n'
   • last_seen에 'n'가 없음 → -1 추가
   • last_seen['n'] = 2
   • answer = [-1, -1, -1]
4. 네 번째 문자 'a'
   • last_seen['a'] = 1 (이전 'a' 위치)
   • 현재 위치 3 - 마지막 위치 1 = 2 → answer에 2 추가
   • last_seen['a'] = 3
   • answer = [-1, -1, -1, 2]
5. 다섯 번째 문자 'n'
   • last_seen['n'] = 2
   • 현재 위치 4 - 마지막 위치 2 = 2 → answer에 2 추가
   • last_seen['n'] = 4
   • answer = [-1, -1, -1, 2, 2]
6. 여섯 번째 문자 'a'
   • last_seen['a'] = 3
   • 현재 위치 5 - 마지막 위치 3 = 2 → answer에 2 추가
   • last_seen['a'] = 5
   • answer = [-1, -1, -1, 2, 2, 2]

중요개념?

1. unordered_map은 무엇인가?

• 키(Key): 특정 값을 찾을 때 사용하는 고유한 식별자 (예: 문자 a, b, c 등)
• 값(Value): 해당 키에 연결된 데이터 (예: 문자 a의 마지막 등장 위치)
• 빠르게 데이터를 저장하고 검색할 수 있음 (O(1))

즉, unordered_map<char, int>은 각 문자(char)를 키로 하고, 그 문자가 마지막으로 등장한 위치(int)를 값으로 저장하는 자료구조입니다.