본문 바로가기

알고리즘 문제408

[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][929] Unique Email Addresses 문제 : https://leetcode.com/problems/unique-email-addresses/ set을 이용한다.이메일을 앞에서 부터 탐색하면서 '@'가 나오기 전까지 문자는 저장하고 '.'은 무시하면서 이메일을 저장한다. 저장하면서 '+'가 나오면 이후부터 '@'가 나오기 전까지는 무시한다.@이후부터 나오는 도메인은 그대로 저장한다.ex) m.y+name@email.com -> my@email.com 모든 emails 배열을 탐색해서 set을 채웠을 때, set에 있는 이메일 개수가 정답이 된다.시간복잡도는 emails 배열의 크기가 N, emails[i]의 크기가 M이라 했을 때, O(N*M*logN). 소스코드 : https://gist.github.com/fpdjsns/3e2400e0e.. 2018. 10. 28.
[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.
[Leetcode][917] Reverse Only Letters 문제 : https://leetcode.com/problems/reverse-only-letters/ 문자열 S를 앞에서부터 탐색하면서 문자라면 스택에 넣고 문자가 아니라면 큐에 넣는다.모두 탐색했다면 다시 한 번 문자열 S를 탐색하면서 정답 문자열을 만든다.2번째 탐색때 문자라면 스택의 top에서 문자를 꺼내 정답 문자열 뒤에 붙인다. 문자가 아니라면 큐의 front에서 기호를 꺼내 정답 문자열 뒤에 붙인다. 시간복잡도는 O(|S|). 소스코드 : https://gist.github.com/fpdjsns/2c4c2a29c1ff9037b27b81b4033f8daf 2018. 10. 25.

티스토리툴바