Algorithm/LeetCode12 [004]Jewels and Stones 문제: https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/534/week-1-may-1st-may-7th/3317/ 'a' ~ 'Z'까지의 알파벳의 상태를 관리하기 위해 아스키코드를 포함한 1바이트를 사용하면 됩니다. 알파벳이 나타날 때 마다 배열의 갯수를 증가시킨 후 쥬얼리 값에 모두 합산해주면 됩니다. class Solution { public: int numJewelsInStones(string J, string S) { int stoneState[128] = {0,}; for (int i = 0; i < S.length(); ++i) { int idx = S[i]; stoneState[idx]++; } int ret = 0;.. 2020. 5. 17. [003]First Bad Version 문제: https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/534/week-1-may-1st-may-7th/3316/ 이분 탐색 문제입니다. mid를 구한 후 Bad Version이 나왔다면, 상한을 en = mid 으로 줄여서 탐색범위를 절반씩 줄여나가면 됩니다. 시간복잡도 O(logN) // The API isBadVersion is defined for you. // bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { long long int st, en,mid, before; st = 0; en = (long long int).. 2020. 5. 16. [002]Single Number 문제: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3283/ 숫자 배열에서 하나의 값만 1개 들어있고, 나머지 값들은 2개씩 들어있을 때 1개만 있는 값을 찾는 문제. std::map을 생성한 뒤 배열을 순회하면서, map에 이미 있는 숫자면 pop, 없는 숫자면 insert. 그렇게 순회하고 나면 map에는 1개인 값만 남게 됩니다. class Solution { public: int singleNumber(vector& nums) { map numbers; int answer; for (int num : nums) { if (numbers.find(num) == numbers.end()) numb.. 2020. 5. 10. [001]Subarray Sum Equals K 문제: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/531/week-4/3307/ array의 부분합이 K인 구간을 O(N)만에 구하는 알고리즘. 구하고자 하는 것: array[L...R] = K인 구간의 갯수 1st. array[L...R] = K (=) prefixSum[R] - prefixSum[L-1] = K (prefixSum은 ∑ array[0...i]) 2nd. prefixSum[R] - prefixSum[L-1] = K 에서 K와 prefixSum[L-1]의 위치를 바꾸면, (=) prefixSum[R] - K = prefixSum[L-1]이 성립합니다. 3rd. prefixSum[R]은 ∑ array[0... 2020. 5. 10. 이전 1 2 3 다음
