[ Programmers - LV2 ] 순위 검색

https://school.programmers.co.kr/learn/courses/30/lessons/72412

프로그래머스

문제 풀이는 성공 했지만 코딩 테스트에 적합한 풀이인가 의문이 많이 들었다.

나의 경우 구현에 시간이 오래 걸렸기 때문에 시간내에 풀 수 있는 조금 더 간단한 방법을 사용했어야 하지 않았을까 싶다.

그 방법들도 생각은 해봤으니 아래에서 공유 하는걸로 하겠다.

 

나는 문제를 풀이할 때 Trie(트라이), BFS(너비 우선 탐색), Binary Search(이분 탐색) 3 가지 방법을 사용했다.

다른 사람들의 풀이를 보고 보완하거나 더 괜찮은 풀이를 찾으려고 했지만 문제가 간단하지 않았기 때문에(내 기준) 이해하기가 난해한 풀이가 많았다.

 

나도 다시 돌아볼지 모르니 풀이에 대해서 블로그에 남기기로 했다.

---

[ 📌 문제에 접근하기... ]

1. 자료 구조 설계

• 개발언어: cpp / java / python 
• 직군: backend / frontend
• 경력: junior / senior
• 소울푸드: chicken / pizza
• 점수

주어진 query 에 대한 필터 옵션이 미리 정해져 있었기 때문에 선택지가 여러개 있었다.

[ 필요한 자료 구조 ]

 

위와 같이 트리 구조로 각 조건에 맞는 인원들에 대한 인덱싱이 필요 하다고 생각이 되었고, 트리를 만들 수 있는 방법들을 생각 하게 되었다.

 

1 - 1. HashMap 을 이용한 변경 불가능한 구조

가장 먼저 내가 생각해낸 방법은 HashMap 을 하드 코딩과 비슷하게 위의 조건들에 맞도록 생성되게 하는 방법 이었다.

Map<String, Map<String, Map<String, Map<String, List<Integer>>>>>

 

하지만 먼저 말했듯이 트리의 자식들 길이 등 모든게 주어진 문제에 맞춰진 구조기 때문에 변경이 불가능하다.

(물론 코딩 테스트라고 생각하면 이게 현명한 구조라고 생각된다...)

---

1 - 2. 배열을 이용한 트리 구조 만들기

알고리즘 스터디에서 스티디원의 풀이를 보고 알게 되었는데, 나는 3 차원 배열을 넘어서는 배열은 사용해본 경험도 없고 생각도 못해봤기 때문에 5 차원 배열을 생각하지 못했다.

int[][][][][] tree = new int[3][2][2][2][100001];

 

배열로 풀이 해도 각 인덱스별로 알아볼 수 있도록 변수명을 작성하면 크게 헷갈리지도 않는 것 같다.

tree[lan][pos][lv][food][score]

 

다만 앞서서 Map 을 이용한 방법과 같이 구조가 고정되어 있기 때문에 변경에 용이하지 않았고, 코딩 테스트에 중요하지 않지만 내가 원치 않아서 다른 풀이를 생각하게 되었다.

(이미 나는 유연한 구조로 풀자라고 머릿속을 가득 채우고 있었기 때문에 생각 자체가 유연한 상태가 아니였다.)

---

1 - 3. Trie 알고리즘 개념

위 방법들은 내가 선호하는 구조는 아니기 때문에 좀 더 유연한 구조를 만들고 싶었고 Trie 알고리즘이 생각 났다.

사실 몇 번 구현한적은 없었지만 사용할 일이 별로 없어서 그런지 처음 접했을 때 신기해서 기억속에 고이 모셔두고 있었다.

 

라이브러리를 사용하지 않는 이상 자료 구조를 직접 구현해야 했기 때문에 조금 고민되었지만 기억도 다시 되짚어서 복습한다고 생각하니 크게 나쁘지 않은 방향이라고 생각이 되었고 Trie 알고리즘을 이용 하기로 했다.

class Node {
    Map<String, Node> children = new HashMap<>();
    List<Integer> scores;  // 마지막 노드만 갖는 리스트로 중간 노드들은 null 값을 갖고 있음
    int level;
    boolean isSorted = false;  // 리스트 정렬이 이미 되었는지
    boolean isLeaf = false;    // 마지막 노드인지

