프로그래머스 - 한 번만 등장한 문자

나의 풀이.

이전에 해시맵 공부하면서 풀어본 문제인데 정리겸 다시 한번 작성하려 한다.
해당 문제를 3가지 방법으로 풀어보고 해당 방법에 따른 실행결과도 한 번 비교해보자.
1. 해시맵/해시테이블로 풀기
2. 계수 정렬 방법으로 풀기
3. 중복값이 없고 순서가 있는 TreeSet으로 풀기

 

1. 해시맵/해시테이블
getOrDefault 메서드를 사용해 문자열을 하나씩 분리하고 key 값으로 매핑하여
value값을 증가시켜준다.
그리고 keySet() 을 돌려 해당 key의 value가 1이면 StringBuilder에 더해주고
이 StringBuilder 를 문자열로 만들어서 다시 배열로 만들어서 sort 해주고
다시 문자열로 반환하기

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.TreeSet;

class Solution {
    public String solution(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();

        for (char ch : s.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
                
        for (char key : map.keySet()) {
            if (map.get(key) == 1) {
                sb.append(key);
            }
        }
        
        String result = sb.toString();
        char[] answer = result.toCharArray();
        Arrays.sort(answer);
        return String.valueOf(answer);
    }
}

2. 계수 정렬 방법으로 풀기
계수 정렬 : 원소들의 개수를 세어서 정렬하는 알고리즘
알파벳 소문자 입력만 들어오니 알파벳 26자리의 int 배열을 만들고
입력받은 s 문자열을 하나씩 나눠 'a' 를 0으로 잡고 해당 알파벳이면 인덱스++
for 루프에서 cntArr 배열을 순회하면서 등장 횟수가 1인 문자를 sb에 추가하고,
마지막으로 sb를 문자열로 변환하여 반환, 이러면 사전순으로 sort 안해줘도 됨
알고리즘 복잡도 : O(n + k) - k는 정렬 대상 데이터 중 최대값, 이 문제에서는 'z'의 위치 26

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.TreeSet;

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

        for (int i = 0; i < cntArr.length; i++) {
            if (cntArr[i] == 1) {
                sb.append((char) ('a' + i));
            }
        }
        
        return sb.toString();
    }
}

 

3. TreeSet으로 풀기

// TreeSet의 특징
정렬된 순서로 원소를 저장: TreeSet에 원소를 추가할 때, 
내부적으로 이진 검색 트리의 특성을 이용하여 원소들을 정렬된 순서로 저장합니다. 
이진 검색 트리의 노드는 왼쪽에는 작은 값, 오른쪽에는 큰 값이 위치하도록 구성됩니다.

중복 원소 제거: TreeSet은 중복된 원소를 허용하지 않습니다. 
새로운 원소가 추가될 때 이미 존재하는 원소인 경우 무시됩니다.

빠른 탐색 시간복잡도: TreeSet은 이진 검색 트리의 특성을 활용하여 
원소를 검색하는 데에 빠른 시간복잡도를 가지며, 
대부분의 연산(추가, 삭제, 검색)에 대해 O(logN)의 시간복잡도를 가집니다.

두 개의 TreeSet을 만들고 하나는 add할 수 있는 TreeSet, 하나는 add할 수 없는 TreeSet 두개를 만든다.
반복문을 돌며 위의 조건에 맞게 각 각의 TreeSet에 데이터를 삽입해 주고 한 번만 나온 알파벳이니
add할 수 있는 TreeSet에서 add할 수 없는 TreeSet의 데이터를 삭제해준다.
그럼 add할 수 있는 TreeSet에는 한 번만 나온 알파벳이 사전순으로 나열되어 있다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.TreeSet;

class Solution {
    public String solution(String s) {
        StringBuilder sb = new StringBuilder();
        TreeSet<Character> onceCharacter = new TreeSet<>();
        TreeSet<Character> overCharacter = new TreeSet<>();
        
        for (char ch : s.toCharArray()) {
            if (!onceCharacter.add(ch)) {
                overCharacter.add(ch);
            }
        }
        
        onceCharacter.removeAll(overCharacter);
        for (char ch : onceCharacter) {
            sb.append(ch);
        }
        
        return sb.toString();
    }
}

 

정리.

3가지 방법 중에서 계수정렬이 빠른거 처럼 보이나
최대 값이 엄청 큰 경우에는 HashMap, TreeSet 보다 시간복잡도가 오히려 안좋고
공간복잡도도 최대값 만큼 메모리가 필요하기 때문에 해시맵 보다 더 큰걸 확인할 수 있다.
트리셋은 걍 이런방법도 있네 정도로 이해하자..
경우와 상황에 맞게 적용할 수 있게 공부하고 또 공부하즈아ㅏㅏㅏㅏㅏㅏㅏㅏㅏ
끗.

 

---

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/120896?language=java