Apes Together Strong.

Q. inorder 와 postorder 순회 정보가 주어질 때 tree를 구성하라.   Solution.  105번(https://artofcom77.tistory.com/258) 의 응용판 문제.  여기서는 post order 정보를 사용하였으므로, 값을 뒤에서 부터 취하는 것이 중요.  또한 뒤에서 부터 취하므로, tree를 left -> right 가 아닌 그 역순(Right->Left)으로 더해 나가기 시작하는 것에 유의 한다.   코드 더보기  TreeNode BT(Dictionary dictBuffer, int[] postorder, ref int idx, int left, int right){ if(left > right) return null; if(idx=dictBuff..

https://leetcode.com/problems/basic-calculator/description Q. 괄호와 기본 +, - 연산을 지원하는 기본 계산기를 구현하라.    Solution.  단순해 보이지만, 조금 문제에 대해 세부 파악이 필요한 문제다.  괄호로 인한 계산 우선 순위, 부호에 의한 값 반전 등 고려해야 할 것들이 있다.   숫자는 부호를 포함해 한덩어리로 생각하기로 한다.  그러면 괄호로 둘러싸인 숫자의 연속이 된다.   닫는 괄호가 나오면, 열린 괄호를 만날때까지 숫자를 더해 준다.  이때 마이너스 값은 음수로 더해 질 것이다.  다만, 괄호를 만나 마감하기 전, 한번 더 그 앞 기호를 확인해 음수이면 최종값을 stack에 반영하기 전에  다시 음수 전환 해 준다.   위 로직..

https://leetcode.com/problems/insert-interval/description Q. 주어진 구간 정보배열 intervals가 있고, 추가 될 구간 newInterval 이 있다. 이때 newInterval을 추가한 상태로 새로운 구간 정보를 구성하라.  Solution.  그냥 있는 그대로의 상태에서 바로 이런 저런 시도를 하려다 보니, 풀이 시간이 길어졌다.  최대로 복잡한 구간을 최대한 간결한 코드로 풀어내는 것이 코딩문제 풀이의 핵심이다.  이것도 최대한 그렇게 해 본다.   주어진 구간 interval은 이미 정렬된 구간 데이터 이다.  따라서 새 구간 정보를 주어진 데이터에 넣으면 되는데, 이때 아래의 규칙에 따른다.   우선 새 구간 정보와 기존 index 순서대로 구..

https://leetcode.com/problems/candy/description Q. 주어진 정수 배열 ratings는 아이들의 사탕에 대한 평점을 의미한다.  이때, 모든 아이들이 사탕 1개 이상씩 갖게 한다.  다만, 바로 주변 보다 평점이 높은 아이는 해당 낮은 주변 아이보다 더 많이 사탕을 갖게 한다.  최소로 필요한 사탕의 수를 찾아라.  Solution 우선 정확하게 문제 해석을 해 본다.   모든 아이들은 우선 1개 이상의 사탕을 갖는다.  주변보다 평점이 높다면, 주변보다 사탕도 많아야 한다.   예를 들어 평점이 1,3,4,5,2  라면,   1, 2, 3, 4, 1  의 사탕을 주어야 조건을 만족하게 된다.   2, 0, 3, 3, 2 의 평점이 주어진 다면,  2, 1, 2, 2..

https://leetcode.com/problems/insert-delete-getrandom-o1/description Q. insert된 Random한 수를 출력하는 객체를 디자인 하라.  insert, remove, getRandom 모두 O(1)에 작동해야 한다.   Solution.  좋은 문제다.   O(1)에 작동해야 하므로, hash 류를 써야 함에는 틀림없다.  다만, 그렇다면 random 값을 O(1)에 반환하는 것에 문제가 생긴다.   따라서 여분의 버퍼를 별도 관리 하여야 한다.   즉, dictionary를 두고, list를 별도로 둔다.  insert : O(1)에 넣는다.  getRandom : random 함수와 list를 이용해 index 접근하여 값을 O(1)에 얻는다...

https://leetcode.com/problems/find-the-duplicate-number/description  Q. 주어진 정수배열 nums는 1부터 배열의 길이까지의 값을 가진다. 이때 하나의 값이 더 있고, 이 값이 기존 값들 중 하나와 중복일 때, 이 중복 값을 찾아라.   이때, 기존 배열을 수정하지 말고, 추가 메모리도 사용하지 말아라.   Solution.  우선 제한을 생각하지 말아 본다.   2중 루프들 돌며 중복 값을 찾는다. -> O(N x N)으로 TL 오류.  추가 버퍼를 가지고 flag checking 한다. -> In Place memory limitation. 정렬하고 중복찾기 -> 기존 배열 수정 금지 오류.   따라서 다른 접근이 필요하다.   각 배열을 lin..

https://leetcode.com/problems/majority-element/description Q. 주어진 정수 배열 nums에서 빈도수가 배열 길이의 반이상이 되는, 대다수가 되는 정수를 찾아라. O(N)의 TC에 O(1)의 memory space를 사용하라.  Solution.  추가 버퍼를 쓸 수 있다면 간단하다. frequency buffer를 만들고 가장 큰 녀석을 찾는다.   정렬해서 가운데 위치하는 녀석을 반환해도 된다. 반 이상 빈도가 되므로 가능한 것이다. 하지만 TC가 O(NxLogN) 이다.   다른 접근이 필요하다.  boyer-moore voting 알고리즘으로 풀이를 시도 해 본다.   즉, 0을 기준으로 후보를 정한다.  후보와 같으면 1을 더하고 아니면 1을 뺀다...

https://leetcode.com/problems/maximum-subarray/description Q. 주어진 숫자배열의 최대 부분합을 구하라.   Solution.  2 중 loop를 돌면 풀이는 간단해 진다.  하지만, O(N)에 구할 방법을 고민해 보자.   여기서 잘 알려진 알고리즘이 dynamic programming을 활용한, 방법이다.  즉, 이전까지의 부분합의 최대값에 현재위치값을 더한 최대값이 현재의 최대 부분합이 된다는 것이다.   이것을 Kadane's Algorithm이라 하며, 이 알고리즘은 꽤 유명하다.   이것을 토대로 코드를 만들어 본다.  더보기 public int MaxSubArray(int[] nums) { // 주어진 배열에서 최대의 합을 가진 subArr..

https://leetcode.com/problems/first-missing-positive/description  Q. 정렬되지 않은 정수 배열 nums가 주어질 때, 배열안에 없는 가장 작은 양수를 찾아라.  O(N)의 TC에 O(1)의 space를 사용하라.  Solution 추가 메모리를 쓰면 간단하다.  하지만, 여기서는 그렇게 하면 안되므로, 다른 방법을 고려한다.   존재하는 수를 특정 방식으로 걸러내에 존재하지 않는 수를 찾아낸다.  여기서는 음수화를 취한다.   우선 루프를 돌며, 해당 값을 nums 배열과 매칭 시킨다면, 범위 바깥이 될 수를 골라내 범위 안 최소 값으로 초기화 한다. 모든 수가 존재한다면, 범위 밖 수는 없게 된다.   이 값을 index로 변환하고, 이 index위..

https://leetcode.com/problems/next-permutation/description Q. 주어진 정수 배열 nums에서 다음 permutation 값을 찾아라.  Solution 이런 문제를 보면 아직도 정말 배워야 할 것이 넘침을 느낀다.  직관으로 풀기는 힘든 문제.   관련 알고리즘을 찾아본다.   우선 nums[i]  이 피봇 포인트를 기준으로 뒤편의  값 중 피봇 포인트보다 큰 수장 가장 작은 값을 찾는다.  이 값과 피봇 포인트 값을 교체한다.  그리고 피봇 포인트 우측편 값들을 오름차순 정렬한다.  ( Reference : https://yoongrammer.tistory.com/109 )  이것이 원하는 답이 된다.   로직대로 코드를 만들어 본다.  더보기public..