[프로그래머스] 튜플

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64065

프로그래머스

코드

import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

class Solution {
    public int[] solution(String s) {

        int[] answer = {};
        
        s= s.substring(1,s.length()-1);
        s = s.replaceAll("\\}\\,\\{", "#");
        s= s.substring(1,s.length()-1);

        String[] arrS = s.split("#");
        
        // 이제 문자열 크기가 가장 작은것부터 순서대로 LinkedHashSet에 넣어준다.
        // 문자열 크기가 가장 작은 대상을 기록한다.
        Map<Integer,Object> map = new TreeMap<>();
        for ( int i = 0 ; i < arrS.length; i++ ) {
        	String[] tuple = arrS[i].split(",");
        	map.put(tuple.length, tuple);
        }
        
        Iterator mapItr = map.keySet().iterator();
        
        Set<Integer> set = new LinkedHashSet<>();
        
        while( mapItr.hasNext() ) {
        	int key = (int)mapItr.next();
        	String[] arr = (String[])map.get(key);
        	
        	for ( String tuple : arr ) {
        		set.add(Integer.valueOf(tuple));
        	}
        }
        
        answer = new int[set.size()];
        
        Iterator setItr = set.iterator();
        
        int index = 0 ;

        while( setItr.hasNext() ) {
        	answer[index] = (int)setItr.next();
        	index++;
        }
        
        return answer;
    
    }
}

제출 결과

나의풀이

음.. 먼저 문제부터 이해하는데 시간이 걸렸다.. ( 이해력이 아직 부족한듯하다... )

 

문제를 읽어보면 튜플이란 "셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음"이라고 한다.

 

핵심은 순서가 있다는 것인것 같다..

 

문제의 예시에서 { 2,1,3,4 } 튜플의 경우에는 아래와 같이 표현할 수 있고,

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

이는 집합 원소의 순서는 바뀌어도 상관이 없다고한다.

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}
• {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}
• {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

위 3개처럼 내부적으로 집합원소의 순서가 바뀔수 있지만, 결국 저 집합의 튜플은 { 2,1,3,4 }라는것을 찾아낼 수 있다.

 

그 이유는 원소가1개인 집합의 경우는 반드시 튜플의 1번째 요소 값을 가지고 있기 때문이다.

 

따라서 원소가2개인 집합의 경우에 원소의 순서가 뒤바뀌어 있어도, 원소가1개인 집합의 값을 가지고 2번째 요소의 값이 무엇인지 유추해낼 수 있다.

 

고로 튜플의 n번째 요소의 값을 n-1개의 집합에서 유추할 수 있다. 

 

이제 이걸 코드로 풀어내면 된다..

 

첫번째로 입력값을 처리할 수 있는데이터로 만드는 작업을 선행해 주었다.

s= s.substring(1,s.length()-1);
s = s.replaceAll("\\}\\,\\{", "#");
s= s.substring(1,s.length()-1);

String[] arrS = s.split("#");

 

{{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}} 형태로 주어진 입력을

 

String[] arrS에 아래와 같이 담길수 있도록 해주었다.

 

arrS[0] = a1

arrS[1] = a1,a2

arrS[2] = a1,a2,a3

arrS[3] = a1,a2,a3,a4

 

두번째로 TreeMap에 아래와 같은 순서로 데이터가 저장되도록 해주었다, key는 집합의 갯수(n), value는 해당 집합의 배열이 되겠다.

 

TreeMap은 key값을 오름차순하여 데이터를 저장해 줌으로 결과적으로 입력값이 어떻게 들어오든 n개의 집합이 오름차순으로 저장된다.

 

key : 1, value : arrS[0]

key : 2, value : arrS[1]

key : 3, value : arrS[2]

key : 4, value : arrS[3]

Map<Integer,Object> map = new TreeMap<>();
  for ( int i = 0 ; i < arrS.length; i++ ) {
  String[] tuple = arrS[i].split(",");
  map.put(tuple.length, tuple);
}

세번째로 TreeMap을 참조하여 1~n개집합을 순서대로 LinkedHashSet에 담아준다.

 

LinkedHashSet은 저장 순서를 유지함으로,

 

1개집합의 값을 add하게 되고 다음으로

 

2개의 집합에서 값을 add하게 되지만 첫번째에 add된 값은 중복값이므로 add되지않는다..

 

그렇게 1~n개집합을 순서대로 LinkedHashSet에 담으면 우리가 원하는 Tuple을 구할 수 있다.

Iterator mapItr = map.keySet().iterator();

Set<Integer> set = new LinkedHashSet<>();

  while( mapItr.hasNext() ) {
  int key = (int)mapItr.next();
  String[] arr = (String[])map.get(key);

  for ( String tuple : arr ) {
  set.add(Integer.valueOf(tuple));
  }
}

마지막으로 LinkedHashSet의 값을 solution함수의 return타입인 int[] answer에 담아 준후 return한다.

 

위와 같은 방법으로 해당 문제를 해결하였다..

 

뭔가 자료구조를 여러개 활용하였지만 최적의 방법은 아닌것같다.. 더 좋은 방법이 생각나면 추가로 수정해야겠다..