    public Node(int level) {
        this.level = level;
    }
}

 

먼저 트리를 생성하기 위해서 트리를 구성하는 노드를 만들었다.

• children: 현 노드의 자식 노드
• socres: 말단 노드가 갖는 지원자들의 점수 리스트 (말단 노드만 초기화된 리스트를 갖음)
• level: BFS 탐색을 할 때 query 의 keyword 식별을 위한 변수 (현재 노드의 트리에서의 높이)
• isSorted: scores 리스트 정렬 여부 (이분 탐색 정렬이 필수인데 중복된 정렬 작업을 막기 위해서)
• isLeaf: 말단 노드인지 여부

/**
 * 마지막 노드 표시
 * @param score 지원자의 점수
 */
public void setIsLeaf(int score) {
    // 이미 마지막 노드인 경우 리스트에 값만 넣는다.
    if(isLeaf) {
        scores.add(score);
        return;
    }

    isLeaf = true;  // 마지막 노드 표시
    scores = new ArrayList<>();  // 리스트 처음 초기화
    scores.add(score);  // 초기화 된 리스트에 지원자 점수 넣기
}

 

마지막 노드 세팅 메소드로 리스트 초기화를 위해 존재한다.

이미 리스트가 초기화 되어 있는 말단 노드인 경우에는 리스트에 점수만 넣고 종료한다.

/**
 * 리스트를 정렬하는 메소드
 * 플래그를 이용하는 이유는 매번 이분 탐색 실행시 정렬한다면 같은 노드에 대해서 정렬을 여러번
 * 실행할 수 있기 때문에 시간 초과 방지 (볼륨이 크기 떄문에 필수)
 */
public void setIsSorted() {
    isSorted = true;
    Collections.sort(scores);
}

 

정렬을 진행하고, 다시 정렬이 수행되지 않도록 isSorted 플래그를 변경한다.

[ Node 클래스 전체 코드 ]

class Node {
    Map<String, Node> children = new HashMap<>();
    List<Integer> scores;  // 마지막 노드만 갖는 리스트로 중간 노드들은 null 값을 갖고 있음
    int level;
    boolean isSorted = false;  // 리스트 정렬이 이미 되었는지
    boolean isLeaf = false;    // 마지막 노드인지

    public Node(int level) {
        this.level = level;
    }

    /**
     * 마지막 노드 표시
     * @param score 지원자의 점수
     */
    public void setIsLeaf(int score) {
        // 이미 마지막 노드인 경우 리스트에 값만 넣는다.
        if(isLeaf) {
            scores.add(score);
            return;
        }

        isLeaf = true;  // 마지막 노드 표시
        scores = new ArrayList<>();  // 리스트 처음 초기화
        scores.add(score);  // 초기화 된 리스트에 지원자 점수 넣기
    }

    /**
     * 리스트를 정렬하는 메소드
     * 플래그를 이용하는 이유는 매번 이분 탐색 실행시 정렬한다면 같은 노드에 대해서 정렬을 여러번
     * 실행할 수 있기 때문에 시간 초과 방지 (볼륨이 크기 떄문에 필수)
     */
    public void setIsSorted() {
        isSorted = true;
        Collections.sort(scores);
    }
}

여기까지는 트리를 구성하는 노드를 알아 보았고, 이제는 트리를 구성하기 위한 클래스를 알아보자

static class Trie {
    Node root = new Node(0);  // 루트 노드
    StringTokenizer st;
}

 

루트 노드는 level 이 0인 노드로 설정한다.

/**
 * 지원자들을 Trie 구조의 노드로 변환 및 삽입
 * @param info 지원자 정보 ex) java backend junior pizza 150
 */
public void insert(String info) {
    Node tmp = root;
    st = new StringTokenizer(info);

    for(int i = 0; i < 4; i++) {
        String key = st.nextToken();
        int level = i + 1;

        // 아직 노드가 만들어지지 않았다면 노드 생성
        tmp = tmp.children.computeIfAbsent(key, k -> new Node(level));
    }

    // 위 반복문에서 4번 실행했기 때문에 st.nextToken() 는 점수에 해당하고, 마지막 노드라는 의미
    tmp.setIsLeaf(Integer.parseInt(st.nextToken()));
}

 

가장 먼저 필요한 메소드로 트리 구조를 위해서 노드를 삽입하는 메소드다.

