오뚝이개발자

문제 https://leetcode.com/problems/3sum/ 3Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 나의 풀이 리트코드 풀이를 하다가 굉장히 재미있는 문제가 있어 가져와봤다. 문제는 간단하다. 리스트와 타겟이 주어지면 그 리스트의 3개의 원소의 합이 타겟과 같아지는 그룹을 return하는 문제다. 여기서 포인트는 단순히 3중 for문으로 구현하면 시간초과가 난다는 것이다. 다른 방법을 고안해야 하는데 그 풀이가 굉장히 흥미롭다. tw..

문제 https://leetcode.com/problems/integer-to-roman/ Integer to Roman - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 나의 풀이 2가지 방법으로 풀이했다. 첫 번째 방법은 좀 naive한 풀이이고, 두 번째 방법은 변환의 규칙을 파악한 풀이이다. SOL 1) 문제에서 주어진 조건이 num의 범위가 [1,3999]이므로 이 범위 안에서만 변환을 생각하면 된다. 예컨대, 256을 변환하려면 200+50+6으로 분..

"abc"와 "bca"는 Anagram이다. anagram이란 이처럼 size가 같고, 같은 알파벳으로 이루어진 문자열을 말한다. 그럼 이러한 anagram을 찾으려면 어떠한 알고리즘을 써야할까? 가령 s="abcdebacb", p="cab"일 때, s에서 p와 anagram인 문자열의 인덱스를 찾는다고 해보자. 그럼 어떠한 것이 같아야 anagram이라고 할 수 있을까? size - p의 사이즈만큼 s를 slicing하면 되므로 간단!! 사용하는 알파벳 종류 등장하는 알파벳의 빈도수 이 땐, 2와 3을 비교하기 위해선 비트마스크를 사용하면 된다. 알파벳은 총 26개이므로 26개의 array를 만들고 각 알파벳의 등장 빈도수만큼 + 해준다. p="cab"이므로 p의 비트마스크 p_mask=[1,1,1,0..