Medium174 [Leetcode] 1375. Bulb Switcher III 문제 : https://leetcode.com/problems/bulb-switcher-iii/ 1 ~ n 까지 번호가 매겨진 n개의 전구가 왼쪽에서 오른쪽으로 나열된 방이 있고, 전구번호를 가진 light 배열이 있다. 모든 전구들은 전구가 꺼져있다. k(0 ~ n-1) 번째에 light[k] 전구를 켠다. 만일 전구가 켜져 있고 해당 전구의 좌측에 있는 모든 전구들 또한 켜져 있다면 전구의 색들이 파란색으로 바뀐다. 켜진 전구들이 모두 파란색이 되는 순간의 횟수를 구해라. k번째에 켜진 모든 전구들이 파란색으로 변경되는 순간은 1 ~ k+1 번째의 전구가 모두 켜져있는 경우밖에 없다. 한 번엔 하나의 전구만 켜지고 전구의 번호는 겹치지 않으므로 이때동안 켜졌던 전구번호중 가장 큰 값이 k+1인 경우가.. 2021. 11. 24. [Leetcode] 289. Game of Life 문제 : https://leetcode.com/problems/game-of-life/ m x n 2차원 배열이 있다. 배열은 1(live) 혹은 0(dead) 로 채워져 있다. 배열의 다음 상태는 각 셀의 8개의 이웃(수직, 수평, 대각선) 의 생사와 관련이 있다. 살아있는 상태의 셀의 살아있는 이웃 수가 2, 3개라면 다음에도 살아있을 수 있다. 하지만 이웃수가 너무적거나(0, 1) 너무 많으면(3초과) 인구과다로 죽게된다. 죽은 상태의 셀의 살아있는 이웃 수가 3개라면 번식한것처럼 되살아난다. 초기 생사 정보를 담은 배열이 입력으로 주어질 때 다음 상태를 반환하라. m x n 배열을 하나 만들어서 모든 셀을 탐색하며 각 셀의 살아있는 이웃들의 수를 저장한다. 다시한번 입력 배열을 탐색하며 만일 살아.. 2021. 11. 23. [Leetcode] 106. Construct Binary Tree from Inorder and Postorder Traversal 문제 : https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 이진 트리의 중위 순회, 후위 순회 결과 배열들이 주어졌을 때 이진 트리를 구하라. 루트노드는 후위순회의 가장 뒤에 있는 노드이다. 후위순회 배열에서 루트 노드를 구한 뒤 중위 순회에서 루트노드의 왼쪽에 있는 값들이 왼쪽 자식 노드들, 오른쪽에 있는 값들이 오른쪽 자식 노드들이 된다. 중위 순회, 후위 순회 배열들의 범위를 위와 같은 방법으로 줄여나가며 재귀함수로 서브트리들의 루트노드, 왼쪽 오른쪽 자식 노드들을 구하며 트리를 만들어나간다. 시간복잡도는 O(N) 소스코드 : https://github.com/fpdjsns/Algorith.. 2021. 11. 21. [Leetcode] 240. Search a 2D Matrix II 문제 : https://leetcode.com/problems/search-a-2d-matrix-ii/ m x n 정수형 배열에서 target 이 존재하는지 유무를 반환하라. 배열은 각 행, 열에서 오름차순 정렬되어 있다. 가장 쉽게 생각할 수 있는건 각 행, 혹은 열마다 차례대로 이분탐색을 돌려서 target 값이 있는지 확인한다. 시간복잡도는 O(N logM) or O(M logN). 각 행, 열에서 오름차순 정렬되어 있다는 특징을 독립적으로 보지 않고 탐색조건에 같이 사용할 수 있을지 생각해보았다. 예제 1번의 배열모습이다. x = 1, y = 1 일 때, matrix[x][y]는 5이다. 이때 matrix[x~][y~] 배열을 한 번 보자. 각 행, 열들은 오름차순 정렬되어있으므로 항상 최상단좌측.. 2021. 11. 20. [Leetcode] 80. Remove Duplicates from Sorted Array II 문제 : https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/ 앞에서부터 탐색하면서 연속으로 등장하는 정수의 수를 저장한다. 만일 이전과 같은 정수인데 3개 이상 등장하는 수라면 해당 요소를 삭제한다. 리턴값은 삭제하고 난 뒤의 nums 배열의 사이즈를 반환한다. 시간복잡도는 O(N). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/80.%20Remove%20Duplicates%20from%20Sorted%20Array%20II.cpp 2021. 11. 15. [Leetcode] 34. Find First and Last Position of Element in Sorted Array 문제 : https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/ 내림차순 정렬된 정수 배열과 target 값이 주어지면 배열에서 target 값의 시작 위치와 끝 위치를 찾아라. 만일 target을 찾을 수 없다면 [-1, -1]을 반환해라. O(log N) 복잡성을 가지는 알고리즘을 작성해라. logN 복잡성이라는거 보니 이분탐색으로 해야겠다. 이분탐색을 진행하면서 target 값을 찾는 경우 정답배열의 최소값, 최대값을 갱신한다. 그리고 시작 위치와 끝 위치를 찾아야 하므로 여기서 끝내지 않고 (left, m-1), (m+1, right) 로 이분탐색 2개를 다시 실행시킨다. (m = (left + r.. 2021. 11. 14. 이전 1 ··· 6 7 8 9 10 11 12 ··· 29 다음
