LinkedHashSet 과 문자열 파싱

프로그래머스 2019 카카오 인턴십 Level 2 문제인 튜플을 Java로 풀어보았다.
LinkedHashSet을 이용했고 파싱이 주요했던 문제다.
문자열 파싱을 정말 간단하게 Java API를 이용해서 푸신 분들이 많던데 사실 난 그 정도로 자바에 능통하지 않기 때문에 직접 열심히 나만의 파서를 구현했다. 실제 시험장에서 내가 쓸 줄 모르는 기술들은 당연히 사용 불가능하기 때문에 현재 내가 알고 있는 지식으로 어떻게든 풀어내는 게 중요하겠다는 생각을 풀고나서 하게됐다.

문제 링크만 첨부하겠다.
https://programmers.co.kr/learn/courses/30/lessons/64065

---

파서 구현

복수의 부분 집합들을 표현하는 String이 주어진다. 내가 만든 파서의 목적은 입력으로 주어지는 String을 먼저 부분 집합별로 ArrayList로 구분해서, 하나의 LinkedList에 집어 넣는 것이다. 전체 LinkedList가 완성되면 각 부분집합의 원소 개수대로 오름차순 정렬을 해서 파싱을 완료한다.

즉, String input = "{{1,2,3},{2,1},{1,2,4,3},{2}}" 으로 주어지면, 이 input을 parser(String input)에 집어넣어서 다음과 같은 결과를 얻어내야 한다.

LinkedList list
1. ArrayList[0] : [2]
2. ArrayList[1] : [2, 1]
3. ArrayList[2] : [1, 2, 3]
4. ArrayList[3] : [1, 2, 4, 3]

이런 식으로 완성이 되어야 하는 것이다.
다음은 내가 구현한 파서의 코드다.

static LinkedList<ArrayList<Integer>> parser(String s){
        LinkedList<ArrayList<Integer>> result = new LinkedList<>();
        int length = s.length();
        int listPos = 0;
        ArrayList<Integer> tmp = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<length-1; i++){ // 어차피 양쪽 끝은 중괄호로 감싸져 있으니 무시
            char cur = s.charAt(i);
            if(cur=='{')    continue;
            if(cur==','){
                char next = s.charAt(i+1);
                if(next=='{'){
                    i++;
                    continue;
                }
                else{
                    tmp.add(Integer.parseInt(sb.toString()));
                    sb = new StringBuilder();
                    continue;
                }
            }
            if(cur=='}') {
                tmp.add(Integer.parseInt(sb.toString()));   sb = new StringBuilder();
                ArrayList<Integer> copy = new ArrayList<>();    copy.addAll(tmp);   tmp.clear();
                result.add(listPos, copy);  listPos++; // 한 부분집합이 끝났으면 다음 부분집합 위치로
                continue;
            } 
            if(cur>='0' && cur<='9')
                sb.append(cur);
        }
//        result.sort(new Comparator<ArrayList<Integer>>() {
//            @Override
//            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
//                if(o1.size()>o2.size()) return 1;
//                else    return -1;
//            }
//        });

        Collections.sort(result, (o1,o2) -> { return Integer.compare(o1.size(), o2.size());}); // 이렇게 쓸 수 있다는 걸 몰랐다. 이게 더 편하네.. 

        return result;
    }

LinkedHashSet 이용하기

위의 파서를 통해 부분 집합의 원소 개수별로 정렬을 마무리했으면 문제 풀이는 끝난 거나 다름 없다.
정렬된 부분집합을 탐색하며 set에 원소를 추가해주면 튜플의 원소 순서대로 set이 구성되게 된다.

아래는 위를 구현한 solution 코드다.

static int[] solution(String s) {
        LinkedList<ArrayList<Integer>> list = parser(s);
        LinkedHashSet<Integer> set = new LinkedHashSet<>();

        for(int i=0; i<list.size(); i++)
            for(int j=0; j<list.get(i).size(); j++)
                set.add(list.get(i).get(j));

        int[] answer = new int[set.size()];
        Iterator<Integer> it = set.iterator();
        for(int i=0; i<set.size(); i++)
            answer[i] = it.next();
        return answer;
    }

---

파서 구현이 가장 중요했던 문제다!
아래는 내가 제출한 전체 코드다.

import java.io.*;
import java.util.*;

public class Tuple {
    static int[] solution(String s) {
        LinkedList<ArrayList<Integer>> list = parser(s);
        LinkedHashSet<Integer> set = new LinkedHashSet<>();

        for(int i=0; i<list.size(); i++)
            for(int j=0; j<list.get(i).size(); j++)
                set.add(list.get(i).get(j));

        int[] answer = new int[set.size()];
        Iterator<Integer> it = set.iterator();
        for(int i=0; i<set.size(); i++)
            answer[i] = it.next();
        return answer;
    }

    static LinkedList<ArrayList<Integer>> parser(String s){
        LinkedList<ArrayList<Integer>> result = new LinkedList<>();
        int length = s.length();
        int listPos = 0;
        ArrayList<Integer> tmp = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<length-1; i++){ // 어차피 양쪽 끝은 중괄호로 감싸져 있으니 무시
            char cur = s.charAt(i);
            if(cur=='{')    continue;
            if(cur==','){
                char next = s.charAt(i+1);
                if(next=='{'){
                    i++;
                    continue;
                }
                else{
                    tmp.add(Integer.parseInt(sb.toString()));
                    sb = new StringBuilder();
                    continue;
                }
            }
            if(cur=='}') {
                tmp.add(Integer.parseInt(sb.toString()));   sb = new StringBuilder();
                ArrayList<Integer> copy = new ArrayList<>();    copy.addAll(tmp);   tmp.clear();
                result.add(listPos, copy);  listPos++;
                continue;
            } // 한 부분집합이 끝났으면 다음 부분집합 위치로
            if(cur>='0' && cur<='9')
                sb.append(cur);
        }

        Collections.sort(result, (o1,o2) -> { return Integer.compare(o1.size(), o2.size());});

        return result;
    }
}

오늘 배운 것

내 머릿속에 있는 재료만으로 어떻게든 풀어내는 연습을 하자