[프로그래머스] 255900 외톨이 알파벳 - JAVA - PCCP 모의고사

[프로그래머스] 255900 외톨이 알파벳 - JAVA - PCCP 모의고사

문제

https://school.programmers.co.kr/learn/courses/20847/lessons/255900

프로그래머스

문제 분석

조건

• 같은 알파벳이 여러 번 등장하되, 중간에 다른 문자가 끼어 그룹이 나뉘면 외톨이 알파벳이다.
• 모든 외톨이 알파벳을 찾아 오름차순 정렬 후 문자열로 반환한다.
• 없다면 "N"을 반환한다.

풀이방법

• 입력 문자열을 앞에서부터 하나씩 확인하며, 각 알파벳이 처음 등장한 것인지 확인하기 위해 `boolean[] visited` 배열을 사용한다.
  • 처음 나온 알파벳이면 `visited[알파벳] = true`로 표시하고 넘어간다.
  • 이미 나온 알파벳이라면, 바로 이전 문자와 다를 경우 → 같은 문자가 여러 덩어리로 나뉘어 등장한 것이므로, 해당 문자를 `Set`에 저장. (`Set`은 중복 제거에 사용)
• 모든 문자를 확인한 후, `Set`에 담긴 외톨이 알파벳들을 `List`로 변환하고 정렬하여 문자열로 이어 붙여 반환.
• 만약 `Set`에 아무것도 없으면 `"N"`을 반환한다.  

+

• 내일이 PCCP 보는날이라 모의고사 풀기.... 모의고사라 1시간 이상 생각하고 문제를 풀기 시작했는데 생각보다 쉬웠다. 실전엔 이렇게 안 나올 거면서..
• 처음에는 중복 체크와 정렬 처리를 간편하게 하기 위해 Set을 사용했다.
  HashSet은 중복을 자동으로 제거해 주기 때문에 구현이 간단하고 깔끔했다.
  하지만 정답 출력을 위해 List로 변환하고 정렬하는 과정에서 불필요한 연산이 추가된다.
  알파벳은 26개로 제한되어 있으므로, boolean[] 배열을 활용하면 정렬 없이 순서대로 순회하면서 바로 출력할 수 있다.
• 최종 시간복잡도는 
  • Set을 사용할 경우 O(n + k log k)
  • 배열을 사용할 경우 O(n)으로, 더 효율적인 풀이가 된다.
• 구현 편의성은 Set이 좋지만, 문자 종류가 제한된 경우에는 배열 기반 풀이가 성능 면에서 유리하다는 점을 체감했다.
  
  • Set > List로 변환하고 정렬하는 시간을 감소시키기 때문이겠지
• 그리고 외톨이 알파벳의 존재 여부를 판단하는 용도로 `StringBuilder answer`의 `null` 여부를 사용하는 방식을 사용했는데 이는 기능과 의미가 어긋난 구조라고 생각한다. 성능면에서는 큰 차이가 없지만 flag 변수를 하나 더 두는 것이 가독성 면에서 더 좋으니 유지보수가 좋은 코드라고 볼 수 있을 것 같다. 또한 해당 문제에선 고작 26개인 알파벳이라는 전제이기에 영향은 거의 없다지만 문자열이 커진다면 불필요하게 객체를 여러 번 새로 만들고 버리게 되므로 GC에 문제가 생길 수도 있다고 하니 변수를 하나 더 만들자.

 

코드

import java.util.*;

class Solution {	// Set사용.
    public String solution(String input_string) {
        StringBuilder answer = new StringBuilder();
        Set<Character> answerSet = new HashSet<>();
        int length = input_string.length();
        boolean[] visited = new boolean[26];
        for (int i = 0; i < length; i++) {
            int alpha = input_string.charAt(i) - 'a';
            if (visited[alpha]) {
                if (input_string.charAt(i - 1) - 'a' != alpha) {
                    answerSet.add(input_string.charAt(i));
                }
            } else {
                visited[alpha] = true;
            }
        }
        if (answerSet.size() == 0) {
            return "N";
        }
        List<Character> anserList = new ArrayList<>(answerSet);
        Collections.sort(anserList);
        for (Character character : anserList) {
            answer.append(character);
        }
        return answer.toString();
    }
}

import java.util.*;

class Solution {	//배열 사용
    public String solution(String input_string) {
        StringBuilder answer = null;
        int length = input_string.length();
        boolean[] answerCheck = new boolean[26];
        boolean[] visited = new boolean[26];
        for (int i = 0; i < length; i++) {
            int alpha = input_string.charAt(i) - 'a';
            if (visited[alpha]) {
                if (input_string.charAt(i - 1) - 'a' != alpha) {
                    answer = new StringBuilder();
                    answerCheck[alpha] = true;
                }
            } else {
                visited[alpha] = true;
            }
        }
        if (answer == null) {
            return "N";
        }
        for (int i = 0; i < 26; i++) {
            if (answerCheck[i]) {
                answer.append(Character.toString('a' + i));
            }
        }
        return answer.toString();
    }
}

결과

왼) Set 사용 / 오) 배열 사용