[Programmers] #120888 - 중복된 문자 제거 [Java][C++][Python]

문제 링크

---

1. 아이디어

문자를 앞에서부터 훑으면서 처음 보는 문자만 결과 문자열에 붙이고, 이미 나온 문자는 건너뛴다. 어떤 문자가 이미 나왔는지는 집합으로 판별한다. 결과를 원본 순서대로 이어 붙이므로 첫 등장만 남고 이후 중복은 자연히 빠진다.

---

2. 복잡도

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

($N$ = my_string의 길이)

---

3. 코드

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

import java.util.*;

class Solution {
    public String solution(String my_string) {
        StringBuilder sb = new StringBuilder();
        Set<Character> set = new LinkedHashSet<>();

        for (char c : my_string.toCharArray()) {
            if (set.add(c)) sb.append(c);
        }

        return sb.toString();
    }
}

LinkedHashSet는 원소가 삽입된 순서를 유지한다. set.add(c)는 c가 처음 들어갈 때만 true를 반환하므로, if (set.add(c))로 중복 판별과 삽입을 한 번에 처리하면서 처음 보는 문자일 때만 sb에 붙였다.

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

string solution(string my_string) {
    string s;
    set<char> st;

    for (char c : my_string) {
        if (st.count(c)) continue;
        s += c;
        st.insert(c);
    }

    return s;
}

def solution(my_string):
    return "".join(dict.fromkeys(my_string))

dict.fromkeys(my_string)는 문자열의 각 문자를 키로 하는 딕셔너리를 만든다. 딕셔너리 키는 중복되지 않고 삽입 순서를 유지하므로, 같은 문자는 첫 등장 자리에 하나만 남는다. 이 키들을 "".join으로 이어 붙여 결과 문자열을 얻었다.

---