[프로그래머스] 64065번 - 튜플 (Java)

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

프로그래머스

---

 

문제

---

 

풀이

1) 입력 문자열을 배열의 형태로 바꾸기

먼저 입력이 '{', '}', ',' 로만 이루어져 있는 2차원 배열 같이 생긴 문자열이기 때문에 이 문자열을 배열의 형태로 바꿔야 합니다.

 

여러 방법이 있지만 저는 substring과 split을 사용했습니다. 먼저 말씀 드리자면 별로 추천드리는 방법은 아닙니다!

처음에는 양쪽에 있는 '{'와 '}'를 뺀 나머지 문자열을 '},{'로 split 하려고 했는데 regex syntax 오류가 났습니다. java 문서에서 split을 찾아보니까 파라미터로 regular expression이 들어가는 데 '},{'는 정규식 표현이 아니기 때문에 오류가 나는 것이었습니다.

 

그래서 일단 맨 앞의 '{'와 맨 뒤의 '}}'를 뺀 substring을 '},'로 split 하였습니다.

그렇게 하면 '{...' 와 같은 문자열이 배열에 들어가는데 그걸 다시 맨 앞의 '{'를 뺀 substring을 사용하는 식으로 작성했습니다.

 

비효율적인 방법이기 때문에 추천드리지 않고! '{'와 '}'를 공백으로 바꾸고 양쪽 공백을 제거한 뒤 ' , '(, 앞뒤로 공백이 있음)로 split하는 방법을 추천드립니다. (좋아요를 가장 많이 받은 풀이 방법입니다.)

 

 

2) 집합이 나타내는 튜플 구하기

튜플이 (a1, a2, a3, ..., an)로 주어질 때, 집합은 {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}와 같이 표현할 수 있습니다. 규칙을 보면, 크기가 1인 집합은 a1, 크기가 2인 집합은 크기가 1인 집합에 a2를 추가한 것, 크기가 3인 집합은 크기가 2인 집합에 a3를 추가한 것, ... 입니다. 따라서 마지막 집합은 크기가 n-1인 집합에 an을 추가한 크기가 n인 집합이 됩니다.

 

이를 거꾸로 집합에서 튜플을 구한다고 한다면 길이가 작은 것부터 새로 추가되는 원소가 튜플의 다음 원소가 됩니다.

예를 들어 집합이 {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}} 이라면 빨간색 원소가 새로 추가되는 원소입니다. 그래서 튜플의 첫 원소는 2, 다음은 1, 다음은 3, 다음은 4가 되는 것입니다. 집합이 {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}처럼 순서가 섞여(?) 있어도 크기가 작은 것부터 정렬하면 위와 같은 방법으로 튜플을 구할 수 있습니다.

 

그래서 집합을 크기를 기준으로 오름차순 정렬한 다음, 각 집합을 돌면서 기존에 값이 포함되어 있지 않는 값을 추가해주면 됩니다.

 

집합도 문자열 형태이기 때문에 ','로 split 한 뒤 정수형으로 바꿔 비교하고 추가하면 됩니다.

 

 

 

소스코드

import java.util.*;

class Solution {
    public int[] solution(String s) {
        // 문자열을 배열의 형태로 바꾸기
        String[] subset = s.substring(1, s.length()-2).split("},");
        
        int maxlen = 0, maxidx = -1;
        for(int i=0; i<subset.length; i++){
            subset[i] = subset[i].substring(1, subset[i].length());
        }
        
        // 배열을 크기를 기준으로 오름차순 정렬
        Arrays.sort(subset, new Comparator<String>(){
            public int compare(String o1, String o2){
                return o1.length() - o2.length();
            }
        });
        
        int[] answer = new int[subset.length];
        ArrayList<Integer> list = new ArrayList<>(); // 튜플 역할
        
        // 배열을 하나씩 돌면서 새로운 값을 추가해줌
        for(int i=0; i<subset.length; i++){
            String[] arr = subset[i].split(",");
            
            for(int j=0; j<arr.length; j++){
                if(!list.contains(Integer.parseInt(arr[j]))){
                    list.add(Integer.parseInt(arr[j]));
                }
            }
        }
        
        for(int i=0; i<list.size(); i++){
            answer[i] = list.get(i);
        }
        return answer;
    }
}

 

---

마치며 ...

split에는 String 형태면 어떤 거든 넣을 수 있을 줄 알았는데 정규식으로 넣어야 한다는 것을 이 문제를 풀면서 알았다 ..! split 말고 replaceAll도 마찬가지였다. 새롭게 알게 된 부분이었다!