가벼운 마음으로 Hexspeak 상기 문제를 풀었는데, 위의 문제는 n 이라는 integer value를 주고 1과 0 그리고 16진수 영어로만 표현 가능한 값인가? 를 알아내는 문제였다. 예를 들자면 $1005 = \text{0x3ED}$ 로 표현 할 수 있다. 여기에 3이라는 숫자가 들어갔기 때문에 오류이다. $6336 = \text{0xCDE}$ 이기 때문에 답으로 CDE를 돌려주면 된다. 위의 문제를 풀기위해서는 간단하게 toString을 사용하면 된다. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/toString let baseTenInt = 10; console.log(bas..

Longest Repeating Character Replacement 문제 내용 주어진 문자열에서 k만큼의 문자를 다른 문자로 교체가 가능하다고 했을 때, 동일한 문자로 가장 길게 만들 수 있는 문자의 길이는 얼마인가? 접근 방법 Brute Force 가장 쉬운 방법은 모든 point에서 loop를 도는 것이다. 위와 같은 문자열이 있을 때, k 즉 교체 가능한 문자열의 횟수는 1회라고 생각해 보자. 이렇게해서 4라는 길이가 나올 수 있다. 그럼 다시 그다음 A에서 실행해 보자. 앞서와 동일한 종료점을 갖는다. 다음은 B이다 B도 4라는 길이가 나올 수 있다. 정답은 4가 되게 된다. 이 방식은 O(N^2) 이 된다. 이것을 최적화가 필요하다. Memorization Brute Force의 내용을 보면..

Power of Four 문제 내용 주어진 수가 4의 제곱으로 표현 가능한가? 접근 방법 주어진 수를 4로 나누어서 최종 값이 1이 되면 된다. var isPowerOfFour = function(n) { if(n < 0) return false; while(1 < n) n /= 4; return n=== 1? true : false; }; 별거 아닌것 같긴한데 2가지 방법으로 접근이 더 가능해서 글을 남기려고 한다. 수학적 접근 방법 $$n = 4^x$$ 로 표현 할 수 있다. 양쪽에 $log_4$ 를 해주면 $log_4 n = log_4 4^x$ 로 표현 할 수 있고 이것을 더 진행하면 $log_4 n = x log_4 4$ $log_4 n = x$ $log_2^2 n = x$ ..

Data Stream as Disjoint Intervals 문제 내용 Class 를 만드는 문제이다. Class의 목표는 다음과 같다. addNum(int) : integer를 입력 받는다 getIntervals() : 입력받은 integer의 배열이 1의 차이로 연결되어 있다면 [start,end]로 연결되어 있는 값의 시작값과 연결이 끝나는 끊값으로 구성된 2차원 배열을 return 한다. 접근 방법 해당 문제는 다음과 같은 constraints를 갖는다. $ 0

Hamming Distance 문제 내용 Hamming Distance를 구하라 접근 방법 Hamming distance는 기본적으로 두개의 integer를 bit로 변환했을 때, 몇개의 bit가 다른지 알아내는 문제이다. 예를 들어 2진수로 110001101 111000011 이 있다고 하면 다른 값은 위의 붉은색이 된다. 즉, 두개의 값의 차이가 나는 값, XOR로 대표 될 수 있다. 위의 값을 XOR해보자. 001001110 이 된다. 이제 1의 갯수를 구하면 답이 된다. 가장 쉬운 방법은 1bit씩 오른쪽으로 shift하면서 끝 값이 1인지만 확인 하면 된다. var hammingDistance = function(x, y) { let xor = x ^ y; let count = 0; while(..

Different Ways to Add Parentheses 문제 내용 숫자와 +,-,* 3개의 Operation으로 구성된 문장이 있다. 임의로 ()

Confirmation Rate 문제 내용 Signups Table과 Confirmations Table 두개가 있을 때 모든 user에 대한 login 성공 확률을 나타내라. Signups Table Column Name Type user_id int time_stamp datetime Confirmations Table Column Name Type user_id int time_stamp datetime action ENUM ('confirmed', 'timeout') 접근 방법 union all 을 이용해서 접근 가능하다. 우선 필요한것은 Confirmations Table을 이용해서 user별 'confirmed'의 횟수와 'timeout'을 포함한 전체 횟수를 구하는 것이다. 궁극적으로 성공확..

2021.05.02 - [Problem Solving] - 2진수 최 우측 1의 자리 찾아내기 우측 찾기에 이어서 최 좌측 1자리를 찾을 일이 있어서 Blog를 남겨 본다. 가장 쉬운 방법은 while(1 >1; } 일 것이다. 이것은 O(N)이 필요 함으로 속도를 높이는 방법을 찾아 보자. ori |= (ori >> 1); ori |= (ori >> 2); ori |= (ori >> 4); ori |= (ori >> 8); ori |= (ori >> 16); return ori - (ori>>1) 위는 O(Log N)의 속도로 가장 좌측 1을 찾게 되는 방법이다. 기본적인 아이디어는 copy and paste다. 10000001 이 있을 경우 1b..

Super Egg Drop 문제 내용 N개의 달걀이 있다. K 층으로 이루어진 빌딩이 있다. 달걀은 해당 빌딩의 특정 층 F에서 깨지기 시작한다. N개의 달걀을 이용해서 F 층을 찾을 수 있는 가장 적은 시도 횟수를 갖는 방법 횟수를 찾아라 접근 방법 문제 자체를 이해하는데 굉장히 난해했다. 이 문제는 굉장히 오래된 문제인데, 아직도 Youtube나 Article을 보면 적당히 설명이 된 글이 많지 않았다. 어떤 글은 너무 쉬운 부분만 설명하거나, 또 어떤 글은 굉장히 어려운 말로 설명되어있었다. 우선 문제를 이해하자. 5층으로 이루어진 빌딩이 있고 달걀 1개가 주어졌다면 몇번 욺직여야 f를 찾을 수 있을까? 한개의 달걀로 f를 무조건 찾을 수 있는 방법은 5층에서 부터 2층사이에 달걀을 던지면 안된다는..