튜플

문제

특정 튜플을 표현하는 집합이 담긴 문자열 s가 주어질 때, s가 표현하는 튜플을 배열에 담아 반환하는 프로그램을 작성하는 문제입니다. 예를 들어, 튜플이 (2, 1, 3, 4)인 경우, 이는 집합 {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}로 표현될 수 있으며, 집합의 순서는 바뀔 수 있습니다.

• 입력: 튜플의 집합을 나타내는 문자열 s (길이 5 이상 1,000,000 이하, 원소는 100,000 이하의 자연수)
• 출력: 원본 튜플을 나타내는 정수 배열

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

풀이 1: 문자열 파싱 (수동 추출)과 길이를 기준으로 한 정렬

문자열에 포함된 괄호를 하나씩 해석하여 각 부분 집합을 분리하고, 원소가 적은 부분 집합부터 순차적으로 탐색하여 새롭게 추가되는 원소를 찾아내는 방식입니다.

• 문자열 파싱 (수동 추출): 입력된 문자열 s에서 가장 바깥쪽 괄호를 제외한 1부터 s.length() - 1까지 순회합니다.
  • 열린 괄호 {를 만나면 flag를 true로 설정하여 원소 기록을 시작합니다.
  • 닫힌 괄호 }를 만나면 지금까지 StringBuilder에 기록된 숫자 문자열을 리스트(list)에 추가하고, StringBuilder를 비운 뒤(setLength(0)) flag를 false로 돌립니다.
  • flag가 true인 상태에서는 콤마(,)와 숫자를 모두 StringBuilder에 덧붙여 부분 집합의 형태를 만들어냅니다.
• 길이 기준 오름차순 정렬: 분리된 부분 집합 문자열들을 담은 리스트를 '문자열의 길이' 기준으로 오름차순 정렬합니다. 가장 짧은 문자열이 튜플의 첫 번째 원소이고, 길이가 길어질수록 새로운 원소가 하나씩 추가되는 구조이기 때문입니다.
• 새로운 원소 추출 및 직접 할당 최적화:
  • 가장 짧은 부분 집합부터 순회하며 콤마(,)를 기준으로 숫자를 분리합니다.
  • 빠른 중복 검사를 위해 크기가 100,001인 boolean 배열(check)을 사용합니다.
  • 튜플의 최종 길이는 부분 집합의 개수(list.size())와 동일합니다. 따라서 정답 배열 ans를 이 크기만큼 미리 선언해 두고, 중복되지 않은 새로운 숫자를 발견하면 별도의 리스트를 거칠 필요 없이 현재 인덱스 i에 직접 ans[i] = x 형태로 삽입하여 메모리와 변환 시간을 단축합니다.

코드 1

import java.util.*;

class Solution {
    public int[] solution(String s) {
        List<String> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        boolean flag = false;
        
        // 1. 바깥 괄호를 제외하고 순회하며 부분 집합 문자열 파싱
        for (int i = 1; i < s.length() - 1; i++) {
            char c = s.charAt(i);
            if (c == '{') {
                flag = true;
            } else if (c == '}') {
                list.add(sb.toString());
                sb.setLength(0);
                flag = false;
            } else if (flag) {
                sb.append(c);
            }
        }
        
        // 2. 부분 집합 문자열을 길이를 기준으로 오름차순 정렬
        Collections.sort(list, (s1, s2) -> {
            return s1.length() - s2.length();
        });
        
        int[] ans = new int[list.size()];
        boolean[] check = new boolean[100001];
        
        // 길이가 짧은 부분 집합부터 순회하며 새로운 원소 발굴
        for (int i = 0; i < list.size(); i++) {
            String[] tmp = list.get(i).split(",");
            for (String a : tmp) {
                int x = Integer.parseInt(a);
                // 이미 튜플에 들어간 원소라면 건너뜀
                if (check[x]) continue;
                
                check[x] = true;
                ans[i] = x;
            }
        }
                
        return ans;
    }
}

풀이 2: split과 HashSet을 활용한 풀이

문자열을 한 글자씩 순회하는 대신 자바의 내장 문자열 자르기 함수(split)와 정규식을 활용하여 코드를 단축시킨 풀이입니다.

• 정규식을 활용한 단괄 파싱: 가장 바깥쪽의 괄호 {{ 와 }} 를 substring으로 잘라냅니다. (s.substring(2, s.length() - 2)) 그 후 내부의 집합들을 구분하는 },{ 를 기준으로 문자열을 split 합니다. 자바 정규식에서 괄호 기호는 특수문자이므로 \\} 와 같이 이스케이프 처리가 필요합니다.
• 배열 정렬: 분리된 문자열 배열을 길이를 기준으로 오름차순 정렬합니다.
• HashSet의 add 특성 활용: HashSet의 add 메서드는 값이 집합에 새롭게 추가되었을 때만 true를 반환하고, 이미 존재한다면 false를 반환합니다. 이를 if문의 조건으로 활용하면 중복 검사와 튜플 배열 생성을 동시에 아주 깔끔하게 처리할 수 있습니다.

코드 2

import java.util.*;

class Solution {
    public int[] solution(String s) {
        // 1. 가장 바깥쪽 괄호 '{{' 와 '}}' 를 제거하고 "},{" 를 기준으로 문자열 분리
        String[] arr = s.substring(2, s.length() - 2).split("\\},\\{");
        
        // 2. 문자열 길이를 기준으로 오름차순 정렬
        Arrays.sort(arr, (a, b) -> a.length() - b.length());
        
        int[] ans = new int[arr.length];
        int idx = 0;
        Set<String> set = new HashSet<>();
        
        // 3. 길이가 짧은 문자열부터 탐색하며 새로운 숫자 발굴
        for (String str : arr) {
            String[] numbers = str.split(",");
            for (String val : numbers) {
                // set.add()는 기존에 없던 새로운 원소가 추가될 때만 true를 반환
                if (set.add(val)) {
                    ans[idx++] = Integer.parseInt(val);
                }
            }
        }
        
        return ans;
    }
}

알고리즘 분류

문자열 (String), 파싱 (Parsing), 정렬 (Sorting), 해시를 사용한 집합 (Hash Set)