[프로그래머스] 외톨이 알파벳(PCCP 모의고사 #1 1번)

https://school.programmers.co.kr/learn/courses/15008/lessons/121683

프로그래머스

프로그래머스 - 외톨이 알파벳(PCCP 모의고사 #1 1번)

문제 유형 : 문자열 처리, 해시

문제 난이도 : Level 1(개인적인 체감)

 

문제 설명

알파벳 소문자로만 이루어진 어떤 문자열에서, 2회 이상 나타난 알파벳이 2개 이상의 부분으로 나뉘어 있으면 외톨이 알파벳이라고 정의합니다.

문자열 "edeaaabbccd"를 예시로 들어보면,

• a는 2회 이상 나타나지만, 하나의 덩어리로 뭉쳐있으므로 외톨이 알파벳이 아닙니다.
  • "ede(aaa)bbccd"
• b, c도 a와 같은 이유로 외톨이 알파벳이 아닙니다.
• d는 2회 나타나면서, 2개의 부분으로 나뉘어 있으므로 외톨이 알파벳입니다.
  • "e(d)eaaabbcc(d)"
• e도 d와 같은 이유로 외톨이 알파벳입니다.

문자열 "eeddee"를 예시로 들어보면,

• e는 4회 나타나면서, 2개의 부분으로 나뉘어 있으므로 외톨이 알파벳입니다.
  • "(ee)dd(ee)"
• d는 2회 나타나지만, 하나의 덩어리로 뭉쳐있으므로 외톨이 알파벳이 아닙니다.
  • "ee(dd)ee"

문자열 input_string이 주어졌을 때, 외톨이 알파벳들을 알파벳순으로 이어 붙인 문자열을 return 하도록 solution 함수를 완성해주세요. 만약, 외톨이 알파벳이 없다면 문자열 "N"을 return 합니다.

 

 

풀이

문자열을 1회 순회하면서, 각 문자들이 등장한 인덱스를 저장합니다.

key-value형식으로 문자열 - 등장한 인덱스를 저장시킵니다.

각 map의 요소들을 확인하면서 만약 2개 이상 등장하고, 이들이 인접한 관계가 아니라면 외톨이 알파벳이므로 정답 문자열에 추가합니다.

정답 문자열을 정렬시켜서 반환하고, 비어있다면 "N"을 반환합니다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

string solution(string input_string) {
    const int n = input_string.size();
    unordered_map<char, vector<int>> um;
    string answer = "";
    
    for(int i = 0; i < n; i++) {
        um[input_string[i]].push_back(i);
    }
    
    for(const auto &map : um) {
        char ch = map.first;
        auto indexes = map.second;
        int groups = 1;
        if(indexes.size() == 1) continue;
        for(int i = 1; i < indexes.size(); i++) {
            if(indexes[i] -1 != indexes[i-1]) groups++;
        }
        if(groups > 1) answer += ch;
    }
    
    sort(answer.begin(), answer.end());
    
    return answer.size() == 0? "N" : answer;
}

hash table

<컴퓨터>해시표(~表)