ProblemSolutionrecursive, backtracking3개 문자중에서 n개 만큼 뽑는 순열문제.단, str[i] != str[i+1] 이어야한다.  Codeclass Solution: def getHappyString(self, n: int, k: int) -> str: chars = ['a', 'b', 'c'] li = [] def happy(cur): # 문자열 길이가 n이면 종료 if len(cur) == n: li.append(cur) return for char in chars: ..

Problem Solutionstackbrute forceI 가 나오면 숫자 증가,D 가 나오면 숫자가 감소하도록하여 가장 작은 수를 반환하는 문제.지난번 비슷한 문제에서 dfs 를 사용했어서 비슷하게 풀면되는 줄 알고 삽질함 사전적으로 가장 작은 숫자를 반환해야하므로 가장 작은 수인 1부터 숫자 추가.마지막 인덱스이거나 patter[i] == I 이면 stack 모두 비울때까지 res 배열에 넣는다. stack 이라서 FIFO 구조로 먼저 넣은 숫자 먼저 res에 저장된다. 마지막에 res 배열에 있는 숫자들 join 해주면됨! pattern의 길이가 8까지라서 hint에도 bruteforce로 다해보라고 권했음.  Codeclass Solution: def smallestNumber(self, ..

ProblemSolutionbacktrackingheuristic (bruteforce)처음에 한번에 이해하는게 어려웠던 문제.조건은 아래와 같다.1 ~ n 까지의 수 중에서 1) 1 은 한번만 나옴2) 2~n 사이의 수는 2번 나옴3) 사전순으로 정렬했을 때 a[i] == a[j] 에 대해서 |j-i| = n 이어야한다. 예를들어     arr = [3, 1, 2, 3, 2] 에서 3은 2번 등장하고 두 거리는 3 이다. (arr[0] = 3, arr[3] = 3)     2는 2번 등장하고 두 거리는 2이다. (arr[2] = 2, arr[4] = 2)4) 사전순으로 정렬했을 때 가장 큰 배열 return이때 처음에 숫자를 넣을 때 n (가장 큰 수) 부터 배열에 넣는게 유리하다.  Codeclass..

Problem Solutionrecursive주어진 n 에 대해서 1 힌트를 보니 재귀로 해당 조건을 만족하는지 체크하는 내용이었다. sqared (제곱) 값을 구한 후 string 으로 변환한 뒤,  1 부터 i 까지 재귀함수를 돌며 조건을 만족하는지 체크한다. (check method)step 1) idx = 0 자리수부터 체크하되 idx == len(sqared) 길이가 동일해지면 지금까지의 합계와 target 값이 동일한지 체크 후 반환.step 2) 0 부터 len(sqared) 까지 각 자리수의 인덱스를 돌면서 합계를 구한다. 재귀함수를 통해서 1의 자리부터, 10의 자리부터, 100의 자리부터 계산해가며 target 값이 나올때까지 반복한다. Codeclass Solution: def ..

Problem Solutionlistlist에서 마지막 K개 원소의 총 곱을 구하는 문제.시간복잡도가 O(N)이면 time out이 발생해서 O(1)으로 해결해야되는 문제!prefix 곱을 모두 구한 뒤, prefix[n-1] // prefix[n-k-1] 로 뒤에서 k개 원소의 곱을 구한다.여기서 문제는 분모가 0이되면 안된다.1) 모든 원소를 저장한 arr중 마지막 k개 원소만 담은 arr[-k:]  에 0이 포함되어있는지 체크2) k == len(arr[-k:]) 이면 prefix[-1] 마지막 값 반환3) 분모가 0이면 for문으로 직접 모두 계산 Codeclass ProductOfNumbers: def __init__(self): self.prefix = [] se..

Problem Solutionheapnums에서 k보다 작고 가장 작은 최소값 2개를 구해서 min(x,y) * 2 + max(x,y) 를 nums에 추가한다.이때 최소값 2개는 반드시 필요하다.위 반복 작업을 몇 번하는지 카운트하는 문제.  Codeimport heapqclass Solution: def minOperations(self, nums: List[int], k: int) -> int: answer = 0 heapq.heapify(nums) while(len(nums) > 1 and nums[0]  ComplexityTime Complexityheapq.heapify(nums) -> O(N) num1 = heapq.heappop(nums) # O(l..