Apes Together Strong.

https://leetcode.com/problems/roman-to-integer/description Q. 주진 로마 문자를 숫자로 변환하라.  Solution이 문제는 1씩 모자라는 숫자들에 대해 특별 처리가 필요하며, 그것을 제외하면 특별한 내용은 없다.  더보기 public int RomanToInt(string s) { Dictionary dictValue = new Dictionary(); dictValue.Add("I", 1); dictValue.Add("V", 5); dictValue.Add("X", 10); dictValue.Add("L", 50); dictValue.Add("C", 100); dictValue.Add("D", 500); dic..

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/remove-duplicates-from-sorted-array-ii/description Q. 정렬된 정수배열 nums에서 해당 숫자를 최대 2번까지 nums에 출력하고 그 길이를 반환하라.  추가 메모리를 사용하지 말아라.  Solution.  기존 로직들과 매우 유사하며, 다만 2회 check 로직을 추가 한다.  public int RemoveDuplicates(int[] nums) { int idx = 1; int cnt = 1; int val = nums[0]; for(int q = 1; q   적절한 결과.

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description Q. 오름차순으로 정렬된 정수 배열 nums가 주어질때, 이 값을 중복을 제거하고 다시 nums에 출력하고 그 길이를 반환하라. 이 후 이 유효한 길이를 반환하라.  이때 추가 메모리를 사용하지 말아라. Solution.  바로 위의 문제와 아주 유사한 문제.   이미 정렬이 되어 있으므로, 중복이 없을 시만, 앞에서부터 overwrite 해 나간다.  public int RemoveDuplicates(int[] nums) { int idx = 1; int val = nums[0]; for(int k = 1; k   적절한 결과.

https://leetcode.com/problems/remove-element/description Q. 정수배열 nums와 val 이 주어질 때, val을 제외한 nums배열을 다시 nums배열에 출력하고 그 길이를 반환하라.  이때 추가 메모리를 사용하지 말아라.  Solution.  어디서 본 0 뒤로 밀기와 비슷한 문제.   그냥 대상이 아닌 값들을 제외한 값들을 당긴다.  public int RemoveElement(int[] nums, int val) { int idx = 0; for(int q = 0; q   빠른 코드와 별 차이가 없는데, 왜 느린속도로 나오는지 잘... ;;;

https://leetcode.com/problems/merge-sorted-array/description Q. 주어진 정렬된 배열 nums1과 nums2를 오름차순으로 merge하라.  이때 nums1과 nums2에 각각 m과 n만큼의 유효한 값이 있다고 가정하고, 결과를 nums1에 넣어라.  Solution. 추가 버퍼 제한이 없으므로, 간단하게 유효한 길이만큼 비교 / 처리 한다.  public void Merge(int[] nums1, int m, int[] nums2, int n) { List ret = new List(); int idx1 = 0, idx2 = 0; for(int q = 0; q =n) val = nums1[idx1++]; e..

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/rotate-array/description Q. 정수배열 nums가 주어질 때, k 만큼 배열을 rotate하여라. 추가 메모리를 사용하지 말아라.   Solution.  고전과도 같은 문제이다.   추가 메모리를 사용할 수 있다면, 간단하다.  오프셋 k 만큼 이동시켜 새 버퍼에 쓰면 된다.   추가 메모리를 쓰지 않으므로, 다른 접근이 필요하고, 이에 대해 알려진 알고리즘을 쓴다.   배열 전체를 reverse한다.  앞에서 k 개 만큼 reverse한다.  이후 위치에서 array.Length - k 만큼 reverse한다.   이것이 결과가 된다.   만약 문제 질의가 left로 회전하지 않고 right로 회전한다면 어떨까? 그 경우도 약간의..

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을 뺀다...