본문 바로가기

알고리즘 문제/Leetcode283

[leetcode][645] Set Mismatch 문제 : leetcode.com/problems/set-mismatch/ 1~n 까지 모든 정수를 포함하는 배열이 있다. 오류로 인해 숫자 하나가 1~n 중 다른 숫자로 변경되었다. 즉, 변경된 배열에는 누락된 숫자와 중복(2번 발생)된 숫자가 존재한다. 변경된 배열이 주어질 때 중복된 수와 누락된 수를 구하여라. n크기의 등장횟수를 저장하는 배열을 만든다. 입력 배열을 탐색하면서 등장횟수를 갱신한다. 등장횟수가 2번인 것과 0번인 수가 정답이 된다. 시간복잡도와 공간복잡도 모두 O(N). 등장하지 않거나 두 번 등장하는 수가 한 개만 존재한다고 하였기에 비트를 쓰거나 수학적으로 접근이 가능할거 같아서 토론글을 둘러보았다. 그러다 좋은 글 있어서 해당 글 보고 정리한 방법. 따봉따봉 학창시절 배운 수학공.. 2021. 3. 3.
[leetcode][575] Distribute Candies 문제 : leetcode.com/problems/distribute-candies/ n개의 사탕타입 배열이 주어진다. n/2개의 사탕만 먹을 때, 가장 다양하게 먹을 수 있는 사탕 타입의 수를 구하라. n/2와 사탕타입의 개수 중 최소값이 정답이 된다. 배열을 탐색하면서 set에 타입을 저장한다. set의 크기가 사탕 타입의 개수가 된다. 시간복잡도는 O(N). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/575.%20Distribute%20Candies.cpp 2021. 3. 2.
[Leetcode][581] Shortest Unsorted Continuous Subarray 문제 : leetcode.com/problems/shortest-unsorted-continuous-subarray/ 정수형 배열이 주어질 때, 연속적인 서브배열을 오름차순 정렬하면 전체 배열이 오름차순 정렬이 되게 하는 서브배열의 최소 길이를 구하라. 가장 간단한 방법은 주어진 배열을 오름차순 정렬한뒤 정렬한 배열과 기존 배열을 비교하면서 다른 요소값을 가지는 인덱스의 최소 값과 최대 값을 구한다. 최대값 - 최소값 + 1이 정답이된다. 이 방법으로 한 경우 정렬이 필요하므로 O(NlogN)의 시간이 소요된다. 문제에서는 선형복잡도로 풀 수 있는지 물었으므로 좀 더 효율적인 방법을 살펴보자. [2,6,4,8,10,9,15] 를 예로 들어보자. 배열이 오름차순 정렬이라고 가정한다면, 왼쪽에서 오른쪽으로 .. 2021. 2. 26.
[leetcode][13] Roman to Integer 문제 : leetcode.com/problems/roman-to-integer/ 로마 문자를 숫자로 1:1 매칭하는 map을 하나 만든다. 문자열 s를 처음부터 탐색하면서 문자를 숫자로 바꾼 결과(let, value)를 stack에 넣는다. 만약 value가 1이 아니라면 바로전 값이 1, 10, 100인지 확인하고 그 값의 5, 10의 배수가 value와 맞는지 비교해야 한다. 이를 위해 바로 전 값을 stack의 top에서 가져온 뒤 판단한다. 만약 마이너스가 되는 경우라면 value에 top 값을 빼주면서 stack을 pop 해준다. value를 적절히 갱신 후 stack에 push 한다. 문자열 s를 모두 탐색해서 stack을 다 채웠다면 stack의 모든 숫자를 더한 값이 정답이 된다. 시간복잡.. 2021. 2. 21.
[leetcode][594] Longest Harmonious Subsequence.cpp 문제 : leetcode.com/problems/longest-harmonious-subsequence/ 배열이 주어질 때, 최대값과 최소값이 정확히 1차이가 나는 subsequence들의 최대 길이를 구해라. 결국 길이가 1차이나는 요소들의 발생횟수들의 합의 최대값을 구하는 문제. 배열을 탐색하면서 요소 값을 key, 나온 횟수를 value로 가지는 map을 만들어 갱신한다. map을 모두 채웠으면 map을 모두 탐색하면서 탐색중인 map의 key값 + 1을 map에서 찾아서 만약 없으면 최대, 최소 차이가 1인 서브시퀀스를 만들수 없으므로 다음 map요소를 탐색한다. 만일 있다면 map[key] + map[key+1] 한 값들의 최대값을 구하면 정답이 된다. 시간복잡도는 O(N). N은 배열의 길이... 2021. 2. 4.
[leetcode][191] Number of 1 Bits 문제 : leetcode.com/problems/number-of-1-bits/ 부호없는 정수 값이 input 값으로 주어질 때, 1비트 수를 구해라. brian kernighan's algorithm을 사용. n & (n-1) 연산을 n이 0이 될 때까지 반복한다. 연산 횟수가 1의 개수가된다. 시간복잡도는 O(logN). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/191.%20Number%20of%201%20Bits.cpp 2021. 2. 2.

티스토리툴바