프로그래머스(사이클 제거, 가사 검색) - Java

[사이클 제거]

https://programmers.co.kr/learn/courses/30/lessons/49188

프로그래머스

 

* 조건

1. 1~N까지의 노드가 존재한다
2. 노드간의 연결된 간선(edges[][])가 주어진다 (무방향)
3. 주어진 그래프에서는 반드시 하나 이상의 사이클이 존재한다
4. 노드를 딱 하나 제거해서 그래프가 사이클이 없도록 만들 수 있다면 해당 노드의 번호를 누적한 합을 출력한다

 

 

* 로직

• 효율성을 만족시키지 못했다. 일단은 정확성을 만족한 로직에 대해 먼저 작성하고 다시 시도해보려한다
• 크루스칼 알고리즘을 사용한다
• 가중치는 모두 1이라고 생각하고, 노드를 1~N까지 하나씩 뺐을 때의 경우를 고려한다
• 만약 크루스칼 알고리즘 진행중에 사이클이 형성된 곳이 없다면 -> 해당 노드를 누적한다
• 사이클이 형성되었다면 -> 다음번 노드를 제거한 경우를 고려한다

 

class Edge_RemoveCycle {
    public int v1, v2;

    public Edge_RemoveCycle(int v1, int v2) {
        this.v1 = v1;
        this.v2 = v2;
    }
}

public class Problem_RemoveCycle {

    static int[] parent;

    public static void main(String[] args) {
        int n = 8;
        int[][] edges = {
//                {1,2}, {1,3}, {2,3}, {2,4}, {3,4}
                {1,2}, {2,3}, {3,4}, {4,5}, {5,6},{6,7},{7,8},{8,1},{2,7},{3,6}
        };

        int answer = solution(n, edges);
        System.out.println(answer);
    }

    public static int solution(int n, int[][] edges) {
        int answer = 0;
        Edge_RemoveCycle[] edgesInfo = new Edge_RemoveCycle[edges.length];

        for(int i=0; i<edges.length; ++i){
            edgesInfo[i] = new Edge_RemoveCycle(edges[i][0], edges[i][1]);
        }

        //노드 1~n까지 하나씩 제거했을 때 사이클이 생기는지 안생기는지
        for(int node=1; node<=n; ++node){
            initParent(n);
            boolean find = false;

            for(Edge_RemoveCycle edge : edgesInfo){
                if(edge.v1 == node || edge.v2 == node) continue;

                if(!isSameParent(edge.v1, edge.v2)){
                    union(edge.v1, edge.v2);
                }

                else {
                    find = true;
                    break;
                }
            }

            if(!find) {
                answer += node;
            }
        }

        return answer;
    }

    private static boolean isSameParent(int v1, int v2) {
        v1 = findParent(v1);
        v2 = findParent(v2);

        if(v1 == v2) return true;
        return false;
    }

    private static int findParent(int v) {
        if(parent[v] == v) return v;
        return parent[v] = findParent(parent[v]);
    }

    private static void union(int v1, int v2) {
        v2 = findParent(v2);
        parent[v2] = v1;
    }

    private static void initParent(int n) {
        parent = new int[n+1];
        for(int i=1; i<=n; ++i){
            parent[i] = i;
        }
    }
}

 

 

---

[가사 검색]

https://programmers.co.kr/learn/courses/30/lessons/60060

프로그래머스

 

* 조건

1. 가사가 주어진다(words)
2. 검색 키워드가 주어진다(queries)
3. 오직 알파벳 소문자로만 구성되어있다
4. queries에는 와일드 카드인 ?가 존재한다 (접두사 or 접미사로 구성된다)
5. 와일드 카드가 포함된 queries에 포함되는 가사의 개수를 출력한다

 

* 알고리즘

• 트라이 알고리즘

 

* 로직

• 주어진 가사를 트라이 형태로 구성한다
  • 같은 글자 수의 문자들을 하나의 트라이로 만든다 (정방향)
  • 문자를 넣어줄 때, 각 글자마다 사용된 횟수를 카운팅한다
  • 와일드 카드(?)가 접두사로 사용된 경우를 고려해 거꾸로 뒤집은 문자를 보관하는 트라이를 구성한다 (역방향)
    (위에서 만든 트라이와 같은 방식이다)