주석과 함께 보면 java -> backend -> juniro -> pizza 노드를 생성 하는데 for 반복을 4번 하도록 설정되어 있는 이유도 마지막 5번 째 데이터는 점수 데이터가 들어오기 때문에 리스트에 넣어야 해서 이다.

---

2. Trie 구조 탐색(Graph Search )

문제에서 요구하는 조건에 해당하는 트리 구조를 만들면 단방향으로 탐색하기 때문에 어떤 그래프 탐색 방법을 사용해도 문제가 되지 않아서 나는 BFS 를 택했고 순환 구조가 만들어지지도 않기 때문에 방문 체크도 필요 없이 오로지 탐색에만 집중하는 코드를 작성 했다.

/**
 * BFS 를 통해서 Trie 자료 구조 탐색
 * @param query 질의문 ex) java and backend and junior and pizza 100
 * @return query 조건을 만족하는 지원자 수 반환
 */
public int find(String query) {
    Queue<Node> q = new LinkedList<>();
    // java and backend and junior and pizza 100 => java backend junior pizza 100 로 변환
    String[] queries = query.replace(" and", "").split(" ");
    Node tmp = root;
    int target = Integer.parseInt(queries[queries.length - 1]);
    int scoreCnt = 0;

    q.add(tmp);

    while(!q.isEmpty()) {
        Node curNode = q.poll();

        if(Objects.isNull(curNode)) continue;

        // 말단 노드
        if(curNode.isLeaf) {
            // 말단 노드가 갖는 지원자 리스트 정렬을 한 번도 안함
            if(!curNode.isSorted) {
                curNode.setIsSorted();
            }

            // 말단 노드가 갖는 리스트에서 이분 탐색을 통해서 점수 이상의 사람을 구함
            scoreCnt += binarySearch(curNode.scores, target);
            continue;
        }

        String keyword = queries[curNode.level];

        if(keyword.equals("-")) {
            // - 는 모든 조건이기 때문에 현재 노드가 갖는 모든 자식을 탐색 범위에 추가 ex) - -> backend / frontend 노드들
            q.addAll(curNode.children.values());
        } else {
            // query 가 요구하는 조건에 해당하는 자식 노드 반환 ex) backend -> backend 노드
            q.add(curNode.children.get(keyword));
        }
    }

    return scoreCnt;
}

 

전형적인 그래프 탐색 로직인 BFS 이고 와일드 카드 조건인 "-" 이 들어오게 되면 현재 노드의 모든 자식들을 전부 가져온다.

주석은 없지만 항상 root 노드를 잃어버리지 않도록 유지 해준다.

---

3. 특정 점수 이상의 지원자들은 몇 명?

/**
 * 이분 탐색을 통해 특정 점수 이상을 갖는 사람의 수를 구한다.
 * @param scores 트라이 말단 노드가 갖고있는 점수 리스트
 * @param target 기준 점수
 * @return 조건에 해당하는 사람 수
 */
