문제

https://school.programmers.co.kr/learn/courses/30/lessons/64065

---

입력

String 형태의 문자열
예시

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

---

출력

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return

---

풀이

제한조건

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

접근방법

문제를 풀기위한 단서들을 우선 정리해보자.

1. 입력으로 주어지는 원소에는 중복이 없다.
2. 각 집합의 원소의 순서가 바뀌어 있을 수 있다.
3. 입력이 불친절하여 직접 파싱해서 써야한다.

우선 입력이 불친절한 문제부터 해결해보자.
"{{4,2,3},{3},{2,3,4,1},{2,3}}"와 같은 입력이 주어진다.
문제를 풀기위해 필요한 데이터는 아래와 같이 각 집합 별 데이터이다.

4,2,3
3
2,3,4,1
2,3

그리고 문제에서 주어진 내용을 보면 원본 튜플을 아래와 같이 표현가능하다.{{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

즉 원소의 갯수가 작은것부터 나열하였을때, 새롭게 추가되는것들이 그 다음 항목인 것이다.

그럼 위에서 구한 데이터를 길이순으로 다시 정렬해보자.

3
2,3
4,2,3
2,3,4,1

처음 원소는 3이다.
두번째 원소의 경우, 첫번째에 없으나 두번째에 추가된 2이다.
이런식으로 계속하여 N까지 확장해나간다.

---

코드

import java.util.*;

class Solution {
    public int[] solution(String s) {
        List<Integer> list = new ArrayList();
        List<String> data = new ArrayList();
        
        // 먼저 필요한 부분집합을 먼저 구한다.
        int size = s.length();
        StringBuilder sb = new StringBuilder();
        boolean flag = false;
        for(int i = 1 ; i < size-1; ++i){
            char c = s.charAt(i);
            if(c == '{'){
                flag = true;
            }else if(c == '}'){
                flag = false;
                data.add(sb.toString());
                sb.setLength(0);
            }else{
                if(flag){
                    sb.append(c);
                }
            }
        }
        
        // 입력에서 파싱이 완료되었다. 길이순으로 정렬하자.
        Collections.sort(data, (o1, o2)-> {return o1.length()-o2.length();});
        
        // 이제 각 집합을 순회하며, 새로 추가된 원소들을 정답 배열에 넣자.
        boolean[] arr = new boolean[100001];
        for(String str : data){
            String[] splitedLine = str.split(",");
            for(String numberString : splitedLine){
                int num = Integer.parseInt(numberString);
                if(!arr[num]){
                    list.add(num);
                    arr[num] = true;
                }
            }
        }
        
        // 반환은 int[] 타입이다.
        return list.stream()
                .mapToInt(i -> i)
                .toArray();
    }
}