Pori_IT

오늘의 학습 키워드:  탐색, BFS

문제: 촌수계산

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

풀이

촌수의 계산을 위해서 각 노드를 탐색하는 BFS를 이용해 풀이했습니다.

각 노드의 번호와 시작 노드로부터의 떨어진 거리를 담는 큐를 이용했고,
이미 방문한 노드에 재방문하지 않기 위해 visited를 사용했습니다.

import sys
from collections import deque
N = int(sys.stdin.readline().strip())

a, b = map(int,sys.stdin.readline().strip().split())

m = int(sys.stdin.readline().strip())

graph = []
for _ in range(m):
    tmp =  list(map(int,sys.stdin.readline().strip().split()))
    graph.append(tmp)

q = deque([])
q.append([a,0])
tk = 0
visited = []

while q:
    m,count = q.popleft()
    if m == b:
        print(count)
        tk = 1
        break
    else:
        for s,e in graph:
            if s == m and [s,e] not in visited:
                visited.append([s,e])
                q.append([e,count+1])
            elif e == m and [e,s] not in visited:
                visited.append([e,s])
                q.append([s,count+1])
if tk == 0:
    print(-1)

오늘의 학습 키워드:  탐색, DFS

문제: 모음사전

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

풀이

dfs를 이용해서 사전이 만들어지면서 내가 원하는 단어와 동일한 경우에 True를 반환하게 한다.

def solution(word):
    global answer
    alphabets = ['A','E','I','O','U']
    answer = 0
    
    def dfs(wd):
        global answer
        answer += 1
        if wd == word:
            return True
        
        if len(wd) == 5:
            return False
        
        for a in alphabets:
            if dfs(wd+a) == True:
                return True
    
    for a in alphabets:
        if dfs(a) == True:
            return answer

프로그래머스 SQL 문제도 다 풀었고 hackerrank로 넘어갑니다.

문제

https://www.hackerrank.com/challenges/the-pads/problem

풀이

우선 두 가지 방식으로 출력이 진행되어야 한다.

1. Name(A)와 같은 (직업 이니셜)의 형태가 포함된 출력 (ex. Ashely(P), Christeen(P))

주의할 점은 직업의 수가 4개만 존재한다는 것이다. [Doctor Professor Singer Actor]

SELECT concat(name,'(',substr(Occupation,1,1),')')  as name
FROM OCCUPATIONS
ORDER BY name;

간단하게 substr과 concat을 사용해서 만들어주면 된다.

2. There are a total of [occupation_count] [occupation] s. 의 형태로 직업의 count를 출력할 것.

여기서 주의할 점은 occupations가 기존에는 Doctor와 같이 첫 글자가 대문자이나 출력값에서는
모두 소문자로 출력해야 하는 점이다. (이 부분이 가장 어려웠다..)

WITH CTE2 AS (
    SELECT  count(*) as c, occupation
    FROM OCCUPATIONS
    GROUP BY Occupation
    ORDER BY 1 
)
, CTE3 AS (
    SELECT CONCAT('There are a total of ',c,' ',lower(occupation),'s.') as name
    FROM CTE2
)
SELECT name
FROM CTE3;

GROUP BY를 사용해서 각 직업별 count를 계산하고 이를 concat을 활용해서 문장의 형태로 만들어주었다.

오늘의 학습 키워드:  탐색

문제: 745. Prefix and Suffix Search

https://leetcode.com/problems/prefix-and-suffix-search/description/

풀이

갑자기 리트코드가 나와서 당황했지만..? 풀이를 진행했다.

class형태로 구현하도록 나와서 결과를 어떻게 받을 지 궁금했지만
그냥 단순하게 클래스 안에서 함수를 구현하고 리턴만 잘 해주면 되는거였다.

신경쓸 부분은 접두사와 접미사가 한 단어만 주어지는건 아니라는점, 시간 제한이 있다는 점이다.

초기에 틀린 코드를 보면 다음과 같이 풀었다.

class WordFilter:

    def __init__(self, words: List[str]):
        self.word_list = words

    def f(self, pref: str, suff: str) -> int:
        l_pref = len(pref)
        l_suff = len(suff)
        max_index = -1
        for idx in range(len(self.word_list)-1,-1,-1):
            word = self.word_list[idx]
            if word[:l_pref] == pref and word[-l_suff:] == suff:
                return idx
        return -1

이 코드는 조회 시 O(n*l)의 복잡도를 갖는다. 조회를 하는 경우에 시간을 많이 사용한다는 의미이다.

그래서 시간 초과가 나온 경우에 조회를 많이 하는 경우를 볼 수 있었는데 (L이 매우 커진다는 의미) 이로 인해서 발생한 것 같다.

따라서 시간 초과를 방지하기 위해 클래스 초기화 시에 값들을 해시로 넣는 방법을 채택했다.

class WordFilter:

	def __init__(self, words: List[str]):

		self.pair_suffix_prefix = {}

		for index in range(len(words)):

			for j in range(len(words[index])):

				new_word1 = words[index][:j+1]

				for k in range(len(words[index])):
					new_word2 = new_word1+'.'+words[index][k:]

					self.pair_suffix_prefix[new_word2] = index


	def f(self, prefix: str, suffix: str) -> int:

		search_word = prefix+'.'+suffix

		if search_word in self.pair_suffix_prefix:
			return self.pair_suffix_prefix[search_word]
		else:
			return -1

조회 시 해시에서 값을 찾기 때문에 O(1)의 시간복잡도를 갖는다.

물론 초기화 시에는 시간이 더 걸리지만 조회가 많다면 효율적인 코드가 된다.