Medium174 [leetcode][945] Minimum Increment to Make Array Unique 문제 : https://leetcode.com/problems/minimum-increment-to-make-array-unique/ A 배열을 오름차순 정렬한다.그리고 unique한 값을 저장하는 변수를 하나 만든다.unique한 값의 초기값은 A배열에서 가장 작은 값과 같고A배열을 탐색해갈수록 1씩 커진다.A배열을 앞에서부터 탐색할 때,unique 값이 A[i]값보다 같거나 작다면 unique 값은 A[i]로 갱신시켜준다. (오름차순 정렬을 했고 조건이 1을 더하는 것이므로 1을 더해서 이후에 유니크한 값을 만드려면 현재 탐색 중인 값보다는 반드시 커야한다.)unique 값이 A[i] 값보다 크다면 A[i]는 unique값이 되기위해 값을 더해야 한다. 이 값이 정답에 더해진다. (ex. unique.. 2018. 11. 27. [leetcode][946] Validate Stack Sequences 문제 : https://leetcode.com/problems/validate-stack-sequences/ poped배열을 앞에서부터 탐색하면서 가능한 순서인지 체크한다. pushed : 1 2 3 4 5 poped : 4 2 5 3 1 를 예로 들어보자. pop할 값 stack에 들어간 값 아직 stack에 들어가지 않은 값 1 2 3 4 5 4 1 2 3 5 5 1 2 3 3 1 2 2 1 1 위 테이블을 보면 pop해야 할 값이 아직 stack에 들어가지 않았다면 pop할 값이 나올 때까지 stack에 값을 넣는다. pop해야 할 값이 이미 stack에 있다고 한다면 stack의 top에 해당하는 값이 해당 값이어야 한다.문제에서 조건을 보면 poped배열 크기와 pushed 배열크기는 같고 모든.. 2018. 11. 25. [leetcode][938] Range Sum of BST 문제 : https://leetcode.com/problems/range-sum-of-bst/ BST는 왼쪽 자식 서브트리는 현재 노드보다 값이 작고, 오른쪽 자식 서브트리는 현재 노드보다 값이 크다.따라서 현재 노드의 val가 L보다 크다면 왼쪽 서브트리에도 정답이 될 수 있는 노드가 있을 수도 있다. -> 왼쪽 서브트리 탐색.현재 노드의 val가 R보다 작다면 오른쪽 서브트리에도 정답이 될 수 있는 노드가 있을 수 있다. -> 오른쪽 서브트리 탐색.루트 노드부터 위 조건에 맞는 서브트리를 탐색해 가면서 정답이 될 수 있는 수를 더해간다. 시간복잡도는 O(노드개수). 소스코드 : https://gist.github.com/fpdjsns/8818a1684ee7bb59abfb404ff6dd792e 2018. 11. 12. [leetcode][129] Sum Root to Leaf Numbers 문제 : https://leetcode.com/problems/sum-root-to-leaf-numbers/ DFS로 풀었다.재귀함수를 만들어서(스택 사용 반복문으로 풀어도 됨) 자식노드로 가면서 합계를 더해나간다.만약 현재 노드가 리프노드(=왼쪽, 오른쪽 자식이 모두 없는경우)라면 이때까지의 합을 정답에 더한다.자식노드로 내려갈때는 현재까지의 합에서 *10을 해준다. 소스코드 : https://gist.github.com/fpdjsns/594442e85df0096e7b2f86f5fb120c15 2018. 11. 10. [Leetcode][934] Shortest Bridge 문제 : https://leetcode.com/problems/shortest-bridge/ BFS로 풀었다.먼저 배열을 탐색하면서 1 위치를 찾는다.찾은 위치를 시작점으로 BFS를 돌리면서 연결된 1을 2로 모두 바꾼다.바꾼 배열에서 아까의 시작점을 또 다시 시작점으로 하여서 BFS를 한 번 더 돌린다.이번에는 0을 1로 바꾼 횟수도 저장해야 한다. 따라서 이때의 너비우선탐색은 0 -> 1로 바꾼 횟수가 가장 작은것부터 먼저 탐색한다.다음 탐색 위치가 0이라면 탐색횟수+1을 한다.2라면 같은 땅이므로 탐색횟수는 이전과 같다.1이라면 현재까지 탐색한 횟수가 정답이 된다. 시간복잡도는 정확하게는 잘 몰겄지만 BFS를 2번 돌리니까 대략적으로 배열크기와 같다고 보면 될 듯하다. 소스코드 : https://g.. 2018. 11. 10. [leetcode][918] Maximum Sum Circular Subarray 문제 : https://leetcode.com/problems/maximum-sum-circular-subarray/ 최대 부분 문자열과 최소 부분 문자열을 구한다.최대 부분 문자열의 합과 배열의 모든 총합 - 최소 부분 문자열 중에 큰 값이 정답이 된다.모든 수가 음수인 경우는 음수 중에 가장 큰 값이 정답이 된다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/fa784f6bf9e9296b8670fc07759ff466 2018. 11. 5. 이전 1 ··· 25 26 27 28 29 다음