[Programmers] #120896 - 한 번만 등장한 문자 [Java][C++][Python]

문제 링크

---

1. 아이디어

문자열 s에 대해 각 알파벳이 몇 번 나오는지 센 다음, 등장 횟수가 정확히 1인 문자만 사전 순으로 모으면 된다. 입력이 소문자로만 이루어지므로 크기 26짜리 카운팅 배열을 활용해서 a부터 z까지 순서대로 확인하면 별도의 정렬 없이도 사전 순으로 결과를 만들 수 있다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(1)$

($N$ = s의 길이. 카운팅과 결과가 모두 소문자 26종에 묶여 s 길이와 무관하게 상수 공간)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public String solution(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (cnt[i] == 1) sb.append((char) (i + 'a'));
        }

        return sb.toString();
    }
}

#include <bits/stdc++.h>
using namespace std;

int cnt[26];

string solution(string s) {
    for (char c : s) cnt[c - 'a']++;

    string ans;
    for (int i = 0; i < 26; i++) {
        if (cnt[i] == 1) ans += i + 'a';
    }

    return ans;
}

from collections import Counter


def solution(s):
    cnt = Counter(s)
    return "".join(sorted(k for k, v in cnt.items() if v == 1))

Counter로 문자별 등장 횟수를 센 뒤, 값이 1인 문자만 골라 sorted로 사전 순 정렬하고 join으로 이어붙였다. Counter는 등장 순서를 유지하므로 사전 순 정렬은 따로 해야 한다.

---