알고리즘 문제/Leetcode283 [leetcode][994] Rotting Oranges 문제 : https://leetcode.com/problems/rotting-oranges/ BFS로 풀었다.백준의 토마토와 비슷한 문제. 큐에 x, y, minutes를 저장한다.배열을 한 번씩 탐색하면서 썩은 오렌지인 경우 큐에 (x, y ,0)을 저장한다.그리고 오렌지(fresh + rotten)의 개수를 저장한다. 배열 탐색이 끝나면 큐가 빌때까지 오렌지 썩음을 전염시킨다.큐에서 요소를 빼낼 때 rotten 오렌지의 개수를 구한다.큐의 앞의 요소부터 탐색하면서 상하좌우 배열을 탐색한다. 만약 탐색한 grid 값이 fresh한 오렌지라면 큐에 넣는다. 이 때 minutes는 +1 해준다.큐에서 마지막으로 꺼낸 요소의 minutes가 정답이 된다.만약 총 오렌지 개수와 rotten 오렌지 개수가 같지.. 2019. 2. 17. [leetcode][993] Cousins in Binary Tree 문제 : https://leetcode.com/problems/cousins-in-binary-tree/ 루트 노드부터 자식 노드로 탐색하면서 val가 x, y일 때의 깊이, 부모노드를 저장한다.깊이, 부모노드를 저장해야 하므로 파라미터로 넘겨줘야 한다.모든 탐색이 끝나고 부모노드가 다르고 깊이가 같은 경우 true, 아니면 false를 반환한다.시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/84b7c2386c834050750401c85011599d 2019. 2. 17. [leetcode][984] String Without AAA or BBB 문제 : https://leetcode.com/problems/string-without-aaa-or-bbb/ A, B 중 최대 최소 횟수를 구한다.A가 B보다 크다면 aabaabaa ... 이런 식으로 남은 A, B의 개수가 같아질 때까지 aab 패턴을 반복한다. B가 A보다 크다면 baa 패턴 반복A와 B의 개수가 같아졌다면 이후로는 abab 패턴을 반복한다.시간복잡도는 O(A + B) 소스코드 : https://gist.github.com/fpdjsns/4508c71f410f330c4d46a8b4319a3f03 2019. 2. 14. [leetcode][992] Subarrays with K Different Integers 문제 : https://leetcode.com/problems/subarrays-with-k-different-integers/ 투포인터로 풀었다.A = 2212211이고 K가 2일 때를 예로 들어보자.인덱스 r이 1일 때,인덱스 l은 K가 2일때를 만족하는 인덱스 0부터 시작한다.이 때, 인덱스 r을 포함시키는 정답이 될 수 있는 경우의 수를 구한다.인덱스 0부터 A[i]의 개수가 1개일 때까지 l을 증가시킨다.정답이 될 수 있는 경우는 이 때 인덱스 l의 증가량 +1이 된다. 정답이 될 수 있으려면 최소한 1개의 범위 내에 각 숫자를 최소한 한 개는 가지고 있어야 한다.즉, 인덱스 r을 포함한 정답가능한 최소 문자열은 위 그림과 같이 "2 1" 이다.여기에서 K가 2일 때를 만족하는 범위의 인덱스들을.. 2019. 2. 14. [leetcode][989] Add to Array-Form of Integer 문제 : https://leetcode.com/problems/add-to-array-form-of-integer/ A배열의 뒤, K 정수의 일의자리부터 서로 더해간다. 가산기 처럼 더한 값의 10으로 나눴을 때 남은 수는 정답의 1의자리가 되고 몫은 다음 가산의 carry로써 더해진다.리턴값은 배열인데 정확한 자리수를 아직 알 수 없으므로 더한 결과를 앞에서부터 차례대로 추가했다.배열 A를 돌면서 값을 더해서 정답 배열을 구한 뒤 남은 K와 carry의 합이 0보다 크다면 일의자리부터 정답 배열의 뒤에 차례대로 더해준다.그러면 정답 배열의 역순을 구할 수 있다. (일의 자리를 앞에서 부터 채웠으므로)역순을 구했으므로 정답배열을 역순한 결과를 반환한다. 소스코드 : https://gist.github.c.. 2019. 2. 13. [leetcode][991] Broken Calculator 문제 : https://leetcode.com/problems/broken-calculator/ X를 Y로 만드는 횟수가 아닌 반대로 Y를 X로 만드는 횟수를 구했다.반대로 구했기 때문에 연산도 반대가 된다. (/2, +1) 만약 X가 Y보다 크다면 나누기 2를 하면 안된다. 따라서 +1 연산만하게 되고 +1 연산 횟수는 X - Y가 된다.X가 Y보다 작고 Y가 2의 배수라면 /2 연산을 한다.X가 Y보다 작고 Y가 2의 배수가 아니라면 +1 연산을 한다. 소스코드 : https://gist.github.com/fpdjsns/c4b613504108f095f368c875dbadeda7 2019. 2. 13. 이전 1 ··· 39 40 41 42 43 44 45 ··· 48 다음
