파이썬 알고리즘 299번 | [백준 14426번] 접두사 찾기

299. 접두사 찾기

1) 어떤 전략(알고리즘)으로 해결?

• 본래 문제의도는 트라이, 이분 탐색 느낌입니다.
• 저는 어쩌다보니 startswith으로 해결했습니다.

2) 코딩 설명

<내 풀이>

(1) startswith : 시간복잡도 = 636ms

import sys
# 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)
N,M = map(int,sys.stdin.readline().rstrip().split())
s = []
m = []
for _ in range(N) :
    s.append((sys.stdin.readline().rstrip()))
for _ in range(M) :
    m.append((sys.stdin.readline().rstrip()))

answer = 0

for i in range(M) : 
    for j in range(N) :
        if s[j].startswith(m[i]):
            answer+=1
            break

print(answer)

(2) 해시테이블 느낌과 비슷하게 구현 :

• 이 부분은 블로그 로부터 알아냄 !

import string
import sys
# 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)
N,M = map(int,sys.stdin.readline().rstrip().split())
s = words = {x: [] for x in string.ascii_lowercase}
m = []

for _ in range(N) :
    word=(sys.stdin.readline().rstrip())
    s[word[0]].append(''.join(word))
for _ in range(M) :
    m.append((sys.stdin.readline().rstrip()))

answer = 0

for i in range(M) : 
    for j in s[m[i][0]] :
        if j.startswith(m[i]):
            answer+=1
            break

print(answer)

< 내 틀렸던 풀이, 문제점>

• 시간초과 (이중 FOR문)
  • 특히 문자열을 join 하는 과정에서 추가 시간 소요 추정

import sys

# 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)
N,M = map(int,sys.stdin.readline().rstrip().split())
s = []
m = []
for _ in range(N) :
    s.append(list(sys.stdin.readline().rstrip()))
for _ in range(M) :
    m.append(sys.stdin.readline().rstrip())

answer = 0

for i in range(M) : 
    for j in range(N) :
        if m[i]=="".join(s[j][0:len(m[i])]):
            answer+=1
            break

print(answer)

• 8프로 시간초과
  • 단순히 동등 비교만 해서 시간 조금은 단축

import sys

# 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)
N,M = map(int,sys.stdin.readline().rstrip().split())
s = []
m = []
for _ in range(N) :
    s.append(list(sys.stdin.readline().rstrip()))
for _ in range(M) :
    m.append(list(sys.stdin.readline().rstrip()))

answer = 0

for i in range(M) : 
    for j in range(N) :
        if m[i] == (s[j][0:len(m[i])]):
            answer+=1
            break

print(answer)

• 알고리즘 분류를 체크해보니 말로만 듣던 트라이 네요 !
• 한번 트리로 구현을 해보겠습니다. 사실 개념만 알고 있던 터라 해보고 모르겠으면 유튜브 강의를 보겠습니다.

startswith을 사용하니깐 되네요

• 그래도 다른 방식으로 푸는 법에 대해 알아보아야 겠습니다. 이중 for문 말고 다르게 풀 수 있는지 말이예요

<반성 점>

• 트라이 자료구조에 대한 미숙

<배운 점>

• startwith 함수

• 사전에 내가 원하는 키/value 값 설정 방법

  words = {x: [] for x in string.ascii_lowercase}
  => 'a':[], 'b':[] ,,, 같이 생성됩니다.

• 파이썬으로 트라이 구조 만들기

  트라이 블로그

import sys
read = sys.stdin.readline

# 아래의 Node, Trie class 구현 부분은
# [https://alpyrithm.tistory.com/74]
# 알파이님의 블로그를 토대로 작성했습니다.

class Node(object):
    # trie 자료구조를 위한 node
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        # dictionary 자료구조 사용
        self.children = {}

class Trie(object):
    def __init__(self):
        self.head = Node(None)

    # 문자열 삽입
    def insert(self, string):
        curr_node = self.head
        # 삽입할 string 각각의 문자에 대해 자식 Node를 만들며 내려간다.
        for char in string:
            # 자식 Node들 중 같은 문자가 없으면 Node 새로 생성
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            # 같은 문자가 있으면 해당 노드로 이동
            curr_node = curr_node.children[char]

        curr_node.data = string

    # 문자열이 존재하는지 search
    def search(self, string):
        curr_node = self.head

        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return False

        if curr_node.data != None:
            return True

n, m = map(int, read().split())

word_trie = Trie()
word_len = list(False for _ in range(501))
# 주어진 문자열과 길이가 같은 문자열에 대해서만 탐색을 진행해
# 시간복잡도 줄이기 위함

for _ in range(n):
    word = read().strip()
    word_trie.insert(word)
    word_len[len(word)] = True
cnt = 0
for _ in range(m):
    word = read().strip()
    if word_len[len(word)] and word_trie.search(word):
        cnt += 1

print(cnt)

---

• 파이썬으로 링크드 리스트 구조 만들기
  all code from here : Linked list Python
  1) 노드 구현

class ListNode:
    def __init__(self,val):
    	self.val = val
        self.next = None

    def __init__(self, val):
        self.val = val
        self.next = None

def printNodes(node:ListNode):
    crnt_node = node
    while crnt_node is not None:
        print(crnt_node.val, end=' ')
        crnt_node = crnt_node.next

class SLinkedList:
    def __init__(self):
        self.head = None
        
    def addAtHead(self, val): #O(1)
        node = ListNode(val)
        node.next = self.head
        self.head = node

    #but when the list
    def addBack(self, val): #O(n)
        node = ListNode(val)
        crnt_node = self.head
        while crnt_node.next:
            crnt_node = crnt_node.next
        crnt_node.next = node

    def findNode(self, val): #O(n)
        crnt_node = self.head
        while crnt_node is not None:
            if crnt_node.val == val:
                return crnt_node
            crnt_node = crnt_node.next
        raise RuntimeError('Node not found')

    def addAfter(self, node, val): #O(1)
        new_node = ListNode(val)
        new_node.next = node.next
        node.next = new_node

    def deleteAfter(self, prev_node): #O(1)
        if prev_node.next is not None:
            prev_node.next = prev_node.next.next