[pgm_64065] 튜플 (java)

문제링크

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 Set

튜플로 만들어지는 집합이 input으로 들어오고 값들을 확인하여 튜플을 찾아내는 문제이다. 이 때 튜플의 수가 (a1,a2,a3,a4)라고 하면 이 것으로 만들수 있는 값들의 집합을 {{a1},{a1,a2},{a1,a2,a3},{a1,a2,a3,a4}}로 구성될 수 있으며, 집합의 순서는 서로 바뀔수 있다. 이 때  튜플로 만들어진 집합을 보고 튜플을 만들어주면 해결할 수 있다.

 

문제를 해결하기 위해서는 구성된 집합의 크기가 가장 작은 것부터 확인해야한다. 왜냐하면 가장 작은 값 중 포함되지 않은 값을 빼면 순서를 구할 수 있기 때문이다. 예시에서 보여준 {{a1},{a1,a2},{a1,a2,a3},{a1,a2,a3,a4}} 이 집합을 무작위로 섞어보겠다.

{{a2,a1},{a1},{a1,a3,a2,a4},{a2,a3,a1}} 집합의 순서가 변경될 수 있기 때문에 이러한 값이 주어질 수도 있다.

이 때 값들만 빼보면 아래와 같다.

 

a2,a1

a1

a1,a3,a2,a4

a2,a3,a1

 

여기서 중요한 것은 a뒤에 오는 숫자가 바로 튜블의 위치가 된다는 것이다. 즉 집합에 있는 데이터의 개수가 가장 적은것부터 순서대로 확인하며 사전에 처리된 값이 아니라면 튜플의 순서대로 구할 수 있다. 집합의 크기가 1인  a1을 집합에 넣어주고 튜플의 첫번째 수로 등록한다.

 

a2,a1

a1

a1,a3,a2,a4

a2,a3,a1

튜플 : (a1)

두번째로 긴 {a2,a1} 집합을 처리하는데 이 때 a1은 이미 집합에 포함되어있으므로 a2를 꺼내어 두번째 수로 넣어주고 집합에 넣어준다.

 

a2,a1

a1

a1,a3,a2,a4

a2,a3,a1

튜플 : (a1,a2)

 

그 다음으로 긴 {a2,a3,a1}집합을 위와 동일하게 처리해준다. 이 때 a1,a2는 이미 집합에 포함되어 있으므로 a3를 튜플의 다음수로 넣어주고 set에 넣어준다.

 

a2,a1

a1

a1,a3,a2,a4

a2,a3,a1

튜플 : (a1,a2,a3)

 

마지막으로 가장 긴  집합인 {a1,a2,a3,a4}를 확인하여 a4를 넣어주면 최종적인 튜플을 완성할 수 있다.

 

a2,a1

a1

a1,a3,a2,a4

a2,a3,a1

튜플 : (a1,a2,a3,a4)

 

나는 이렇게 문제를 해결하기 위해서 우선 String 값들을 위처럼 정제하여주고 순서대로 실행하기 위해 미리 배열의 크기로 정렬을 해주었다.

Arrays.sort(values,(o1,o2) -> o1.length() > o2.length() ? 1 : -1);

함수형 인터페이스를 활용하여 값을 정렬할 때 배열의 길이를 기준으로 정렬할 수 있도록 변경하여 sort해주었다.

 

구현코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution {

    public Integer[] solution(String s) {
        s = s.substring(1,s.length()-1);
        ArrayList<String> list = new ArrayList<>();

        for(int i = 0; i < s.length(); i++){
            String value = "";
            if(s.charAt(i) == '{'){
                while (s.charAt(++i) != '}'){
                    value =  value + s.charAt(i);
                }
                list.add(value);
            }
        }

        String[] values = list.toArray(new String[0]);
        Arrays.sort(values,(o1,o2) -> o1.length() > o2.length() ? 1 : -1);

        ArrayList<Integer> tuple = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for(String value : values){
            String[] splitValue = value.split(",");

            for(String v : splitValue){
                if(!set.contains(Integer.parseInt(v))){
                    tuple.add(Integer.parseInt(v));
                    set.add(Integer.parseInt(v));
                }
            }
        }
        return tuple.toArray(new Integer[0]);
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)