99클럽 TIL (240814)
> [Middler] 대충 만든 자판
https://school.programmers.co.kr/learn/courses/30/lessons/160586#
문제풀이 과정
keymap의 키들을 조작하여 targets의 각각의 문자열들을 만들어야 한다. 이때 최소값을 구해야 한다. 그래서 targets 배열을 순회하면서 원소인 target 길이만큼 거리 배열 (d)을 생성하여 최솟값을 기록했다. dfs로 생각해 문제를 해결했다.
문제풀이
python
def solution(keymap, targets):
ans = []
# 아이디어 정리
# bfs->큐, dfs->스택
# targets 길이만큼 반복한다.
# targets의 원소 중 i번째 문자를 stack에 넣는다. stack을 꺼내어 keymap의 원소들 중 일치하는 인덱스를 찾는다.
# 찾은 인덱스 값이 0보다 크고 이전에 찾은 값보다 더 작은 값이라면 d에 기록한다.
# keymap을 돌면서 최솟값을 리턴한다.
# 리턴값을 저장한다.
def dfs(target, start) :
stack = []
stack.append(target[start])
d = [int(1e9)] * len(target)
sum = 0
while stack :
now = stack.pop()
for i, k in enumerate(keymap) :
isAvail = k.find(now) + 1
if isAvail > 0 :
d[start] = min(d[start], isAvail)
if start < len(target)-1 :
stack.append(target[start+1])
start+= 1
for i in d :
if i != int(1e9) :
sum += i
else :
return -1
return sum
for i, t in enumerate(targets) :
cnt = int(1e9)
ans.append(dfs(t, 0))
return ans
javascript
굳이 스택을 사용하지 않고 좀더 간결하게 작성해보았다.
function dfs(keys, t, start, d) {
while (start < t.length) {
now = t[start]
for(let i=0 ;i<keys.length; i++){
let isAble = [...keys[i]].findIndex((i)=>i===now)+1;
if(isAble > 0) {
d[start] = Math.min(d[start], isAble)
}
}
start += 1
}
return d.findIndex(i=>i===1e9) > -1 ? -1 : d.reduce((total, num)=>total+num)
}
function solution(keymap, targets) {
var answer = [];
// dfs를 targets 배열 길이만큼 돌린다.
// targets 원소들의 길이만큼 최소 이동횟수를 담는다.
for (let i=0 ; i<targets.length; i++) {
d = Array.from({length : targets[i].length}, ()=>1e9)
answer.push(dfs(keymap, targets[i], 0, d))
}
return answer;
}
시간복잡도 O(N^2)
targets, keymap이 100이하 배열
오늘의 회고 및 느낀점
지금생각해보니, 최소값이기 때문에 다익스트라 알고리즘으로도 풀수 있나라고 생각이 든다. 더 효율적인 코드에 대해서 고민해보자.
> [Beginner] Find Center of Star Graph
https://leetcode.com/problems/find-center-of-star-graph/description/
문제 풀이 과정
우선 주어진 edges 배열을 통해 모든 노드들과 연결되어 있는 노드를 고르면 된다. 문제를 읽었을 때, '인접 리스트'를 생각했다. 주어지는 edges는 위 그림과 같은 star graph 형태를 띄고 있다. 그렇기 때문에 주어지는 간선 배열의 길이 + 1인 만큼의 노드를 가지고 있다.
* 인접리스트 : 그래프의 각 정점(노드)마다 연결된 노드들의 정보를 저장하는 방식
1. 노드의 수만큼 배열을 만든다.
2. edges를 순회하면서 인접리스트를 만든다.
3. 저장된 인접리스트 중 edges와 길이가 같은 노드를 반환
문제 풀이
python
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
# 인접리스트를 그려본다.
arr = [ [] for _ in range(len(edges)+2) ]
for i in edges :
arr[i[0]].append(i[1])
arr[i[1]].append(i[0])
for i, v in enumerate(arr) :
if len(v) >= len(edges) :
return i
return 0
javascript
생각해보니 별의 중앙에 있는 노드는 연결된 노드의 수, 즉 간선의 개수가 edges 의 길이와 같을 수 밖에 없다. 이를 활용해 js에서 코드를 좀더 간결하게 작성해보았다.
var findCenter = function(edges) {
nodes = Array.from({length : edges.length + 2}, ()=> 0)
for (let i=0; i<edges.length ;i++){
nodes[edges[i][0]] += 1
nodes[edges[i][1]] += 1
}
return nodes.findIndex(i=>i===edges.length);
};
시간복잡도 O(V)
회고 및 느낀점
그래프 탐색 로직은 코테에 자주 출제되니 더 기본기를 익혀두는 것이 좋겠다
> [Challenger] 가장 먼 노드
https://school.programmers.co.kr/learn/courses/30/lessons/49189?language=python3
문제 풀이 과정
이 문제는 시작노드 1로부터 가장 먼 노드의 개수를 구하면 되는 문제이다. 내 생각의 흐름은 이렇다.
1. 시작노드로부터 거리를 모두 센다.
2. 거리가 가장 먼 노드들의 개수를 모두 센다.
이를 구현하기 위해 큐 라이브러리인 deque를 사용했다.
문제 풀이
python
from collections import deque
def solution(n, edge):
arr = [[] for _ in range(n+1)]
d = [int(1e9)] * (n+1)
for i in edge :
arr[i[0]].append(i[1])
arr[i[1]].append(i[0])
q = deque([1])
d[1] = 0
while q :
now = q.popleft()
for i in arr[now] :
if d[i] == int(1e9) :
q.append(i)
d[i] = d[now] + 1
max_val = 0
for i in range(1, n+1) :
max_val = max(max_val, d[i])
ans = 0
for i in range(1, n+1) :
if d[i] >= max_val : ans += 1
return ans
시간복잡도 O(V)
한번 방문한 노드는 거리가 갱신되기 때문에 각 노드는 한번씩만 큐에 적재된다.
회고 및 느낀점
파이썬스럽게 코드를 짜는 게 어렵다. 그래도 lv3 이라 못풀줄 알았는데 풀어서 뿌듯했다 ㅎ__ㅎ