Medium174 [Leetcode] 1663. Smallest String With A Given Numeric Value 문제 : https://leetcode.com/problems/smallest-string-with-a-given-numeric-value/ 먼저 n 개의 a로 문자열을 만든 다음 가장 뒤에서부터 남은 k 만큼 문자열의 뒤에서부터 더한다. 예를 들어, n=3, k=27인 경우, "aaa"를 만든다. 남은 k는 24이다. 이를 뒤에서부터 더해나가면 "aay"가 된다. n=5, k=73인 경우, "aaaaa", k = 68으로 초기값을 세팅한다. 가장 뒤에 있는 문자에 25를 더해 "aaaaz", k=43. "aaazz", k=18 "aaszz", k=0. 시간복잡도는 O(N) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1.. 2022. 3. 22. [Leetcode] 763. Partition Labels 문제 : https://leetcode.com/problems/partition-labels/ 배열(arr)을 하나 만들어서 문자열 S에서 알파벳이 나오는 시작인덱스와 끝인덱스를 저장한다. S문자열을 탐색하면서 배열을 다 채운뒤 오름차순 정렬한다. 정렬한 배열을 앞에서부터 탐색하면서 나눌수 있는 부분문자열의 마지막 인덱스(last)를 구한다. 1. 만약 현재 탐색중인 알파벳의 시작인덱스가 last보다 작다면 이 알파벳도 부분문자열에 속해야 한다. 알파벳의 종료 인덱스가 last보다 크다면 갱신한다. ex) aabbab -> last는 b 인덱스로 갱신 2. 만약 현재 탐색중인 알파벳의 시작인덱스가 last보다 크다면 이 알파벳은 별도의 부분문자열로 나뉠 수 있다. 이때까지 구한 부분문자열의 길이를 정답에.. 2022. 3. 21. [Leetcode] 316. Remove Duplicate Letters 문제 : https://leetcode.com/problems/remove-duplicate-letters/ 문자열 s가 주어지면 모든 문자가 한 번만 나타나도록 중복되는 문자를 제거하라. 가능한 결과 문자열들 중 사전순으로 가장 작은 문자열을 구하라. 사전순으로 가장 작은 문자열을 구해야 하므로 앞에 있을수록 작은 문자열이 앞에 가야한다. 즉, 현재 만든 문자열에서 탐색 중인 문자를 추가하고자 할 때 정답 문자열에 있는 문자보다 탐색 중인 문자가 작다면 정답에 추가해주어야 한다. 이를 판단하기 위해 스택을 추가한다. 문자열 s를 앞에서부터 탐색하면서 스택에 정답 문자열을 만들 수 있는 문자들을 넣는다. 사전순으로 앞에 있는 문자열을 만들기 위해서는 앞으로 추가될 문자가 현재 정답문자열에 있는 문자보다 .. 2022. 3. 18. [LeetCode] 856. Score of Parentheses 문제 : https://leetcode.com/problems/score-of-parentheses/ 문자열 S를 앞에서부터 탐색한다. 스택을 사용하는데 여기에는 닫는 괄호가 나와서 유효한 값이 생기면 계산된 양수가 아직 닫는 괄호랑 짝지어지지 않은 여는 괄호는 0을 저장한다. 탐색 중 여는 괄호가 나오면 스택에 0을 push 한다. 닫는 괄호가 나오면 스택에 있는 수를 탐색하여 해당 닫는 괄호와 짝이 되는 여는 괄호 사이에 있는 괄호들의 두 번째 조건 AB = A + B 를 계산한다. ex) (()()) -> 진한 괄호들의 연산 1 + 1 계산 짝이 되는 여는 괄호는 스택에 존재하는 0 중 가장 위에 있는 값이다. 따라서 스택의 top이 0이 나오기 전까지 pop 되어 나오는 숫자들을 모두 더한다. 모.. 2022. 3. 17. [Leetcode] 36. Valid Sudoku 문제 : https://leetcode.com/problems/valid-sudoku/ 9 x 9 스도쿠 보드가 유효한지 확인해라. 채워진 셀만으로 다음 규칙을 만족하는지 검증해야 한다. 각 행, 열은 반복 없이 숫자 1~9를 포함해야 한다. 그리드의 3x3 하위 사각형 블럭은 반복 없이 숫자 1~9를 포함해야 한다. 숫자를 포함하는지 비트 연산으로 확인한다. 변수의 이름을 visits으로 하고 초기값은 0이며 i 숫자를 포함한다면 visits or (1 2022. 3. 9. [Leetcode] 740. Delete and Earn 문제 : https://leetcode.com/problems/delete-and-earn/ DP로 풀었다. nums 배열의 최대 요소값을 구하고 이를 maxNum이라 하자. maxNum 크기만큼의 1차원 배열 cnts를 만들고 cnts[i] = nums 요소들중 i의 개수 를 nums 배열을 탐색하며 저장한다. maxNum 크기만큼의 1차원 배열 dp를 만들고 이는 아래의 점화식을 가진다. dp[i] = 0 ~ i 요소들에서 포인트를 얻을 때 얻을 수 있는 최대 포인트 = max(dp[i-1], dp[i-2] + (cnts[i] * i)) i-1 번째 포인트를 얻은경우 i번째 포인트는 지워지므로 얻을 수 없지만 i-2 번째 포인트를 얻은 경우 i번째 포인트도 얻을 수 있기 때문에 위와 같은 점화식이 된.. 2022. 3. 5. 이전 1 2 3 4 5 6 7 8 ··· 29 다음