public int binarySearch(List<Integer> scores, int target) {
    int l = 0;
    int r = scores.size() - 1;

    while(l <= r) {
        int mid = (l + r) / 2;

        if(scores.get(mid) >= target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    return scores.size() - l;
}

특정 점수 이상을 요구하기 때문에 마지막 노드가 갖고있는 (정렬된) 리스트에서 이분 탐색을 수행해서 몇 명이 조건에 만족하는지 구하는 메소드이다.

[ Trie 클래스 전체 코드 ]

static class Trie {
    Node root = new Node(0);  // 루트 노드
    StringTokenizer st;

    /**
     * BFS 를 통해서 Trie 자료 구조 탐색
     * @param query 질의문 ex) java and backend and junior and pizza 100
     * @return query 조건을 만족하는 지원자 수 반환
     */
    public int find(String query) {
        Queue<Node> q = new LinkedList<>();
        // java and backend and junior and pizza 100 => java backend junior pizza 100 로 변환
        String[] queries = query.replace(" and", "").split(" ");
        Node tmp = root;
        int target = Integer.parseInt(queries[queries.length - 1]);
        int scoreCnt = 0;

        q.add(tmp);

        while(!q.isEmpty()) {
            Node curNode = q.poll();

            if(Objects.isNull(curNode)) continue;

            // 말단 노드
            if(curNode.isLeaf) {
                // 말단 노드가 갖는 지원자 리스트 정렬을 한 번도 안함
                if(!curNode.isSorted) {
                    curNode.setIsSorted();
                }

                // 말단 노드가 갖는 리스트에서 이분 탐색을 통해서 점수 이상의 사람을 구함
                scoreCnt += binarySearch(curNode.scores, target);
                continue;
            }

            String keyword = queries[curNode.level];

            if(keyword.equals("-")) {
                // - 는 모든 조건이기 때문에 현재 노드가 갖는 모든 자식을 탐색 범위에 추가 ex) - -> backend / frontend 노드들
                q.addAll(curNode.children.values());
            } else {
                // query 가 요구하는 조건에 해당하는 자식 노드 반환 ex) backend -> backend 노드
                q.add(curNode.children.get(keyword));
            }
        }

        return scoreCnt;
    }

    /**
     * 이분 탐색을 통해 특정 점수 이상을 갖는 사람의 수를 구한다.
     * @param scores 트라이 말단 노드가 갖고있는 점수 리스트
     * @param target 기준 점수
     * @return 조건에 해당하는 사람 수
     */
    public int binarySearch(List<Integer> scores, int target) {
        int l = 0;
        int r = scores.size() - 1;

        while(l <= r) {
            int mid = (l + r) / 2;

            if(scores.get(mid) >= target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return scores.size() - l;
    }

    /**
     * 지원자들을 Trie 구조의 노드로 변환 및 삽입
     * @param info 지원자 정보 ex) java backend junior pizza 150
     */
    public void insert(String info) {
        Node tmp = root;
        st = new StringTokenizer(info);

        for(int i = 0; i < 4; i++) {
            String key = st.nextToken();
            int level = i + 1;

            // 아직 노드가 만들어지지 않았다면 노드 생성
            tmp = tmp.children.computeIfAbsent(key, k -> new Node(level));
        }

        // 위 반복문에서 4번 실행했기 때문에 st.nextToken() 는 점수에 해당하고, 마지막 노드라는 의미
        tmp.setIsLeaf(Integer.parseInt(st.nextToken()));
    }
}

 

---

[ 📌 전체 코드 - Java ]

/**
 * Author    : Lee In Bok
 * Date      : 2024.11.27(Wed)
 * Runtime   : 728.57 ms
 * Memory    : 258 MB
 * Algorithm : Trie, Binary Search, Graph Search
 */

package com.Week26.LV2_72412;

import java.util.*;

public class LV2_72412 {
    public static void main(String[] args) {
        Solution sol = new Solution();

        System.out.println(
                Arrays.toString(sol.solution(
                        new String[]{"java backend junior pizza 150", "python frontend senior chicken 210", "python frontend senior chicken 150", "cpp backend senior pizza 260", "java backend junior chicken 80", "python backend senior chicken 50"},
                        new String[]{"java and backend and junior and pizza 100", "python and frontend and senior and chicken 200", "cpp and - and senior and pizza 250", "- and backend and senior and - 150", "- and - and - and chicken 100", "- and - and - and - 150"}
                ))
        );
    }

    static class Solution {
        public int[] solution(String[] info, String[] query) {
            Trie trie = new Trie();
            List<Integer> ans = new ArrayList<>();

            // Trie 구조 생성
            for(String result: info) {
                trie.insert(result);
            }

            // Query 질의에 해당하는 결과 반환
            for(String term: query) {
                ans.add(trie.find(term));
            }

            return ans.stream().mapToInt(Integer::intValue).toArray();
        }
    }

    static class Trie {
        Node root = new Node(0);  // 루트 노드
        StringTokenizer st;

        /**
         * BFS 를 통해서 Trie 자료 구조 탐색
         * @param query 질의문 ex) java and backend and junior and pizza 100
         * @return query 조건을 만족하는 지원자 수 반환
         */
        public int find(String query) {
            Queue<Node> q = new LinkedList<>();
            // java and backend and junior and pizza 100 => java backend junior pizza 100 로 변환
            String[] queries = query.replace(" and", "").split(" ");
            Node tmp = root;
            int target = Integer.parseInt(queries[queries.length - 1]);
            int scoreCnt = 0;

            q.add(tmp);

            while(!q.isEmpty()) {
                Node curNode = q.poll();

                if(Objects.isNull(curNode)) continue;

                // 말단 노드
                if(curNode.isLeaf) {
                    // 말단 노드가 갖는 지원자 리스트 정렬을 한 번도 안함
                    if(!curNode.isSorted) {
                        curNode.setIsSorted();
                    }

                    // 말단 노드가 갖는 리스트에서 이분 탐색을 통해서 점수 이상의 사람을 구함
                    scoreCnt += binarySearch(curNode.scores, target);
                    continue;
                }

                String keyword = queries[curNode.level];

                if(keyword.equals("-")) {
                    // - 는 모든 조건이기 때문에 현재 노드가 갖는 모든 자식을 탐색 범위에 추가 ex) - -> backend / frontend 노드들
                    q.addAll(curNode.children.values());
                } else {
                    // query 가 요구하는 조건에 해당하는 자식 노드 반환 ex) backend -> backend 노드
                    q.add(curNode.children.get(keyword));
                }
            }

            return scoreCnt;
        }

        /**
         * 이분 탐색을 통해 특정 점수 이상을 갖는 사람의 수를 구한다.
         * @param scores 트라이 말단 노드가 갖고있는 점수 리스트
         * @param target 기준 점수
         * @return 조건에 해당하는 사람 수
         */
        public int binarySearch(List<Integer> scores, int target) {
            int l = 0;
            int r = scores.size() - 1;

            while(l <= r) {
                int mid = (l + r) / 2;

                if(scores.get(mid) >= target) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }

            return scores.size() - l;
        }

        /**
         * 지원자들을 Trie 구조의 노드로 변환 및 삽입
         * @param info 지원자 정보 ex) java backend junior pizza 150
         */
        public void insert(String info) {
            Node tmp = root;
            st = new StringTokenizer(info);

            for(int i = 0; i < 4; i++) {
                String key = st.nextToken();
                int level = i + 1;

                // 아직 노드가 만들어지지 않았다면 노드 생성
                tmp = tmp.children.computeIfAbsent(key, k -> new Node(level));
            }

            // 위 반복문에서 4번 실행했기 때문에 st.nextToken() 는 점수에 해당하고, 마지막 노드라는 의미
            tmp.setIsLeaf(Integer.parseInt(st.nextToken()));
        }
    }

    static class Node {
        Map<String, Node> children = new HashMap<>();
        List<Integer> scores;  // 마지막 노드만 갖는 리스트로 중간 노드들은 null 값을 갖고 있음
        int level;
        boolean isSorted = false;  // 리스트 정렬이 이미 되었는지
        boolean isLeaf = false;    // 마지막 노드인지

        public Node(int level) {
            this.level = level;
        }

        /**
         * 마지막 노드 표시
         * @param score 지원자의 점수
         */
        public void setIsLeaf(int score) {
            // 이미 마지막 노드인 경우 리스트에 값만 넣는다.
            if(isLeaf) {
                scores.add(score);
                return;
            }

            isLeaf = true;  // 마지막 노드 표시
            scores = new ArrayList<>();  // 리스트 처음 초기화
            scores.add(score);  // 초기화 된 리스트에 지원자 점수 넣기
        }

        /**
         * 리스트를 정렬하는 메소드
         * 플래그를 이용하는 이유는 매번 이분 탐색 실행시 정렬한다면 같은 노드에 대해서 정렬을 여러번
         * 실행할 수 있기 때문에 시간 초과 방지 (볼륨이 크기 떄문에 필수)
         */
        public void setIsSorted() {
            isSorted = true;
            Collections.sort(scores);
        }
    }
}

---

[ 📌 결과 - Java ]

[ 결과 - Java ]

---

[ 📌 마치며... ]

나는 문제를 풀이 하는데 3 시간 이상을 소요했다.....

코딩 테스트 전체 시간을 이 한 문제에 소비했으니 당연히 탈락 이겠지만 일단 풀었다는데 의의를 두기로 했다.

 

또 하나 문제는 이 문제는 IDE 에서 풀었다는 것인데, 적당한 난이도의 문제들은 IDE 도움 없이도 풀 수 있는데 코드 라인 수가 늘어가고, 복잡해지면 나는 IDE 에서 감당하기가 너무 힘들다......ㅠ