CodeDrive

문제:

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

출력:

첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

풀이방법:

이 문제는 다른 방법을 사용하면 쉽게 풀 수 있겠지만, 트라이 자료구조를 활용해서 풀어보았다. 생각보다 시간제한이 어려웠던 문제라서 최대한 시간을 줄이고자, Node를 정의해서 풀었던 다른 문제들과는 달리 하나의 class만으로 해결해보도록 구성해보았다.

class Trie(object):
    @classmethod
    def __init__(self):
        self.root = {}
        self.terminate = 'eof'
        
    @classmethod
    def insert(self, string):
        currNode = self.root
        for chr_ in string:
            if chr_ not in currNode:
                currNode[chr_] = {}
            currNode = currNode[chr_]
        currNode[self.terminate] = string
        
    @classmethod
    def search(self,string):
        currNode = self.root
        for chr_ in string:
            if chr_ in currNode:
                currNode = currNode[chr_]
            else:
                return False
        if 'eof' in currNode.keys():
            return True
        else:
            return False

n, m = map(int,input().split())
T = Trie()
for _ in range(n):
    T.insert(input())
answer = 0
for _ in range(m):
    if T.search(input()):
        answer+=1
        
print(answer)

문제링크:

https://www.acmicpc.net/problem/14425

문제:

개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠)  일을 하네.

개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네.

한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들!

우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다.

행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.

로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다.

이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.

로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. (로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.)

다음은 로봇 개미들이 윤수에게 보내준 정보다.

• KIWI BANANA
• KIWI APPLE
• APPLE APPLE
• APPLE BANANA KIWI

(공백을 기준으로 왼쪽부터 순서대로 로봇 개미가 각 층마다 지나온 방에 있는 먹이 이름을 뜻한다.)

윤수는 로봇 개미들이 보내준 정보를 바탕으로 다음과 같이 개미굴의 구조를 손으로 그려봤다.

APPLE
--APPLE
--BANANA
----KIWI
KIWI
--APPLE
--BANANA

(개미굴의 각 층은 "--" 로 구분을 하였다.

또 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.)

우리의 천재 공학자 윤수는 복잡한 개미굴들을 일일이 손으로 그리기 힘들어 우리에게 그려달라고 부탁했다.

한치 앞도 모르는 험한 이세상 그렇지만 오늘도 행복한 개미들!

행복의 비결을 알기 위해 윤수를 도와 개미굴이 어떤 구조인지 확인해보자.

입력:

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다.  (1 ≤ N ≤ 1000)

두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정보 개수 K가 주어진다. (1 ≤ K ≤ 15)

다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보이며 먹이 이름 길이 t는 (1 ≤ t ≤ 15) 이다. 

출력:

개미굴의 시각화된 구조를 출력하여라.

개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.

풀이방법:

문자열 알고리즘 중 효율성이 가장 좋은 트라이(Trie) 알고리즘을 사용해서 입력받는 문자열을 정리하고, 별도의 탐색없이 지정된 출력형식으로 출력하면 되기 때문에, 재귀를 사용해서 문제에서 요구하는 방식대로 출력하도록 한다.

class Node(object):
    def __init__(self,name,flag=False):
        self.parent = name
        self.terminate = flag
        self.child = {}
        
    def __str__(self):
        return self.parent
        
class Trie(object):
    @classmethod
    def __init__(self):
        self.root = Node(None)
        
    @classmethod
    def insert(self, food):
        currNode = self.root
        for f in food:
            if f not in currNode.child:
                currNode.child[f] = Node(f)
            currNode.terminate = False
            currNode = currNode.child[f]
        currNode.terminate = True
        
    @staticmethod
    def antPrint(curNode,count):
        currList = sorted(list(curNode.child))
        for curr in currList:
            print("-"*count*2,end='')
            print(curNode.child[curr])
            Trie.antPrint(curNode.child[curr],count+1)

n = int(input())
T = Trie()
for _ in range(n):
    list_ = input().split()
    m, foods = list_[0], list_[1:]
    Trie.insert(foods)
Trie.antPrint(Trie.root,0)

문제링크:

https://www.acmicpc.net/problem/14725

문제:

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자.

- 긴급전화 : 911

- 상근 : 97 625 999

- 선영 : 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력:

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1<=t<=50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1<=n<=10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화 번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력:

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

풀이방법:

 이전에 프로그래머스에서 이 문제를 풀었었지만, 그 때에는 단순히 반복문을 사용해서 풀었다면 이번에는 문자열에서 비교하는 자료구조인 Trie를 사용하도록 한다.

 정보를 담을 Node 클래스와 이 Node들로 이루어진 Trie 클래스를 사용한다. Node의 key에는 알파벳, char 하나의 값이 들어가고, terminate는 이 Node가 마지막인지, 즉 string의 마지막인지를 나타내는 boolean 값이다. children은 더 이동할 수 있는 곳을 나타낸다.

 함수로는 insert와 search 두 개가 있다. insert로 전화번호를 넣어주고 search로 일관성을 파악하도록 한다.

문제링크:

https://www.acmicpc.net/problem/5052