Min IT's Devlog

풀이 일자: 23.09.25 난이도: [Easy] 분류: [Hash Table/String/Bit Manipulation/Sorting] 문제 내용 s와 t가 주어졌을 때 s에서 1개의 letter을 추가로 넣고 섞었다고 했을 때 추가된 letter가 뭔지를 return하는 문제이다. ( 실제로는 s를 섞고 임의의 위치에 letter를 넣었다고 나오지만 편의상 넣고 섞었다고 보자) 문제 해결 흐름 1. 사실상 딱 봐도 Hash를 사용해야 하는 것이 자명하다. → 여러개의 알파벳이 중복해서 있을 수 있고 각각의 알파벳과 숫자를 모두 기억해두어야 하기 때문이다. 2. 그렇다면 s와 t중에서 뭐를 dictionary로 바꾸고 나머지를 순회해가면서 비교할지 결정해야 한다. → 나라면 s를 dictionary로 ..

풀이 일자: 23.07.03 난이도: [Easy] 분류: [Hash] 문제 내용 2개의 string이 주어지고 s에서 2 문자의 자리를 바꿨을 때 goal이 될 수 있는지 리턴하는 문제이다. 문제 해결 흐름 1. 일단 불가능한 경우과 가능한 경우가 있을텐데 불가능한 경우의 경우의 수가 훨씬 많을 것이다. → 크게 나누면 len이 다른 경우, len이 같은데 들어가 있는 문자 수가 다른 경우, 자리를 바꾸더라도 불가능한 문자인 경우 이렇게 나눌 수 있을 것이다. class Solution: def buddyStrings(self, s: str, goal: str) -> bool: sc = Counter(s); gc = Counter(goal); if sc != gc: # 크기가 다르거나 문자의 갯수가 다른..

