📙[Algo] 24.08.13 알고리즘

알고리즘 문제) BOJ 5052. 전화번호 목록

• 링크 : https://www.acmicpc.net/problem/5052

문제 요약

• 전화번호 목록이 주어질 때, 일관성 여부를 확인해라
• 일관성을 유지한다는 것은
  • 한 번호가 다른 번호의 접두어인 경우가 없어야 한다
  • 예를들어, 아래와 같이 존재한다면
    • 911
    • 91123
    • 911을 치자마자 바로 첫번째 전화로 걸려버리기 때문에 일관성이 없다

시간 제한

• 1초

입력

• 테스트 케이스 개수 t
  • 1 ≤ t ≤50
• 각 테케의 첫째줄에는 전화번호 수 n이 주어진다
  • 1 ≤ n ≤ 10000
• 다음 n개의 줄에는 목록에 포함된 전화번호가 한 줄씩 주어진다
  • 최대 10자리이며, 중복된 경우 X

출력

• 각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력

접근법

• 일관성이 없다
  • 즉, 특정 전화번호가 다른 전화번호와 시작이 같고, 포함되는 관계면 X
• 완전탐색으로 할 경우
  • 각 문자마다 다른 문자에 접두사도 같고, 포함되는지를 확인해야 하므로,
  • 테스트케이스별로 N * N * 문자열 길이 정도연산이 필요하므로
    • 최악의 경우 1_000_000_000 개 연산이 필요하다
  • 이때, 테스트케이스가 최대 50개까지 가능하므로 최종적으로 500억 연산이 필요하므로 최적화 필요
• 트라이 자료구조를 활용
  • 주어진 문자열을 트리구조로 저장(insert)한 다음 탐색(search)을 진행한다
    • 이때, 특정 문자열이 해당 트라이에 존재해도, 리프노드가 아닐 경우는 false를 반환하도로 했다
      ⇒  return curNode.child.isEmpty() && curNode.isEndOfWord;

코드

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

public class Main {

    static class Node{
        Map<Character, Node> child = new TreeMap<>();
        boolean isEndOfWord;
    }

    static class Trie{
        Node root;

        Trie() {
            this.root = new Node();
        }

        // 트라이 생성
        public void insert(String str) {
            Node curNode = this.root;

            char c;
            for (int i = 0; i < str.length(); i++) {
                c = str.charAt(i);

                curNode.child.putIfAbsent(c, new Node());

                curNode = curNode.child.get(c);
            }

            curNode.isEndOfWord = true;
        }

        // 특정 문자열 탐색
        public boolean search(String str) {
            Node curNode = this.root;

            char c;
            for (int i = 0; i < str.length(); i++) {
                c = str.charAt(i);

                if (curNode.child.containsKey(c)) {
                    curNode = curNode.child.get(c);
                } else {
                    return false;
                }
            }

            return curNode.child.isEmpty() && curNode.isEndOfWord;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        int N; String str; String[] list;
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());

            Trie trie = new Trie();
            list = new String[N];

            for (int i = 0; i < N; i++) {
                str = br.readLine();


                trie.insert(str);
                list[i] = str;
            }

            boolean ret = true;
            for (int i = 0; i < N; i++) {
                ret = trie.search(list[i]);

                if (!ret) break;
            }

            if (!ret) {
                sb.append("NO\n");
            } else {
                sb.append("YES\n");
            }
        }

        System.out.println(sb);
    }
}

 

알고리즘 문제) BOJ 5670. 휴대폰 자판

• 링크 : https://www.acmicpc.net/problem/5670

문제 요약

• 사전이 주어졌을 때, 아래 규칙을 사용하면서 각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하는 프로그램을 작성
• 규칙
  • 반드시 첫 글자는 사용자가 버튼을 눌러 입력
  • 만약 특정 글자 c1로 시작하는 단어의 다음 글자가 c2일 때, 사전에 존재하는 글자중 c1으로 시작하는 단어 다음에는 c2가 오는 경우밖에 없다면 자동으로 입력되지만, 그렇지 않다면 사용자가 직접 입력
