Min IT's Devlog

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

풀이 일자: 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.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..

풀이 일자: 23.04.14 난이도: [Medium] 분류: [DP] 문제 내용 s가 주어졌을 때 해당 s의 subsequence 중 가장 긴 회문의 길이를 구하는 문제이다. subsequences > 0개 이상의 원소를 삭제함으로써 반들어지는 substring으로 보면 된다. 회문 > 앞으로 읽어도 뒤로 읽어도 똑같은 것을 의미한다. ex)기러기.. 문제 해결 흐름 1. 처음 이 문제를 보고 떠오르는 알고리즘은 two-pointer나 DP정도뿐이었다. → 그 이유로는 전체를 일단 쪼개서 작은 것부터 처리하고 점차 붙여나가면서 답을 만들어가는 해결방식뿐이었다. dp[i][j] = i ~ j번째의 문자를 이용하여 만들 수 있는 최대 회문의 크기 dp[i][i] = i ~ i번째의 문자를 이용하여 만들 수 ..

풀이 일자: 23.04.12 난이도: [Medium] 분류: [String, Stack] 문제 내용 절대경로를 간단한 캐노니컬 경로로 바꿔서 리턴하는 문제였다. 문제 해결 흐름 1. 가장 먼저 떠오른 방법은 path의 글자를 하나씩 읽어가면서 stack에 넣고 ..와 .에 따라 처리해주는 방법이었다. => 결과는 여러 경우의 수를 따져가면서 처리를 하나씩 해줬는데 실패였다. 이런 예외사항을 고려하면 다른 게 또 걸리고 그런 식이었다. 다른 방식을 생각해보자. 예외의 경우 /./..stack /hi///.././.. class Solution: def simplifyPath(self, path: str) -> str: ans = ['/']; dotCnt = 0; for s in path: if s == '..

풀이 일자: 23.04.06 난이도: [Medium] 분류: [Array, DFS, BFS, Union Find] 문제 내용 문제의 내용은 0(land), 1(water)로 이루어진 배열이 주어졌을 때 사면이 물로 둘러싸여있는 섬의 수를 구하는 문제였다. 문제 해결 흐름 1. 일단 가장 먼저 떠오른 방법은 Union-Find이긴 했다. → 1의 group과 0의 group으로 나눠질거고 0내부에서도 각 섬별로 grouping이 되는거니까 Union-Find로도 가능하다. 2. Union-Find는 간단하지만 더 쉬운 방법을 찾아볼 필요가 있다. DP나 DFS정도를 생각할 수 있겠다. → DP는 점화식을 뽑아야 하는데 그것보다는 더 쉬운 방법일 수 있는 DFS를 선택하자. 3. 우선 edge에 0이 등장한..

풀이 일자: 23.04.05 난이도: [Medium] 분류: [Array, Prefix Sum] 문제 내용 nums배열이 주어졌을 때 이는 n의 음수가 아닌 정수를 포함하고 있다. 이때 1~n-1의 인덱스를 골라 그 인덱스를 i번째라고 한다면 nums[i]는 1을 줄이고 nums[i-1]는 1을 증가시켜서 배열의 최댓값이 최소가 되도록 만드는 문제이다. 문제 해결 흐름 1. 최대한 Greedy하게 풀면 되지 않을까라는 생각을 해보았다. ( Fail to Solve) → 배열에서 가장 큰 값과 큰 값을 기준으로 왼쪽에 있는 값들중 가장 작은 값을 비슷하게 만들다보면 뭔가 평균에 수렴하지 않을까라는 생각에 기반하였다. 문제) -1 +1 응용) -1 +1 -1 +1 --------- -1 0 +1 => 위의 ..

풀이 일자: 23.04.04 난이도: [Medium] 분류: [Hash Table, String, Greedy] 문제 내용 s라는 문자열이 주어졌을 때 이를 여러 개의 subString으로 자른다고 했을 때 각각의 subString 내의 중복되는 문자가 unique하게 자를 때 최소한으로 나오는 subString의 갯수를 리턴하라는 문제이다. 문제 해결 흐름 1. 일단 가장 간단하게 생각하면 앞에서부터 탐색하면서 카운팅하면 되겠네. → 앞에서부터 array에 문자를 넣기 시작하다가 array내부에 있는 문자가 나오면 ans+=1을 하고 거기서부터 다시 나온 문자에 대해 history를 저장하면 되겠다. class Solution: def partitionString(self, s: str) -> int:..