Study Blog

문제 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 예제1 입력 [0,1,0,2,1,0,1,3,2,1,2,1] 출력 6 풀이1 투 포인터를 이용한 풀이 이 문제는 높이와 너비 모든 공간을 차례대로 모두 살펴보면 O(n^2)에 풀이가 가능하다. 하지만 시간 복잡도가 너무 높기 때문에 좀 더 효율적인 풀이를 찾아야 한다. 투 포인터와 스택으로 O(n) 풀이를 할 것이다. 먼저 투 포인터 풀이부터 살펴보자. 이 풀이 방법은 현재 높이와 이전 높이와의 차이만큼 물 높이 volume을 더해 나간다. 이후에는 왼쪽 포인터가 크다면 오른쪽 포인터를 이동시키고, 오른쪽 포인터가 크다면 왼쪽 포인터를 이동시킨다. 투 포인터를 이용한 풀이의 코드는 다음과 같다. def trap(height: li..

문제 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. 예제1 입력 nums = [2, 7, 11, 15], target = 9 출력 [0, 1] 설명 nums[0] + nums[1] = 2 + 7 = 9 따라서 0, 1을 리턴한다. 풀이1 브루트 포스로 계산 이 문제는 최적화할 수 있는 방법이 여러가지로 숨어 있어서 코딩 인터뷰 시 높은 빈도로 출제되는 문제다. 이 문제에 대한 풀이는 쉽게 생각해보았을때 배열을 2번 반복하면서 모든 조합을 더해서 일일이 확인해보는 무차별 대입 방식인 브루트 포스로 확인할 수 있다. 정답을 찾기 위해 2부터 시작해 다른 요소들인 7, 11, 15를 차례대로 모두 비교한다. 즉 2 + 7, 2 + 11, 2 + 15와 같은 식으로 마지막 요소들까지 모두 차..

문제 가장 긴 팰린드롬 부분 문자열을 출력하라. 예제1 입력 "babad" 출력 "bab" 예제2 입력 "cbbd" 출력 "bb" 이 문제는 다이나믹 프로그래밍을 이용한 풀이도 가능하지만 직관적인 이해가 어렵고, 실행 속도가 늦다. 따라서 여기서는 훨씬 더 성능이 좋은 투 포인터가 중앙을 중심으로 확장하는 형태로 풀이해본다. 팰린드롬 판별만 하면 되기 때문에 앞, 뒤 문자가 같을 때 중앙을 중심으로 점점 확장해 나가면서 가장 긴 팰린드롬을 판별하는 알고리즘을 구현해본다. 알고리즘의 진행 순서는 다음과 같다. 원본 문자열과 뒤집은 문자열이 동일한 경우(aba, 131 등등...)나 문자열의 길이가 1 이하인 경우는 들어온 문자열을 그대로 리턴 길이가 2인 포인터를 전진하며 팰린드롬 찾기 길이가 3인 포인터..

문제 문자열 배열을 받아 애너그램 단위로 그룹핑하라. 예제1 입력 ["eat", "tea", "tan", "ate", "nat", "bat"] 출력 [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] 이 문제를 해결하는 방법은 먼저 입력으로 들어온 값을 정렬해보고, 각 정렬한 값의 딕셔너리키의 값에 입력값을 추가하는 것이다. 말로 표현하는 것이 어려우니 아래 그림을 보면 쉽게 이해할 수 있다. 먼저 입력으로 들어온 strs 리스트 내부의 원소를 하나씩 word로 옮기고, word에 들어온 원소를 정렬한 후 다시 문자열로 합치고 딕셔너리의 값에 추가한다. 키와 값이 추가된 딕셔너리가 완성되었다면, 각 값들을 출력한다. 코드로 위 과정을 진행하면 이 문제를 풀 수 있게 된다..

문제 금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며, 구두점(마침표, 쉼표 등) 또한 무시한다. 예제1 입력 input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit." banned = ["hit"] 출력 output: "ball" 풀이1 리스트 컴프리헨션과 defaultdict 모듈을 사용하기 입력값에는 대소문자가 섞여 있으며 쉼표 등 구두점이 존재한다. 따라서 데이터 클렌징을 이용해 입력값에 대한 전처리 작업이 필요하다. 좀 더 편리하게 처리하기 위해 정규식을 섞어 쓰면 다음과 같이 처리할 수 있다. words = [word for word in re.sub(r'[^\w]', ' '..