본문 바로가기

Medium174

[leetcode][91] Decode Ways 문제 : https://leetcode.com/problems/decode-ways/ DP로 풀었다.알파벳이 될 가능성이 있는 수는 한자리 수(1~9)이거나 두 자리 수(10~26)다.문자열을 앞에서부터 탐색하면서 한자리 수와 현재 탐색중인 문자보다 하나 작은 문자를 합쳐서 두 자리 수를 구해 이들이 알파벳이 될 수 있는지 체크한다. ex) "12" -> 1, 2, 12 체크.탐색 중인 문자열 인덱스를 ind라 하고 ind번째 문자열까지 만들 수 있는 알파벳문자열의 경우의 수를 저장하는 d[ind] 배열을 만든다. 한 자리 수가 숫자가 될 수 있는 경우 ind-1 번째 문자열까지 만들 수 있는 알파벳 배열의 수(d[ind-1])를 d[ind]에 더한다. (d[ind-1]로 만들 수 있는 알파벳 문자열 뒤.. 2018. 11. 2.
[leetcode][423] Reconstruct Original Digits from English 문제 : https://leetcode.com/problems/reconstruct-original-digits-from-english/ Note 2번에 집중해보면 코드를 더 간결하게 짤 수 있다. 2. Input is guaranteed to be valid and can be trasformed to its original digits. That means invalid inputs such as "abc" or "zerone" are not permitted. 모든 문자는 숫자로 변경될 수 있는 문자라는 뜻이다. 즉, 0~9 숫자의 알파벳 중에 자신만 고유하게 가지고 있는 문자가 입력 문자열에 있다면 해당 문자는 반드시 나온다는 뜻이다. 그렇지 않으면 2번 조건에 어긋나기 때문이다.ex) z~~ -.. 2018. 11. 1.
[leetcode][62] Unique Paths 문제 : https://leetcode.com/problems/unique-paths/ 학창시절 때 배웠던 것을 떠올려본다. 3*4 그리드가 있다고 하면 일단 가장 위에 행과 가장 왼쪽 행은 1로 갱신한다. 이 부분들은 갈 수 있는 횟수가 전부 1이다. (오른쪽으로만 가거나 아래로만 가거나) 남은 그리드 부분은 왼쪽+위가 갈 수 있는 경우의 수가 된다. (위에서 내려오거나, 왼쪽에서 오른쪽으로 오거나) 이렇게 왼쪽 위에서부터 오른쪽 아래 방향으로 차례대로 모든 그리드를 채웠을 때 가장 오른쪽 아래에 있는 수(10)가 정답이 된다. 시간복잡도는 O(NM). 소스코드 C++ : https://gist.github.com/fpdjsns/7640cc2431977f51ce86007374ddf8e5 pythone .. 2018. 10. 29.
[leetcode][921] Minimum Add to Make Parentheses Valid 문제 : https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/ 스택을 이용한다.스택에는 열린 괄호가 나올 때 이를 저장한다. 문자열 S를 처음부터 모두 탐색하면서 만약 문자가 열린 괄호라면 스택에 push한다. 문자가 닫힌 괄호이고 스택이 비어있지 않은 경우 스택을 pop해준다.ex) () -> 파란색 여는 괄호가 빨간색 닫는괄호의 짝이 된다. 문자가 닫힌 괄호이고 스택에 아무것도 없는 경우 열린 괄호가 하나 더 필요하다는 의미이므로 정답 + 1을 해준다.ex) ()) -> 짝이 없는 닫힌 괄호문자열 S를 모두 탐색했을 때 스택의 크기(짝이 없는 여는 괄호)를 정답에 더해준다.ex) ())(( 시간복잡도는 O(|S|). 소스코드 : h.. 2018. 10. 28.
[LeetCode][926] Flip String to Monotone Increasing 문제 : https://leetcode.com/problems/flip-string-to-monotone-increasing/description/ 문자열을 앞에서부터 탐색하면서 1과 0의 개수를 센다.00110이 있다면 1로 바꿔야 하는 0은 1보다 뒤에 위치한다. (00110)1은 앞에 나오는것부터 바꿔야 하므로 처음부터 세어준다.지금 세어주는 수가 현재부터 0 혹은 1을 반대 수로 flip 할 때 바꿔야 하는 최소 횟수가 된다. 만약 0을 바꾸는 것 보다 1을 바꾸는게 더 이득이라면 1을 바꾸는횟수로 초기화한다.예를들어, 1010011이 있다면 4번째 인덱스까지 탐색했을 때 0의 개수(3)는 1의 개수(2)보다 크다.따라서 앞에서 나오는 1들을 모두 0으로 바꾸면 된다. -> 0000011반대의 경.. 2018. 10. 27.
[Leetcode][915] Partition Array into Disjoint Intervals 문제 : https://leetcode.com/problems/partition-array-into-disjoint-intervals/ 배열 A를 뒤에서부터 탐색하면서 [탐색중인 인덱스, 끝] 에 포함되는 배열 요소들의 최소값을 저장하는 배열을 만든다.최소값을 저장하는 배열을 만들었다면 이번에는 배열 A를 앞에서부터 탐색하면서 [시작 ~ 탐색중인 인덱스]의 요소들의 최대값을 구한다.탐색중인 인덱스를 ind라 하였을 때 만약 ind까지 구한 최대값이 [ind, 끝] 범위의 최소값보다 작다면 정답이 될 수 있는 경우이다.ex) [5, 0, 3, 8, 6] -> [5, 0] [3, 8, 6] 으로 나뉜다고 보면 ind는 1이 되고 ind까지의 최대값은 5, ind ~ 끝 범위의 최소값은 3이 되므로 정답이 될.. 2018. 10. 26.

티스토리툴바