프로그래머스 pccp 모의고사 1회 1번 - 외톨이 알파벳

문제설명

알파벳 소문자로만 이루어진 어떤 문자열에서, 2회 이상 나타난 알파벳이 2개 이상의 부분으로 나뉘어 있으면 외톨이 알파벳이라고 정의합니다.

문자열 "edeaaabbccd"를 예시로 들어보면,

• a는 2회 이상 나타나지만, 하나의 덩어리로 뭉쳐있으므로 외톨이 알파벳이 아닙니다.
  - "ede(aaa)bbccd"
• b, c도 a와 같은 이유로 외톨이 알파벳이 아닙니다.
• d는 2회 나타나면서, 2개의 부분으로 나뉘어 있으므로 외톨이 알파벳입니다.
• "e(d)eaaabbcc(d)"
  - e도 d와 같은 이유로 외톨이 알파벳입니다.

문자열 "eeddee"를 예시로 들어보면,

• e는 4회 나타나면서, 2개의 부분으로 나뉘어 있으므로 외톨이 알파벳입니다.
  - "(ee)dd(ee)"
• d는 2회 나타나지만, 하나의 덩어리로 뭉쳐있으므로 외톨이 알파벳이 아닙니다.
  - "ee(dd)ee"

문자열 input_string이 주어졌을 때, 외톨이 알파벳들을 알파벳순으로 이어 붙인 문자열을 return 하도록 solution 함수를 완성해주세요. 만약, 외톨이 알파벳이 없다면 문자열 "N"을 return 합니다.

제한 사항

• 1 ≤ input_string의 길이 ≤ 2,600

• input_string은 알파벳 소문자로만 구성되어 있습니다..

입출력 예

input_string
"edeaaabbccd"
"eeddee"
"string"
"zbzbz"

result
"de"
"e"
"N"
"bz"

문제풀이

1. input을 돌면서 이전값과 비교했을 때 똑같은 값이면 계속 나아간다.

2. 나아가다가 다른 값이 나오게 된다면 그 값을 또 측정한다.

3. 나왔던 알파벳을 따로 저장해두면서 다른 값이 나왔을 때 따로 저장된 곳에 들어가 있으면 result에 넣는다.

4. result를 정렬해서 string 타입으로 출력한다.

풀이 방법

1. 나왔던 알파벳들을 저장하기 위한 input을 list로 설정한다.

2. 띄워져서 나온 알파벳을 저장하기 위한 TreeSet을 설정한다.

3. 처음 값을 ' '로 설정한다.

4. for문을 돌며 input_String을 하나하나 탐색한다.

5. 탐색하며 전 값과 동일 하면 아무 작업도 안한다.

6. 전 값과 다르면 input에 add를 하는데 만약 이미 input에 있다면 result에 add한다.

7. result에 계속 add해도 set이므로 중복 값은 허용되지 않아서 하나의 값만 들어간다.

8. treeset이므로 따로 sort하지 않아도 정렬이 되어서 나온다.

9. 정렬된 값을 string으로 출력

첫번째 풀이

import java.util.*;
class Solution {
    public String solution(String input_string) {
        List<Character> input = new ArrayList<>();
        List<Character> result = new ArrayList<>();
        String answer = "";
        char a = ' ';
        for(int i = 0; i < input_string.length(); i++){
            if(input_string.charAt(i) != a){
                if(input.contains(input_string.charAt(i)) && !result.contains(input_string.charAt(i))){
                    result.add(input_string.charAt(i));
                }else{
                    input.add(input_string.charAt(i));
                }
            }
            a = input_string.charAt(i);
        }
        Collections.sort(result);
        for(int j = 0; j < result.size(); j++){
            answer += result.get(j);
        }
        if(answer == ""){
            answer = "N";
        }
        return answer;
    }
}

• 다음과 같은 코드로 풀었을 땐, input에 값이 들어있으면 result에 똑같은 값이 추가되어서 따로 if문안에 AND를 통해 두개의 조건을 넣어야 했다.
• 또한, 따로 result를 sort를 통해서 정렬을 했어야했다.
• 이러한 문제를 해결하기 위해서 굳이 저 두 문장을 안쓰고 중복된 값을 없애며 바로 정렬하는 함수를 사용할 수 없을까라고 생각을 했다.
• 그래서 TreeSet을 생각하기로 했다.
• TreeSet은 Set으로 중복도 막아주며 Tree를 통해 add하면서 정렬이 자동적으로 이루어진다.

두번째 풀이

import java.util.*;
class Solution {
    public String solution(String input_string) {
        List<Character> input = new ArrayList<>();
        Set<Character> result = new TreeSet<>();
        String answer = "";
        char a = ' ';
        for(int i = 0; i < input_string.length(); i++){
            if(input_string.charAt(i) != a){
                if(input.contains(input_string.charAt(i))){
                    result.add(input_string.charAt(i));
                }else{
                    input.add(input_string.charAt(i));
                }
            }
            a = input_string.charAt(i);
        }
        for(Character b : result){
            answer += b;
        }
        if(answer == ""){
            answer = "N";
        }
        return answer;
    }
}

배운점

• 사실 아직 효율성을 따지는데 어려움이 발생하는 것 같기도하다.
• Java의 List의 contains 메서드는 주어진 요소가 리스트에 포함되어 있는지 확인하기 위해서는 리스트를 순회해야 하므로 시간 복잡도가 O(n)이다.
• 따라서 리스트가 큰 경우에는 성능 문제가 발생할 수 있다.
• 최대한 효율성도 따지면서 코딩을 풀어나가보자...

문제풀이 주소https://school.programmers.co.kr/learn/courses/15008/lessons/121683