• 예를 들면, 사전에 "hello", "hell", "heaven", "goodbye" 4개의 단어가 있고 사용자가 "h"를 입력하면 모듈은 자동으로 "e"를 입력해 준다.
  • 그러나 단어들 중 "hel"로 시작하는 것도, "hea"로 시작하는 것도 있기 때문에 여기서 모듈은 사용자의 입력을 기다린다.
  • 이어서 사용자가 "l"을 입력하면 모듈은 "l"을 자동으로 입력해 준다.
  • 그러나 여기서 끝나는 단어인 "hell"과 그렇지 않은 단어인 "hello"가 공존하므로 모듈은 다시 입력을 기다린다.
  • 사용자가 "hell"을 입력하기 원한다면 여기서 입력을 멈출 것이고, "hello"를 입력하기 원한다면 직접 "o" 버튼을 눌러서 입력해 줘야 한다.

시간 제한

• 1초

입력

• 각 테스트 케이스의 첫째 줄에 사전에 속한 단어의 개수 N이 주어지며(1 ≤ N ≤ 10^5)
• 이어서 N개의 줄에 1~80글자인 영어 소문자로만 이루어진 단어가 하나씩 주어진다.
  • 똑같은 단어는 두 번 주어지지 않는다.
  • 각 테스트 케이스마다 입력으로 주어지는 단어의 길이 총합은 최대 10^6

출력

• 각 테스트 케이스마다 한 줄에 걸쳐 문제의 정답을 소수점 둘째 자리까지 반올림하여 출력

접근법

• 사전에 주어진 단어들로 트라이 자료구조 생성
• 규칙에 따르면,
  • hello글자를 찾으려고 할 때
  • 첫 글자인 h는 무조건 입력해야한다.
  • 그 다음, h로 시작하는 단어의 다음 글자가 모두 e일 경우 e는 자동 입력된다.
    • 하지만, ho로 시작하는 단어가 존재한다면 e는 임력해야한다.
• 즉, 현재 가리키는 노드(글자)가 첫 글자이거나 해당 노드의 자식 노드 개수가 2개 이상인 경우에는 무조건 해당 글자를 입력해줘야 하므로 카운트 + 1
  ⇒ if (i == 0 || size > 1) cnt++;
• 또한, 특정 단어에 포함된 다른 단어가 존재할 경우, 더 긴 단어를 탐색할 때그 다음 글자를 입력해야한다.
  • 예를들어, hello와 hell이 있을 때, hello를 찾고 싶다면, 마지막에 o를 추가로 입력해줘야한다.
  • 따라서, 아직 단어 탐색이 끝나지 않았는데, 현재 노드가 가리키는 문자로 끝나는 단어가 존재한다면 카운트 + 1
    ⇒ if (curNode.isEndOfWord && !curNode.child.isEmpty()) cnt++;
• 참고로 문제에서 테스트 케이스 개수가 입력으로 주어지지 않기 때문에 try~catch로 감싸서 에러가 뜰 경우 결과를 출력하게 함

코드

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

public class Main {

    static class Node{
        Map<Character, Node> child = new TreeMap<>();
        boolean isEndOfWord = false;
    }

    static class Trie{
        Node root;

        Trie() {
            this.root = new Node();
        }

        public void insert(String str) {
            Node curNode = this.root;

            char c;
            for (int i = 0, len = str.length(); i < len; i++) {
                c = str.charAt(i);
                curNode.child.putIfAbsent(c, new Node());
                curNode = curNode.child.get(c);
            }

            curNode.isEndOfWord = true;
        }

        public double search(String str) {
            Node curNode = this.root;

            char c; int size; double cnt = 0;
            for (int i = 0, len = str.length(); i < len; i++) {
                c = str.charAt(i);

                size = curNode.child.size();

                if (i == 0|| size > 1) cnt++;
                else if (curNode.isEndOfWord && !curNode.child.isEmpty()) cnt++;

                curNode = curNode.child.get(c);
            }

            return cnt;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        try {
            int N;
            String str;
            String[] lst;
            double sum;
            while (true) {
                N = Integer.parseInt(br.readLine());

                Trie trie = new Trie();
                lst = new String[N];

                for (int i = 0; i < N; i++) {
                    str = br.readLine();
                    trie.insert(str);
                    lst[i] = str;
                }

                sum = 0;
                for (int i = 0; i < N; i++) {
                    sum += trie.search(lst[i]);
                }

                sb.append(String.format("%.2f", (sum / N))).append("\n");
            }
        } catch (Exception e) {
            System.out.println(sb);
        }
    }
}