프로그래머스 Lv.2) 튜플

튜플

코딩테스트 연습 - 튜플

풀이

 답의 규칙을 찾은 결과 가장 작은 크기의 부분 수열이 가진 원소의 순서대로 답의 순서가 정해진다는 것이었다.

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

위의 예제로 설명하면,

가장 작은 크기의 부분수열 {2}로부터 2가 정답의 맨 첫번째임을 알 수 있고, 그다음 {2,1}을 통해 2->1, {1,2,3}을 통해 2->1->3, {1,2,4,3}을 통해 2->1->3->4가 되는 것이다.

 

우선순위 큐를 통해 가장 작은 크기의 부분수열부터 큰 부분수열을 찾아가며 답을 리턴해줬다.

또한, String 하나로 주어지기 때문에 이를 parsing하기 위해 replaceAll과 split 메소드를 이용했다.

HashSet은 중복 검사를 통해 원소가 딱 한번만 들어가게 하기위해 썼고, MyNum은 부분수열을 관리하기 위해 클래스를 만들었다.

 

코드

import java.util.HashSet;
import java.util.PriorityQueue;

public class Tuple_64065 {
    private static int[] solution(String s) {
        PriorityQueue<MyNum_64065> pq = new PriorityQueue<>();
        HashSet<String> strSet = new HashSet<>();
        String[] strArr = s.split("},");
        int len = 0;
        for(String str : strArr) {
            MyNum_64065 tmp = new MyNum_64065(str.replaceAll("[{]", "").replaceAll("[}]","").split(","));
            len = Math.max(len, tmp.numArr.length);
            pq.offer(tmp);
        }
        int[] answer = new int[len];
        int idx=0;
        while(!pq.isEmpty()) {
            MyNum_64065 mynum = pq.poll();
            String[] tmpArr = mynum.numArr;
            for(String str : tmpArr) {
                if(!strSet.contains(str)) {
                    answer[idx++] = Integer.parseInt(str);
                    strSet.add(str);
                }
            }
        }

        return answer;
    }
    public static void main(String[] args) {
        String s = "{{2},{2,1},{2,1,3},{2,1,3,4}}";
        int[] result = solution(s);

        for(int num : result) {
            System.out.print(num + " ");
        }
    }
}

class MyNum_64065 implements Comparable<MyNum_64065> {
    String[] numArr;

    public MyNum_64065(String[] numArr) {
        this.numArr = numArr;
    }

    @Override
    public int compareTo(MyNum_64065 mynum) {
        return this.numArr.length > mynum.numArr.length ? 1 : -1;
    }
}