[프로그래머스] 튜플 (2019 카카오 개발자 겨울 인턴십)-JAVA

[문제 설명]

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

• (a1, a2, a3, ..., an)

튜플은 다음과 같은 성질을 가지고 있습니다.

1. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)
2. 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)
3. 튜플의 원소 개수는 유한합니다.

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

• {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

와 같이 표현할 수 있습니다. 이때, 집합은 원소의 순서가 바뀌어도 상관없으므로

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
• {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
• {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

[제한 사항]

• s의 길이는 5 이상 1,000,000 이하입니다.
• s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.
• 숫자가 0으로 시작하는 경우는 없습니다.
• s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
• s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
• return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.

[풀이]

해당 문제의 Key Point 정규식과 Comparator, 그리고 Set을 사용할 수 있는 활용 여부인 것 같습니다. 그리고 한가지 팁이라면, {}괄호 안에 있는 숫자들의 개수가 작을수록 최종 배열에서 앞에 나오는 수라고 생각하면 편합니다.

 

예를 들어, "{{2},{2,1},{2,1,3},{2,1,3,4}}"이라는 문자열이 주어질 경우 {}안에 개수가 가장 작은 첫번째 괄호의 경우 "2" 하나만 존재합니다. 따라서 최종 결과물의 가장 앞에 위치합니다. 다음으로 크기가 작은 {2,1}에서 중복인 2를 제외한 1은 최종 배열에서 두번째에 위치합니다. 이 같은 과정을 반복하면 결과적으로 최종 결과물은 [2,1,3,4]가 되게 됩니다.  

 

먼저 정규식을 통해 여러 괄호를 제거하고 배열에 저장하는 과정입니다. 

        s = s.substring(2, s.length() - 2).replaceAll("[{]","");
        String[] arr = s.split("},");

코드는 굉장히 짧지만 많은 역할을 하는 코드 두줄입니다. 먼저 첫째줄의 코드는 문자열의 가장 끝 양옆의 "{{" 과 "}}"를 제거합니다. 그리고 replaceAll() 메서드와 정규식을 활용하여 문자열 내에 있는 모든 "{" 문자열을 제거합니다. 만약 s가"{{2},{2,1},{2,1,3},{2,1,3,4}}" 라고 한다면 첫째줄 만으로 s문자열은 다음과 같이 변환됩니다. 

s="{{2},{2,1},{2,1,3},{2,1,3,4}}"

//변환

s="2},2,1},2,1,3},2,1,3,4"

그리고 두번째 줄은 "}," 문자열이 나올때 s문자열을 잘라서 배열화 환다는 의미의 코드입니다. 

String[] arr ={"2","2,1","2,1,3","2,1,3,4"};

문자열 내에 "," 뺴고는 모두 제거된 형태로 배열안에 저장됩니다. 

 

다음은 Comparator의 활용입니다. Comparator은 주로 문자열, 객체 등의 정렬을 위해 사용됩니다. 

       Arrays.sort(arr,new Comparator<String>() {
           @Override
           public int compare(String o1, String o2) {
               return o1.length() - o2.length();
           }
       });

Arrays.sort안에 있는 compare 메소드는 배열의 문자열 두개를 크기를 비교하여 정렬하는 기능을 수행합니다. 만약 return 값이 마이너스 즉, 음수라면 해당 배열은 아무런 변화가 없습니다. 그러나 만약 return이 플러스라면 앞에 있는 문자열이 더 크다는 의미기 때문에 두 문자열의 위치가 변환됩니다. 

 

마지막으로 Set을 활용하여 중복을 제거해 보겠습니다. 

        LinkedHashSet<Integer> set = new LinkedHashSet<>();
        for (int i = 0; i < arr.length; i++) {
            String[] temp = arr[i].split(",");
            for (int j = 0; j < temp.length; j++) {
                set.add(Integer.parseInt(temp[j]));
            }
        }

set 내에 들어오는 값의 순서를 보장해 주는 LinkedHashSet을 활용했습니다. 이전 배열(["2","2,1","2,1,3","2,1,3,4"])에서 각각의 콤마를 기준으로 temp라는 새로운 배열을 생성합니다. 그리고 배열의 크기만큼 각각 숫자들을 set에 추가합니다. 순서가 유지되기 되고 중복은 제거되기 떄문에 set 안에는 2->2,1->2,1,3->2,1,3,4 의 순서로 값이 채워지게 됩니다. 

 

최종 코드입니다.

import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedHashSet;
class Solution {
    public int[] solution(String s) {
        s = s.substring(2, s.length() - 2).replaceAll("[{]","");
        String[] arr = s.split("},");

        Arrays.sort(arr,new Comparator<String>() {
           @Override
           public int compare(String o1, String o2) {
               return o1.length() - o2.length();
           }
        });

        LinkedHashSet<Integer> set = new LinkedHashSet<>();
        for (int i = 0; i < arr.length; i++) {
            String[] temp = arr[i].split(",");
            for (int j = 0; j < temp.length; j++) {
                set.add(Integer.parseInt(temp[j]));
            }
        }
        
        int answer[] = new int[set.size()];
        Iterator it = set.iterator();
        int count=0;
        while(it.hasNext()){
            answer[count++] = (int)it.next();
        }
        return answer;
    }
}