• 주어진 검색 키워드가
  • 끝 글자가 ? 라면 접미사로 사용된 경우이다
    => 정방향 트라이에서 문자를 검색한다
    => 다음 글자가 ?가 나온다면 현재 위치한 글자가 사용된 횟수를 리턴한다
    => 만약 글자가 존재하지 않는다면 0을 리턴한다
    
    
  • 그렇지 않다면 접두사로 사용된 경우이다
    => 역방향 트라이에서 문자를 검색한다
    => 다음 글자가 ?가 나온다면 현재 위치한 글자가 사용된 횟수를 리턴한다
    => 만약 글자가 존재하지 않는다면 0을 리턴한다
    
    
  • 또한, 모든 검색 키워드가 ?인 경우를 고려해야한다
    => 끝 글자가 ?인 상황, 정방향 트라이를 탐색하는 과정에서 맨 첫 글자가 ?인 경우에는 root의 개수를 출력하면 현재 글자 수에 존재하는 모든 단어의 개수를 리턴해줄 수 있다
• 답을 출력한다

 

import java.util.ArrayList;

class Trie_SearchLyrics {
    Node_SearchLyrics root;

    public Trie_SearchLyrics() {
        this.root = new Node_SearchLyrics(' ');
        root.usedCnt = 0;
    }

    public void insert(String words) {
        Node_SearchLyrics current = root;
        current.usedCnt++;

        for(int i=0; i<words.length(); ++i){
            char ch = words.charAt(i);
            int index = ch - 'a';

            if(current.child[index] == null){
                current.child[index] = new Node_SearchLyrics(ch);
            }
            else {
                current.child[index].usedCnt++;
            }
            current = current.child[index];
        }
    }

    public int search(String query){
        Node_SearchLyrics current = root;

        for(int i=0; i<query.length(); ++i){
            char ch = query.charAt(i);
            int index = ch - 'a';

            //?인 경우 -> 현재 위치에서 글자 개수 출력
            if(ch == '?') return current.usedCnt;

            //단어가 존재한다면 해당 단어로 이동
            if(current.child[index] != null) current = current.child[index];

            //query의 단어가 존재하지 않는다면 0을 리턴
            else if(current.child[index] == null) return 0;
        }

        //? 표기 없이 전체 단어로 다 돌았을 때 -> 마지막 단어에서 리턴(이 문제에서는 상관 없음)
        return current.usedCnt;
    }
}

class Node_SearchLyrics {
    public char word;
    public Node_SearchLyrics[] child;
    public int usedCnt;

    public Node_SearchLyrics(char word) {
        this.word = word;
        this.child = new Node_SearchLyrics[26];
        this.usedCnt = 1;
    }
}

public class Problem_SearchLyrics {

    static Trie_SearchLyrics[] tries = new Trie_SearchLyrics[10001];
    static Trie_SearchLyrics[] tries_reversed = new Trie_SearchLyrics[10001];

    public static void main(String[] args) {
        String[] words = {"frodo", "front", "frost", "frozen", "frame", "kakao"};
        String[] queries = {"fro??", "????o", "fr???", "fro???", "pro?"};

        int[] answer = solution(words, queries);
        for(int ans : answer)
            System.out.print(ans + " ");
    }

    public static int[] solution(String[] words, String[] queries) {
        int[] answer = {};

        //주어진 단어를 트라이 형태로 정렬
        //단어 개수별로 트라이 정렬 (정방향, 역방향)
        for(String word : words){
            int size = word.length();
            if(tries[size] == null){
                tries[size] = new Trie_SearchLyrics();
            }
            tries[size].insert(word);

            //역방향으로도 트라이 정렬
            StringBuilder sb = new StringBuilder(word);
            String wordReversed = sb.reverse().toString();

            if(tries_reversed[size] == null) tries_reversed[size] = new Trie_SearchLyrics();
            tries_reversed[size].insert(wordReversed);
        }


        //질문에 대한 처리과정
        ArrayList<Integer> answers = new ArrayList<>();
        for(String query : queries){
            int size = query.length();

            //만약에 뒤에 ?가 있다면 -> 해당 단어 개수에 맞는 트라이로 가서 검색
            if(query.charAt(query.length()-1) == '?'){
                if(tries[size] == null) answers.add(0);
                else {
                    int tmp = tries[size].search(query);
                    answers.add(tmp);
                }
            }

            //앞에 ?가 있다면 -> 해당 단어 개수에 맞는 트라이로 가서 검색
            else {
                StringBuilder sb = new StringBuilder(query);
                String queryReversed = sb.reverse().toString();

                if(tries_reversed[size] == null) answers.add(0);
                else {
                    int tmp = tries_reversed[size].search(queryReversed);
                    answers.add(tmp);
                }
            }
        }

        answer = new int[answers.size()];
        for(int i=0; i<answer.length; ++i){
            answer[i] = answers.get(i);
        }

        return answer;
    }
}

 

 

트라이를 글자 개수에 따라 배열로 관리한다는 방법과, 접두사 접미사의 특성을 고려해 문자 역순으로도 관리하는 방법에 대해 깊은 인상을 받았다. 꼭 하나의 트라이로만 관리할 필요가 없었는데... 분류시키는 방법과 아이디어를 계속해서 습관화시켜야겠다.