Min IT's Devlog

풀이 일자: 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.03 난이도: [Medium] 분류: [Array, Two Pointers, Greedy, Sorting] 문제 내용 사람들의 무게가 담긴 people이라는 배열이 주어졌을 때 최대중량이 limit인 배를 이용해 최대 2명의 사람들을 운반하고자 한다면 최소 몇 개의 배가 필요한지에 대한 문제였다. 문제 해결 흐름 1. 제일 먼저 떠올릴 수 있는 건 Greedy가 제일 먼저 떠오르겠다. → 최소한으로 옮겨야 하므로 Greedy하게 무게가 제일 많이 나가는 애랑 적게 나가는 애랑 같이 운반할 수 있다면 최소가 되겠네 2. 무게의 순서가 중요하니까 people에 대한 sort는 필수적이다. → sort를 해서 시작점과 끝점에 포인터를 두고 가장 무게가 큰 것부터 시작해서 되도록 맨 앞에..