링크

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

1. 시간

테스트 1 〉	통과 (0.73ms, 82MB)
테스트 2 〉	통과 (0.63ms, 77.6MB)
테스트 3 〉	통과 (0.65ms, 96.5MB)
테스트 4 〉	통과 (1.14ms, 84.6MB)
테스트 5 〉	통과 (2.64ms, 78.7MB)
테스트 6 〉	통과 (3.85ms, 82.3MB)
테스트 7 〉	통과 (31.52ms, 76.7MB)
테스트 8 〉	통과 (49.23ms, 90.2MB)
테스트 9 〉	통과 (51.67ms, 101MB)
테스트 10 〉	통과 (62.25ms, 87.4MB)
테스트 11 〉	통과 (68.06ms, 94.6MB)
테스트 12 〉	통과 (97.66ms, 100MB)
테스트 13 〉	통과 (101.94ms, 126MB)
테스트 14 〉	통과 (94.41ms, 117MB)
테스트 15 〉	통과 (0.61ms, 75.5MB)

2. 풀이

카카오 문제는 입력부터가 쉽지 않다. 일단 입력 부분에서 한번 꼬는 건 기본인 것 같다.

입력 예시: "{{2},{2,1},{2,1,3},{2,1,3,4}}”

일단 고려할 사항

1. 로직
2. 입력

로직

로직은 쉬웠다. 각 괄호 안의 숫자들의 개수에 따라 정렬하고, 순차적으로 탐색한다.

없는 원소일 경우 그 원소의 다음 번호를 부여하면 되는 방식이다.

예를 들어, 입력이 이렇게 있을 경우

튜플이 (3,2,4,1)이다.

그 이유는,

이기 때문에, {3}이 있으므로 3이 튜플의 가장 첫번째 원소여야 한다. 그 다음 {2,3}에서 3은 이미 첫번째 원소이기 때문에 2는 2번째 원소가 된다. 즉, 집합의 길이별 오름차순 정렬을 먼저 해주고, 각 집합의 원소 중 번호가 부여 안된 원소가 있다면 번호를 부여하면 된다. (번호가 몇번째 원소인지)

이건 HashMap으로 처리해줬다.

입력

솔직히 입력 어떻게 해야하는지 생각한게 더 오래 걸렸다.

split으로 하려고 했는데, 집합 안에도 ,가 있어서 제대로 안나올 것 같았다.

그래서 스택으로 괄호 문제 했던 것처럼,

입력을 순차 탐색해서

1. {가 나올 경우, 집합의 원소를 담을 ArrayList 생성
2. }가 나올 경우, ArrayList를 저장
3. ,가 나올 경우, 앞의 문자를 숫자로 변환해 ArrayList에 저장
4. 숫자가 나올 경우, StringBuilder에 추가

3. 코드

⭕ 정답

import java.util.*;

class Solution {
    
    ArrayList<ArrayList<Integer>> infos;
    ArrayList<Integer> arr;
    HashMap<Integer, Integer> chk;
    
    public int[] solution(String s) {
        init(s);
        return proc();
    }
    
    public void init(String s){
        infos=new ArrayList<>();
        chk=new HashMap<>();
        
        StringBuilder num=new StringBuilder();
        for(int i=1;i<s.length()-1;i++){
            if(s.charAt(i)=='{'){
                arr=new ArrayList<>();
            }
            else if(s.charAt(i)==','){
                if(num.length()>0){
                    arr.add(Integer.parseInt(num.toString()));
                    num=new StringBuilder();
                }
                
            }
            else if(s.charAt(i)=='}'){
                arr.add(Integer.parseInt(num.toString()));
                num=new StringBuilder();
                infos.add(arr);
            }
            else{
                num.append(s.charAt(i));
            }
        }
        
    }
    
    public int[] proc(){
        infos.sort((a,b)->Integer.compare(a.size(),b.size()));
        int idx=0;
        
        for(ArrayList<Integer> temp: infos){
            for(int num: temp){
                //System.out.print(num+" ");
                if(!chk.containsKey(num)){
                    chk.put(num,idx++);
                }
            }
            System.out.println();
        }
        
        int[] ans=new int[chk.size()];
        
        for(Map.Entry<Integer, Integer> info: chk.entrySet()){
            ans[info.getValue()]=info.getKey();
        }
        
        return ans;
    }
}