leetcode5 [Leetcode] 838. Push Dominoes 문제 : https://leetcode.com/problems/push-dominoes/description/ 배열을 하나 만들어서 문자열 길이만큼 0을 채운다. 이 배열에 L이라면 음수를, R이라면 양수를 채울 것이다. '.' 인 경우는 0. 'L', 'R'을 만나서 배열을 갱신할 때 시작점과 얼마나(인덱스) 떨어져 있는지 저장한다. 문자가 'L'이라면 왼쪽으로 가면서 -1, -2, -3 … 이런식으로 다음 문자를 만날 때까지 채워준다. 'R'이라면 오른쪽으로 가면서 1, 2, 3 … 을 다음 문자를 만날 때까지 채워준다. 문자가 있는 부분은 양수나 음수로 적절히 채운다. 나는 L은 '-1', R은 '1'을 채워줬다. 주의할 점이 2가지 있다. 1. "R . . . L" 이 경우 정답은 "R R . L.. 2022. 9. 28. [Leetcode] Weekly Contest 312 contest : https://leetcode.com/contest/weekly-contest-312/ 1. Sort the People (Easy, 3) 문제 : https://leetcode.com/contest/weekly-contest-312/problems/sort-the-people/ heights 배열로 {heights[index], index}를 요소를 가지는 배열을 만든 뒤 높이내림차순 정렬. 정렬된 배열을 앞에서부터 탐색하면서 names[index]를 정답에 차례대로 세팅 시간복잡도는 O(NlogN) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/2418.%20Sort%20the%20People.cpp 2... 2022. 9. 25. [Leetcode][17] Letter Combinations of a Phone Number 문제 : leetcode.com/problems/letter-combinations-of-a-phone-number/ 전화 버튼과 동일한 숫자와 문자의 매핑이 있다. 2~9까지의 숫자로 이루어진 문자열이 주어지면 가능한 모든 문자 조합을 반환해라. 하나의 숫자에 복수개의 문자가 매핑되므로 dict[숫자] = 문자의 배열 을 먼저 구해준다. 가능한 문자 조합들은 백트래킹을 이용하여 구한다. 예시로 주어진 23이면 1. 빈 문자열부터 시작해서 2에 해당하는 문자들 중 하나를 넣고("a") 다음 숫자를 판단한다. 2. "a" 이후 3에 해당하는 문자들 중 하나를 세팅한다. "ad". 모든 digits들의 숫자를 판단했으므로 "ad"를 정답에 추가한다. 3. 가장 마지막 문자를 제거한 후('d'가 제거되어 "a.. 2021. 4. 10. [leetcode][1008] Construct Binary Search Tree from Preorder Traversal 문제 : https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/ 문제에서는 inorder 순서로 숫자 배열을 입력으로 준다고는 하지만 생각해보면 이진 탐색트리(BST)를 만드는 것과 같다.항상 루트부터 탐색하면서 NULL이 나올 때까지 현재 탐색중인 노드보다 작으면 왼쪽 자식, 크면 오른쪽 자식 노드로 탐색해간다.NULL이면 그 자리에 값을 val로 노드를 만들어 넣으면 된다.이렇게 하면 O(NlogN) 정도 나온다. (코드는 이 방식으로 짰다.)사실 입력 값을 다 알고 있으면 굳이 항상 루트 노드부터 탐색하면서 트리를 만들 필요는 없다.예를 들어 [8,5,1,7,10,12]가 입력값이라고 하자.inorder이.. 2019. 3. 13. [leetcode][1004] Max Consecutive Ones III 문제 : https://leetcode.com/problems/max-consecutive-ones-iii/ 투 포인터로 풀었다.큐를 하나 만들어서 0인 경우 0일 때의 인덱스를 큐에 저장한다.그리고 start, end 인덱스 2개를 저장한다. A 배열을 앞에서 탐색하면서 탐색 중인 인덱스가 end인덱스가 되는 정답이 될 수 있는 가능한 start 인덱스를 갱신해나간다.start인덱스는 0부터 시작되며 갱신되는 경우는 [start, end] 범위에 0의 개수(0 인덱스를 저장하는 큐의 size)가 K개를 초과하는 경우이다.start는 큐의 가장 앞에 있는 0의 인덱스 + 1이 된다.A 배열을 모두 탐색하면서 가능한 [start, end] 범위를 구하고 해당 범위의 길이 중 최대 값이 정답이 된다.시간복잡.. 2019. 3. 4. 이전 1 다음
