Medium174 [leetcode][525] Contiguous Array 문제 : https://leetcode.com/problems/contiguous-array/ 이진수 배열이 주어질 때, 0과 1의 개수가 같은 subarray의 최대 길이를 구하라. 부분합을 키로 하고 해당 부분합이 처음으로 나타난 위치(1이 시작점)를 value로 하는 map을 만든다. 0이 나오는 경우 합에 -1을 해주고 1이 나오는 경우 +1을 한다. 현재 탐색하고 있는 인덱스를 i라 하고 만약 이때까지 나온 부분합들 중 현재까지의 부분합(0~i)을 키로 하는 value가 있다면 i - value가 정답이 될 수 있는 경우이다. 예를 들어, 0011 이 있다면 subSum은 0 -1 -2 -1 0 이 된다. 가장 처음에 있는 0(시작)도 반드시 필요. 이 경우 정답이 될 수 있는 경우는 빨간색과,.. 2020. 4. 13. [leetcode][207] Course Schedule 문제 : https://leetcode.com/problems/course-schedule/ numCourses 개의 코스가 있다. 이 코스들은 선행되는 코스들이 있을 수 있다. 선행되는 코스들을 모두 수강한 경우, 해당 코스를 수강할 수 있다. 코스들의 개수(numCourses), 선행 코스들에 대한 정보(prerequisites)가 주어질 때, 모든 코스들을 수강할 수 있는지 구해라. 위상정렬(topological sort) 관련 문제다. 1. 코스를 선수 과목으로 보는 코스들의 번호를 저장하는 2차원 배열. 2. 코스를 수강하기 위해 선행되어야 하는 코스의 수를 저장하는 1차원 배열. 3. 남은 선수 코스의 개수가 0이여서 수강할 수 있는 코스를 저장하는 큐. 총 3개의 자료구조를 사용했다. 먼저 .. 2020. 4. 3. [leetcode][200] Number of Islands 문제 : https://leetcode.com/problems/number-of-islands/ 2차원 배열 grid가 있다. grid는 1(육지)이나 0(물)로 이루어져있다. 연결되어 있는 1들의 테두리가 모두 0들로 둘러쌓여 있다면 이를 하나의 육지로 본다. grid의 테두리도 0으로 감싸여있다고 한다. grid에 있는 육지의 수를 구해라. DFS, BFS 연습하기 좋은 문제다. 기본적인 구현으로도 풀 수 있다. grid를 전부 탐색하면서 육지를 발견하면 해당 위치를 기준으로 dfs나 bfs를 돌린다. 이 때, 육지를 발견했으므로 정답에 1을 더해준다. 돌리면서 4방면(상하좌우)의 grid 요소들을 탐색하며 이가 육지(1)인 경우 물이나 육지 이외의 사인으로 바꾸어 탐색한 위치라고 표시한다. (연결된.. 2020. 3. 30. [leetcode][152] Maximum Product Subarray 문제 : https://leetcode.com/problems/maximum-product-subarray/ 정수형 배열 nums가 주어질때, subarray의 원소들의 곱 중 최대를 구해라. 곱한다고 했을 때, 최대값이 될 가능성이 있는 경우는 현재 탐색중인 원소가 양수인 경우 가장 큰 양수를 곱하는 경우이고. 탐색중인 원소가 음수인 경우 가장 작은 음수를 곱하는 경우이다. 즉, 배열을 탐색해나가면서 원소의 곱이 가장 큰 경우와 가장 작은 경우를 변수에 저장해둔다. // let, now = 탐색중인 원소 값 // let, maxProducts = 연속되는 원소들의 곱들 중 최대 // let, minProducts = 연속되는 원소들의 곱들 중 최소 maxProducts = max(now, maxProd.. 2020. 3. 24. [leetcode][139] Word Break 문제 : https://leetcode.com/problems/word-break/ 문자열 s, 단어 리스트가 주어질 때 단어 리스트들로 문자열 s를 만들 수 있는지 구하는 문제. 단어는 사용하지 않아도 되고 여러번 사용해도 된다. DP로 해결했다. dp[i] = s[i..]를 단어 리스트로 만들 수 있는지 여부(true, false) 저장. index를 기준으로 s[index]와 문자[0]가 같다면 s[index~] prefix가 문자와 같은지 비교하고 같다면 index+문자길이를 index로 다시 탐색한다. 만약 탐색중 dp[index]가 이미 있다면 이를 반환한다. (이미 s[index..]를 탐색했다는 것을 의미) 시간복잡도는 O(|s| x |wordDict|). 문자가 같은지 비교해야 되기 때문.. 2020. 3. 18. [leetcode][567] Permutation in String 문제: https://leetcode.com/problems/permutation-in-string/ 문자열 s1, s2가 주어졌을 때, s2 서브 문자열에서 s1 문자열 문자들이 전부 존재하는지 구하는 문제. 예를 들어, s1="ab", s2="eidbaooo" 라면 true. s1="ab", s2="eidboaoo" 라면 false. 투포인터로 풀었다. 문자열 s1을 전부 탐색하면서 문자개수를 저장한다. (let, arr) s2 서브 문자열 범위의 시작 위치와 종료 위치를 변수 s, e에 저장한다. s2 문자열을 탐색하면서 탐색 중인 문자 위치를 e라 하자. (let, nowChar = s2[e]) 만약 arr[nowChar] 이 0 보다 크다면 arr[nowChar]를 1 감소시키고 다음 문자를 탐.. 2020. 3. 10. 이전 1 ··· 17 18 19 20 21 22 23 ··· 29 다음