[Java] 프로그래머스 - 튜플

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/64065?language=java 

프로그래머스

[풀이]

String 형식으로 입력되는 집합의 묶음 s를 문자열 함수들로 쪼개어 각 집합을 ArrayList에 담고 나서 이를 크기 순으로 저장 하기 위해 고민해본 결과, Comparable을 상속받은 Class를 이용해 우선순위 큐를 이용하였습니다.

 

Tuple 클래스

Tuple 클래스를 선언하여 집합을 저장할 set과 집합의 크기 size를 선언해줍니다.

compareTo함수를 오버라이드 받아 크기순으로 정렬 할 수 있게 size - o.size를 return해줍니다.

 

Tuple클래스를 선언한 후 String s를 탐색하며 각 집합들을 PriorityQueue<Tuple> pq 에 Tuple 객체의 형태로 삽입합니다. pq 세팅이 완료된 후 getTuple()를 통해 poll()연산을 통해 각 집합의 숫자를 answer에 삽입하며 최종 튜플을 구합니다.

[코드]

import java.util.*;
class Tuple implements Comparable<Tuple>{
    ArrayList<Integer> set;
    int size;
    public Tuple(ArrayList<Integer> set, int size) {
        this.set = set;
        this.size = size;
    }
    @Override
    public int compareTo(Tuple o) {
        return size - o.size;
    }
}
class Solution {
    public static PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();
    public static int[] answer;
    public int[] solution(String s) {
        String[] str = s.split("");
        int index = 1;
        
        // PQ에 각 집합 원소들을 split을 통해 쪼개서 넣음, 이때 집합 크기순으로 저장
        while(index < str.length) {
            if(str[index].equals("{")) {
                int i = index + 1;
                String temp = "";
                ArrayList<Integer> list = new ArrayList<Integer>();
                while(!str[i-1].equals("}")) {
                    if(str[i].equals(",") || str[i].equals("}")) {
                        list.add(Integer.parseInt(temp));
                        temp = "";
                    } else {
                        temp += str[i];   
                    }
                    i++;
                }
                pq.offer(new Tuple(list,list.size()));
            }
            index++;
        }
        getTuple();
        return answer;
    }
    // 튜플을 구해준다
    public static void getTuple() {
        ArrayList<Integer> list = new ArrayList<Integer>();
        // 작은 List부터 탐색
        while(!pq.isEmpty()) {
            Tuple t = pq.poll();
            // 이전 List에 포함되지 않은 숫자만 추가
            for(Integer n:t.set) {
                if(!list.contains(n)) {
                    list.add(n);
                }
            }
        }
        answer = new int[list.size()];
        int i = 0;
        for(Integer n:list) {
            answer[i] = n;
            i++;
        }
    }
}