2019 카카오 개발자 겨울 인턴십 - 튜플- [프로그래머스][Level2]

1시간 30분 ~ 2시간이 걸린 문제.

 

정렬 + Map 자료구조 + String API + pointer(알고리즘 기법)의 활용 등등 알고리즘에서 자주 활용하는 기술들을 많이 활용할 수 있었던 문제여서 좋았다.

 

다른 사람들의 풀이를 보니 { , } 구분을 위해서 replaceAll을 활용하는 경우가 많았다. [ 한수 배우고 간다. ]

 

나의 경우 {의 위치와 }위치를 가리키는 포인터 변수를 따로 두어서 문제를 풀었다.

 

크게 3부분으로 나뉘어 문제를 바라보고 풀어야 할 만큼 까다로운 문제였다.

 

1. 문제에 대한 접근

 

문제를 읽자마다 split(",")하고 배열 길이만큼 정렬한 뒤 값을 추출해서 Map에 넣어서 처리하면 그만이겠구먼! 하고 자신 있게 접근했다.

split(",")하는 순간 집합의 내부에 있는 , 까지 취급되어 제공된 문자열이 완전히 뭉개졌다.

 

아뿔싸 싶었다. 너무 쉽게 접근해버린 것이었다.

 

이후 고민했다. 문자열 내부의 집합을 배열로 전환해서 얻어야 정렬이 가능했다. 그리고 정렬을 해서 작은 수부터 Map에 넣어야만 문제에서 원하는 순서를 얻을 수 있다.

 

이 문제의 핵심은 주어진 문자열에서 어떻게 배열(혹은 리스트)로 추출할 것인가였다.

 

{의 위치는 }의 위치 2칸 이후에 있다. ( , 와 {) 이 규칙을 이용서 {를 Pointer가 가리키는 기준으로 두고 }를 String의 indexOf()로 탐색해나갔다.

        List<List<Integer>> list = new ArrayList<>();
        for(int i = 0; i < len && pos < len; i ++) {
            int a = pos + s.substring(pos, len).indexOf("}");
            String extractstr = s.substring(pos + 1, a); // 배열(리스트)로 전환해야 하는 부분
            List<Integer> ret = convertToList(extractstr); // 배열(리스트)방식으로 전환하는 헬퍼 메서드
            list.add(ret); // 얻은 배열(리스트) 결과를 List에 추가한다.
            pos = a + 2;
        }

배열의 경우 기본적으로 사이즈를 지정해줘야 하기 때문에 해당 문제 도메인과 성격이 맞지 않는다는 것을 느꼈고 [ 가능이야 하다만... ] 나중에 정렬을 처리할 때 좀 더 편리할 수 있는 List에 넣기로 했다.

[ {에 위치를 가리키는 pos가 len을 넘기지 않도록 주의해야 한다! ]

 

converToList() 헬퍼 메서드를 두어서 이를 List<Integer>로 전환하자. 이 부분은 나름 수월하다.

    private List<Integer> convertToList(String s) {
        String[] sArr;
        List<Integer> ret = new ArrayList<>();
        if(s.contains(",")) {
            sArr = s.split(",");
        } else {
            ret.add(Integer.parseInt(s));
            return ret;
        }
        for(int i = 0; i < sArr.length; i++) {
            ret.add(Integer.parseInt(sArr[i]));
        }

        return ret;
    }

주어진 문자열을 ,로 분리한다. 1개의 값이 들어오는 경우가 있는데 이 경우 split(", ")하고 나서 빈 문자열과 관련된 문제가 발생해서 contains()로 해당 값이 존재하는지 체크했다.

 

여기까지 풀었다면 반쯤 온거다.

 

이제 정렬 + Map 자료구조의 활용 파트이다. 

        Collections.sort(list, (l1, l2) -> l1.size() - l2.size());
        for(List<Integer> ret : list) {
            for(int x : ret) {
                if(!map.containsKey(x)) map.put(x, 1);
            }
        }

 

Collection 전용 유틸리티 클래스 Collections를 이용해서 정렬하자. 컨테이너가 담는 값은 LIst <Integer>이기 때문에 따로 정렬 방식을 객체로 넘겨줘야 한다.

 

Comparator를 넘기는 것인데 편하게 람다식으로 넘기도록 하자. l1.size() - l2.size()를 넘기면 크기가 작은 리스트가 앞으로 오게끔 정렬이 된다.

 

이제 해당 List를 순회하면서 Map에 값을 둔다.

Map의 경우 HashMap이 어느 정도 순서를 보장해주지만 확실하진 않다. HashMap에서 순서를 보장해줄 수 있는 LinkedHashMap을 구현체로 두었다.

public Map<Integer, Integer> map = new LinkedHashMap<>();

 

이후 KeySet()을 통해 key을 얻어내고 이 값들을 순차적으로 배열에 넣은 후 반환하면 된다.

 

전체 코드

class Solution {
    public Map<Integer, Integer> map = new LinkedHashMap<>();
    public int[] solution(String s) {

        s = s.substring(1, s.length() - 1);
        int len = s.length();

        // System.out.println(s);

        int pos = 0;
        List<List<Integer>> list = new ArrayList<>();
        for(int i = 0; i < len && pos < len; i ++) {
            int a = pos + s.substring(pos, len).indexOf("}");
            // System.out.println("substring: " + s.substring(pos, len) + ", pos : " + pos + " a : " + a);
            String extractstr = s.substring(pos + 1, a);
            List<Integer> ret = convertToList(extractstr);
            list.add(ret);
            // System.out.println(ret);
            pos = a + 2;
        }
        Collections.sort(list, (l1, l2) -> l1.size() - l2.size());
        for(List<Integer> ret : list) {
            for(int x : ret) {
                if(!map.containsKey(x)) map.put(x, 1);
            }
        }

        int[] answer = new int[map.size()];
        int index = 0;
        for(int key : map.keySet()) {
            answer[index++] = key;
        }

        return answer;
    }

    private List<Integer> convertToList(String s) {
        String[] sArr;
        List<Integer> ret = new ArrayList<>();
        if(s.contains(",")) {
            sArr = s.split(",");
        } else {
            ret.add(Integer.parseInt(s));
            return ret;
        }
        for(int i = 0; i < sArr.length; i++) {
            ret.add(Integer.parseInt(sArr[i]));
        }

        return ret;
    }
}

 

개인적인 생각 : 정렬, String API, Map, Pointer [메모리 Pointer가 아니라 알고리즘 테크닉인 포인터 ] 활용방식.

 

문제를 보고 바로 달려들어 함정에 보기 좋게 빠졌던 문제.

 

풀면 풀수록 활용해야 하는 알고리즘 스킬이 왜 이리도 많은지 당황하게 되는 문제였다.

 

보통 Level 2라면 2~3가지의 알고리즘 역량들을 확인하는데 해당 문제는 무려 4가지가 활용되는 문제였다.

 

진짜 애먹은 문제.

 

이런 문제를 출시하는 것도 새삼 놀랍다.

 

DFS, BFS, DP, 탐욕, 그래프 등등의 문제보다 이런 문제가 더 재밌긴 하지만... 진짜 어려웠다.

 

이게 Level 2라는 게 알고리즘 세상의 평균치가 어느 만큼 높아졌는지를 느끼게 해 준다.