본문 바로가기

easy67

[Leetcode][696] Count Binary Substrings 문제 : https://leetcode.com/problems/count-binary-substrings/ 0과 1로 이루어진 문자열에서 연속적으로 같은 숫자의 문자가 나오는 부분문자열들의 수를 구하라. 부분문자열 예 : 0011, 01, 10 / 안되는 예 : 1010 (같은 숫자가 연속적이지 않음). 11100 (숫자들의 등장횟수가 다름) 동일한 부분 문자열이라도 여러번 발생하면 발생한 횟수만큼 정답에 더해준다. 문자열을 탐색하면서 연속적으로 나오는 0과 1의 수를 센다. 예를 들어, "00110011"이라면 인덱스 / 숫자 0 1 0 (0) 1 0 1 (0) 2 0 2 (1) 2 1 3 (1) 2 2 4 (0) 1 2 5 (0) 2 2 6 (1) 2 1 7 (1) 2 2 위와 같이 채워진다. 인덱스.. 2021. 4. 24.
[Leetcode][160] Intersection of Two Linked Lists 문제 : leetcode.com/problems/intersection-of-two-linked-lists/ 2개의 연결리스트가 주어질 때, 교차점이 시작되는 노드를 찾아라. 교차점이 시작되는 노드 이후의 노드들은 두 개의 연결리스트에서 모두 같다. 예시로 나온 listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]로 살펴보자. listA-listB listB-listA 를 순서대로 연결한뒤 앞에서부터 하나씩 비교하다보면 교차점이 시작되는 노드를 찾을 수 있다. [4,1,8,4,5-5,6,1,8,4,5] [5,6,1,8,4,5-4,1,8,4,5] 위와같이 연결해서 앞에서부터 하나씩 비교하면 언젠가는 교차점이 되는 8을 찾을 수 있다. 만일 탐색이 끝날때까지 같아지는 노드를 찾을 수 .. 2021. 3. 4.
[leetcode][268] Missing Number 문제 : leetcode.com/problems/missing-number/ 고유한 숫자 배열 nums가 주어질 때, 0~n 까지 수 중 누락된 수를 구하라. 누락된 수는 0~n까지 수들의 합에서 nums배열의 합을 뺀 값과 같다. 0~n까지 수들의 합은 등차수열의 합 공식으로 n(n+1)/2로 구할 수 있고, nums배열의 합은 배열을 한 번 탐색하면서 구할 수 있다. 시간복잡도는 O(n), 공간복잡도는 O(1). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/268.%20Missing%20Number.cpp 2021. 3. 3.
[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][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.

티스토리툴바