[PS] PCCP 모의고사 1회 - 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 ≤ input_string의 길이 ≤ 2,600
• input_string은 알파벳 소문자로만 구성되어 있습니다..

---

입출력 예

input_stringresult

"edeaaabbccd"	"de"
"eeddee"	"e"
"string"	"N"
"zbzbz"	"bz"

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.
• 외톨이 알파벳인 e, d를 알파벳순으로 이어 붙여 문자열을 만들면 "de"가 됩니다.

입출력 예 #2

• 문제 예시와 같습니다.

입출력 예 #3

• 모든 문자들이 한 번씩만 등장하므로 외톨이 알파벳이 없습니다.

입출력 예 #4

• 외톨이 알파벳인 z, b를 알파벳순으로 이어 붙여 문자열을 만들면 "bz"가 됩니다.

풀이

aabbbbcca와 같은 알파벳이 있을 때, 마지막 a처럼 덩어리에서 떨어진 알파벳을 찾는 문제이다.

이 문제를 풀기 위해서는 먼저 "덩어리"와 "덩어리에서 떨어진 것"을 정의해야 한다.

 

덩어리 & 덩어리에서 떨어진 것

덩어리
- 2회 이상 나타날 것
- 알파벳 간의 거리가 1일 것 (연속해서 뭉쳐있을 것)

덩어리에서 떨어진 것
- 2회 이상 나타날 것
- 알파벳 간의 거리가 1보다 클 것 (연속해서 뭉쳐있지 않을 것)

나는 여기서 입력받는 string을 배열로 생각하고, 알파벳들의 위치를 인덱스로 추적했다.

 

덩어리가 아닌 것 찾기

aabbcca 의 경우

- a의 위치: 0, 1, 6

- b의 위치: 2, 3

- c의 위치: 4, 5

 

여기서 a는 0, 1 까진 괜찮지만 1과 6은 사이의 거리가 5이므로 덩어리에서 떨어져있다.

즉, 이 경우가 외톨이 알파벳인 것이다!

 

반면 b와 c의 경우에는 2, 3과 4, 5로 연속하는 숫자로 잘 붙여있는 것을 알 수 있다.

이 논리대로 코드를 작성하면 쉽게 풀 수 있다.

 

주의할 점

덩어리가 아닌, 외톨이 알파벳의 경우에도 1개가 있는 경우는 카운트하지 않는다는 것을 주의한다.

 

코드

#include <string>
#include <vector>
#include <map>

using namespace std;

string solution(string input_string) {
    string answer = "";
    map<char, vector<int>> map;
    
    for (int i = 0; i < input_string.size(); i++) map[input_string[i]].push_back(i);
    
    for (const auto& pair : map) {
         
        int prevIndex = -1;
        int nextIndex = -1;
        int cnt = 0;
        for (auto index : pair.second){
            nextIndex = index;
            int size = pair.second.size();
                
            if (size == 1) break;
            
            if (prevIndex == -1){
                prevIndex = index;
                continue;
            }
            
            if (prevIndex + 1 != nextIndex){
                answer.push_back(pair.first);
                break;
            }
            
            prevIndex = nextIndex;
        }
    }
    
    if (answer == "") return "N";
    
    return answer;
}

 

회고

쉬운 문제였지만 1시간이나 걸렸다...

생각하는 시간을 좀 줄이고 먼저 구현해나가면서 풀이 시간을 줄여야 할 것 같다.