풀이 일자: 23.06.28 난이도: [Medium] 분류: [Shortest Path/ Bellman-Ford/ Dijkstra] 문제 내용 문제의 내용은 start부터 end까지 간다고 했을 때 가장 높은 weight를 가지고 있는 경로의 weight를 반환하는 문제이다. 문제 해결 흐름 1. 우선 하나의 노드에서 다른 노드로의 이동이기 때문에 BFS를 생각해보았다.(실패) class Solution: def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float: visited = list(); path = dict(); for i in range(len(edges..

풀이 일자: 23.06.01 난이도: [Medium] 분류: [BFS] 문제 내용 내용은 0과 1로 이루어진 배열이 주어졌을 때 (0,0)에서 (n-1,n-1)로 0만 밟으면서 이동할 때 최단 거리를 리턴하는 문제로 이동할 수 있는 범위는 edge와 맞닿아있는 총 8개의 면에 갈 수 있다. 문제 해결 흐름 1. 항상 이러한 배열과 최단거리의 조합은 BFS와 DFS 둘 중 하나를 떠올릴 수 있다. → 나는 BFS를 순회 알고리즘에서 매우 선호하기도 하고 DFS를 사용하기에는 BFS를 사용하는 것보다는 최단거리를 계산하기 부적합하다고 생각하여 BFS를 이용하여 문제를 해결했다. class Solution: def shortestPathBinaryMatrix(self, grid: List[List[int]])..

풀이 일자: 23.05.31 난이도: [Medium] 분류: [Hash] 문제 내용 문제의 내용은 사용자들이 지하철을 타고 내릴 때 걸리는 시간의 평균을 리턴하는 문제였다. 문제 해결 흐름 1. 이 문제를 해결하기 위해서 떠오를 만한 방법은 해시정도? → 그 이유는 지하철을 환승한다던가 여러 곳을 거쳐야 한다던가하는 일이 없고 정직하게 시작점과 끝점의 시간정보와 사용자 수에 대한 정보만 가지고 있다면 되기 때문이다. → 또한 해시를 사용할 수밖에 없는 것이 배열에서 startStation과 endStation의 인덱스를 찾아서 그 인덱스로 2D array에서 평균 시간을 리턴하고 체크인 체크아웃을 하기에는 시간이 너무 많이 걸리기 때문이다. → 따라서 이중 해시를 이용해서 문제를 해결해보았다. class..

풀이 일자: 23.05.22 난이도: [Medium] 분류: [Hash Table, Divide and Conquer, Sorting, Heap, Bucket Sort] 문제 내용 단순하게 숫자 배열이 주어졌을 때 상위 k개의 빈번하게 등장하는 수를 순서상관 없이 리턴하는 문제였다. Follow-up에서는 NLogN의 시간복잡도를 갖는 알고리즘으로 풀어보라고 했다. 문제 해결 흐름 1. 단순하게 생각해보면 dictionary 하나 만들어서 숫자 카운트하고 이를 value기준으로 sort해서 return하면 끝나겠다. class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: cnt = dict(); for i in range..

풀이 일자: 23.05.19 난이도: [Medium] 분류: [DFS, BFS, Union Find, Graph] 문제 내용 이번 문제는 undirected graph가 주어졌을 때 이 노드들을 A와 B그룹으로 나눌 수 있는지 여부를 리턴하는 문제로 각 A,B 내부의 노드끼리는 연결되어 있지 않아야 한다. A와 B는 연결되어 있어도 상관없다. 문제 해결 흐름 1. 처음에는 Graph문제이고 A와 B그룹으로 나눌 수 있기 때문에 Union-Find를 떠올렸다. → 가능은 하겠지만 좀더 쉬운 방법을 떠올리고자 했다 2. A그룹과 B그룹을 나누고 같은 그룹의 노드들이 서로 인접하면 안되기 때문에 노드를 색칠하는 문제로 생각해도 되겠다는 생각을 할 수 있다. → BFS를 이용하여 각 level별로 같은 색으로 ..

풀이 일자: 23.05.18 난이도: [Medium] 분류: [Graph] 문제 내용 문제의 내용은 0 ~ N-1까지의 노드가 있는 순환이 없는 graph가 주어졌을 때 모든 노드에 접근하는 것이 목표이다. 최소한의 시작점을 사용하여 위와 같은 목표를 달성할 때 그 때의 시작점들의 집합을 리턴하는 것이 목표이다. 문제 해결 흐름 1. 처음에는 Union-Find를 생각해보았지만 그래프가 방향성이 있는 그래프이고 모두 합쳐져 있어서 부적합하다. → Union-Find는 Pass 2. 그래프를 직접 순회해가면서 각 노드가 접근할 수 있는 노드들의 집합을 구하는 것이 어떨까? → 가능은 하지만 시간이 오래 걸릴 것이다. 이는 cycle이 존재할 수 있어 이에 대한 처리가 필요하고 각 시작점에서 접근가능한 노드..

풀이 일자: 23.05.17 난이도: [Medium] 분류: [Linked List, Two Pointers, Stack] 문제 내용 오늘의 문제는 LinkedList가 주어졌을 때 i번째 노드와 n-1-i번째 노드를 twin이라고 했을 때 여러 twin들이 등장할 텐데 이 twin내의 노드값의 합이 최대가 되는 값을 리턴하는 문제이다. 문제 해결 흐름 1. 가장 간단하게 array에 값을 저장해놓고 값을 확인했다. class Solution: def pairSum(self, head: Optional[ListNode]) -> int: arr = list(); while head: arr.append(head.val); head = head.next; ans = 0; n = len(arr) for i i..

풀이 일자: 23.05.16 난이도: [Medium] 분류: [Linked List] 문제 내용 문제의 내용은 주어진 LinkedList를 홀수번 째 있는 노드와 짝수번 째 노드의 앞뒤를 바뀌는 문제이다. 문제 해결 흐름 1. 단순히 LinkedList의 자료구조 문제이기 때문에 그냥 풀면 된다. class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: node = head; i = 1; pprev = None; prev = None; h = None; if node == None or node.next == None: return node; while node: if i & 1: prev = node; nod..