Lv 0. 한 번만 등장한 문자.

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

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int a[200];

string solution(string s) {
    string answer = "";
    cout<<int('a')<<' '<<int('z');
    for(auto c:s){
        a[int(c)]++;
    }
    for(int i=97;i<=122;i++){
        if(a[i]!=1) continue;
        answer+=char(i);
    }
    return answer;
}

 

배열을 따로 선언해서, 해당 문자가 등장한 횟수를 카운트 하고, 해당 문자가 등장한 횟수가 1회라면 answer에 해당 문자를 추가하는 형태로 코드를 작성했다. 

아스키코드 상에서 소문자가 몇번부터 몇번인지 (97번부터 122번) 정확히 기억하지 못하고 있는 상황이라 iostream 헤더를 추가해서 cout으로 int로 캐스팅한 char의 숫자들을 출력해서 범위를 알아내고, 해당 범위에서의 배열들의 값을 for문에 활용하였다. 

 

다른 사람의 풀이를 보니까, map을 활용한 풀이들이 많은것 같다. 

#include <string>
#include <vector>
#include <map>
using namespace std;

string solution(string s) {
    string answer = "";

    map<char,int> m;
    for(const auto v : s)
        m[v]++;
    for(const auto& v : m)
        if(v.second == 1)
            answer.push_back(v.first);
    return answer;
}

위와 같은 형태로, map을 활용해서 문제를 푸는것도 꽤나 깔끔한 풀이 방법이라는 생각이 든다. 

 

이때에 unorderd_map과 map이 있는데, map을 사용하는 이유에 대해서 , 그리고 그 둘의 차이에 대해서 검색해보면, 

 

`map` 대신 `unordered_map`을 사용하는 것은 특정 상황에 따라 선택하는 것이며, 두 컨테이너 모두 키-값 쌍을
저장하는 목적으로 사용됩니다. 풀이에 `map`을 사용하는 이유는 다음과 같을 수 있습니다:

1. **순서가 중요한 경우:** 풀이에서는 문자열 `s`에서 처음으로 나타나는 유일한 문자를 찾아야 합니다. 이런 
경우에는 문자가 처음 나타난 순서가 중요하며, `map`은 키를 기반으로 정렬된 순서로 요소를 저장하므로 문자의 등장 
순서를 보존하기 쉽습니다.

2. **해시 함수 작성의 복잡성 회피:** `unordered_map`을 사용할 때, 사용자 정의 타입에 대한 해시 함수를
작성해야 할 수 있습니다. 문자열과 같은 기본 데이터 타입을 다루는 경우, 이러한 복잡성을 회피할 수 있습니다.

3. **코드의 간결성:** `map`은 정렬된 순서를 보존하기 때문에 추가적인 정렬 작업 없이도 원하는 결과를 얻을 수
있습니다. `unordered_map`을 사용하려면 결과를 다시 정렬해야 할 수 있습니다.

단순히 문자의 출현 빈도를 기록하고, 그 순서가 중요하지 않은 경우에는 `unordered_map`을 사용하는 것이 
메모리와 검색/삽입 시간면에서 더 효율적일 수 있습니다. 그러나 문자열에서 유일한 문자를 찾는 경우처럼 순서가 
중요하거나 복잡한 해시 함수를 구현하기 어려운 경우에는 `map`을 사용하는 것이 간단하고 효과적일 수 있습니다.

C++에서 `unordered_map`과 `map`은 둘 다 키-값(key-value) 쌍을 저장하는 연관 컨테이너입니다. 그러나 
두 컨테이너 간에는 중요한 차이점이 있습니다:

1. **정렬 여부:**
    - `map`: 키(key)를 기반으로 정렬된 순서로 요소를 저장합니다. 이는 키의 순서에 의해 요소에 접근할 때 
    일정한 순서를 보장합니다. 기본적으로 오름차순으로 정렬됩니다.
    - `unordered_map`: 요소들은 해시 함수를 기반으로 저장되며, 키의 순서가 보장되지 않습니다. 따라서 
    요소에 순서대로 접근하는 것은 보장되지 않습니다.

2. **검색 및 삽입 시간복잡도:**
    - `map`: 키-값 쌍을 검색할 때 `O(log n)` 시간이 걸립니다. 즉, 이진 검색 트리(binary search tree)
    로 구현되어 있어 빠르고 안정적인 검색이 가능합니다.
    - `unordered_map`: 해시 테이블을 사용하므로 키-값 쌍의 검색 및 삽입 시간복잡도는 평균적으로 `O(1)`입니다. 
    그러나 최악의 경우 해시 충돌이 발생할 수 있어 `O(n)`까지 늘어날 수 있습니다.

3. **메모리 사용:**
    - `map`: 추가적인 정렬 정보를 저장하기 위한 메모리를 사용하므로, 일반적으로 `unordered_map`에 비해 더 많은
    메모리를 소비합니다.
    - `unordered_map`: 정렬 정보를 저장하지 않기 때문에 메모리 사용이 더 효율적입니다.

4. **반복(iteration) 순서:**
    - `map`: 요소들은 키의 순서대로 정렬되어 있으므로 반복(iteration)을 수행할 때 키 순서대로 순회합니다.
    - `unordered_map`: 요소들은 키의 해시값에 따라 저장되므로 순회 순서는 예측하기 어렵습니다.

5. **해시 함수 요구사항:**
    - `unordered_map`은 해시 함수를 요구합니다. 사용자 정의 타입에 대한 해시 함수를 제공해야 할 수 있습니다.
    - `map`은 키 타입에 대한 비교 연산자(`<`, `==` 등)만 필요하며 해시 함수를 요구하지 않습니다.

어떤 컨테이너를 선택할 것인지는 사용 사례에 따라 다릅니다. 정렬된 순서가 필요하거나 메모리 사용에 크게 신경을 쓰지 않아도
 되는 경우 `map`을 사용할 수 있고, 빠른 검색과 삽입이 중요한 경우 `unordered_map`을 고려할 수 있습니다.

 

추가적으로 이 문제의 풀이에, map을 사용하지 않고 내가 사용한 방법처럼 문제를 풀이하되, 조금 더 깔끔해 보이는 풀이를 첨부해보면, 

#include <string>
#include <vector>

using namespace std;

string solution(string s) {
    int alphabet[27] = {0};
    string answer = "";

    for(int i = 0; i < s.size(); i++)
    {
        alphabet[s[i] - 'a']++;
    }

    for(int i = 0; i < 26; i++)
    {
        if(alphabet[i] == 1) answer += char('a' + i);
    }

    return answer;
}

위와 같은 형태처럼 배열의 갯수를 알파벳의 갯수만큼 선언해서 사용하는 방법이 조금 더 깔끔해 보이긴 한다. 

혹은 아래 첨부하는 코드처럼 벡터를 선언해도 되고. 

#include <string>
#include <vector>

using namespace std;

string solution(string s) {
    string answer = "";
    vector<int> count(26,0);
    for(int i=0; i<s.length(); i++) {
        char c = s[i];
        count[(int)c - 97]++;
    }
    for(int i=0; i<26; i++) {
        if(count[i] == 1) {
            answer += (char)(i + 97);
        }
    }
    return answer;
}

 

둘다 내가 풀이한 방법처럼 int a[200] 처럼 넉잡아서 하지 않고, 27개의 알파벳을 고려해서 적게 선언하는데, 이렇게 선언하는것이 조금 더 깔끔해 보이는 느낌이다. 하지만 내 풀이 또한 크게 차이는 없으니 취사선택 하도록 하자.