Min IT's Devlog

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

풀이 일자: 23.04.02 난이도: [Medium] 분류: [Array, Two Pointers, Binary Search, Sorting] 문제 내용 문제의 내용은 정수가 담긴 2개의 배열이 주어지고 이 배열들 간의 이루어질 수 있는 원소들간의 곱이 success라고 하는 기준점 이상인 경우를 count해서 spells 기준으로 가능한 경우의 수를 리턴하는 문제이다. spells = [5,1,3], potions= [1,2,3,4,5], success = 7 spells = 5 => [5,10,15,20,25] # successful 횟수는 4 spells = 1 => [1,2,3,4,5] # successful 횟수는 0 spells = 3 => [3,6,9,12,15] # successful 횟수..

풀이 일자: 23.03.21 난이도: [Medium] 분류: [Array, Math] 문제 내용 문제 내용은 Array 하나 받아서 0으로만 이루어진 subarray가 몇 개 나오는지 리턴하는 문제였다. 문제 해결 흐름 1. 딱히 생각나는 알고리즘이 없다. 열심히 처음부터 정직하게 탐색해서 0의 위치만 확인하면 되겠다. → Linear Search하다가 0이 보이기 시작하면 0에 대한 count를 시작한다. 0이 나오다가 다른 게 나오면 수학적 계산 예를 들어, [0,0,0,0]이 연달아 4번 나왔다고 하자.. [0]인 subgroup이 4개 [0,0]인 subgroup 3개 ..... [0,0,0,0]인 subgroup이 1개. => 결과적으로 n개의 0이 연달아 나오는 경우 n(n+1)/2개의 sub..

풀이 일자: 22.08.18 난이도: [Medium] 문제 내용 주어진 integer array를 가지고 해당 array의 length를 반 이하로 줄일 때 최소한의 빼야하는 숫자의 개수에 대한 문제였다. arr = [3,3,3,3,5,5,5,2,2,7] → 이런식으로 주어졌을 때 3과 7을 뺀다면 남는 array는 [5,5,5,2,2]가 되게 되면서 기존의 1/2가 되게 된다. 문제 해결 흐름 1. 우선 중복되는 수를 몇 개씩 있는지 check를 해야겠다. → Dictionary를 이용하여 각각 몇개씩 있는지 세자. 2. 어떤 원소를 빼야 하는지가 아니라 최소한 빼야하는 원소의 개수에 대한 문제이니까 갯수에 대한 정보만 있으면 되겠네! → Dictionary의 value값만을 가져와서 list로 저장해..

풀이 일자: 22.08.17 난이도: [Easy] 문제 내용 여러 단어가 담겨있는 words 배열의 각각의 단어의 Unique한 조합이 몇 개인지 구하는 문제였다. "gin" -> "--...-." "zen" -> "--...-." → 이런식으로 다른 문자더라도 같은 모스부호 조합이 나올 수 있다. 문제 해결 흐름 1. 우선 각 alphabet마다의 모스부호의 규칙이 따로 없기 때문에 해당 정보를 미리 저장해두어야겠다. → 배열 형식으로 저장한다. 2. Unique한 조합을 찾기 때문에 미리 이전에 나왔던 모스부호 조합에 대한 정보를 저장해두어야겠다. → 만약 나오지 않았다면 갯수를 +1하면서 해당 정보를 저장한다. 3. 앞서 배열정보로 저장해둔 각 문자별 모스부호의 접근 방식은 어떻게 하면 좋을까? →..

풀이 일자: 22.08.16 난이도: [Easy] 문제 내용 주어진 문자열 s안에서 1번만 나온 문자의 가장 첫번째 index를 반환하는 문제 문제 해결 흐름 1. 1번만 나오는 문자를 체크하기 위해서는 문자의 개수를 세야겠다. → 중복은 하나로 처리해야하고 탐색도 해야하기 때문에 Dictionary(Hash)를 사용하면 좋겠다. 2. 가장 첫번째 index를 반환하려면 순서에 대한 정보를 가지고 있어야겠다. → 새로운 문자가 들어올때마다 append로 넣고 동일한 문자가 들어오면 remove로 없앨 수 있도록 list를 사용하자. 3. 첫번째 index를 찾자 → str.find()를 이용하여 찾고 만약에 candidate가 비었다면 다 중복이 있다는 이야기임으로 -1을 리턴하자. class Solut..