junhwa100 님의 블로그

1. 문제 이해정수 배열 nums가 주어진다.다음 조건을 만족하는 세 수의 조합을 모두 리턴한다.- 세 수의 인덱스는 모두 다르다.- 세 수의 합은 0이다. 2. 풀이 과정먼저 오름차순으로 정렬한다. 배열을 순회하며 첫 번째 요소(a)를 고정한다. 이때 나머지 두 수의 합, target은 -a가 되어야 한다.반복문이 진행될 때, 이전에 이미 사용했던 같은 값의 a를 만나면 건너뛴다.(모든 조합을 이미 찾았기 때문) a를 고정한 상태에서 나머지 배열에 투 포인터를 적용한다.left, right 포인터를 만들어 배열 양측 끝의 인덱스로 초기화한다. left 만약 세 수의 합이 0이 되는 경우, 세 수의 조합을 정답 배열에 추가한다. left, right 포인터를 모두 업데이트한다.(left += 1, r..

1. 문제 이해문자열 배열과 최대 너비(maxWidth)가 주어진다.텍스트의 각 줄이 정확히 최대 너비만큼의 문자를 가지며 완전히 좌우 정렬되도록 포맷팅한다. (조건)- 각 줄에 최대한 많은 단어를 채워 넣는다. 필요한 경우 공백(' ')을 채워 넣는다.- 단어들 사이의 여분의 공백은 가능한 한 고르게 분배되어야 한다.- 한 줄의 공백 개수가 단어들 사이의 빈 공간에 균등하게 나누어지지 않는다면, 왼쪽에 있는 빈 공간이 오른쪽에 있는 빈 공간보다 크도록 한다.- 텍스트의 마지막 줄에 대해서는, 왼쪽 정렬이 되어야 하며, 단어들 사이에 여분의 공백을 삽입하지 않는다. 2. 풀이 과정주어진 단어 배열을 maxWidth가 초과하지 않도록 각 줄에 들어갈 단어들로 묶는다.단어들을 순회하면서 현재 줄에 단어를 ..

1. 문제 이해height라는 non-negative 정수 배열이 주어진다.각 배열의 요소는 벽의 높이를 의미한다.벽 사이에 갇힐 수 있는 최대 빗물의 양을 리턴한다. 2. 풀이 과정벽 사이에 갇히는 빗물의 양은 왼쪽에서 가장 높은 벽과 오른쪽에서 가장 높은 벽 중 더 낮은 벽에 의해 결정된다. max_left, max_right 배열을 만든다.각 배열의 i번째 요소는 각각 왼쪽, 오른쪽에서 시작하여 i번째 위치까지 가장 높은 벽의 높이를 나타낸다. i번째 위치에서 갇힐 수 있는 물의 양은 min(max_left[i], max_right[i]) - height[i]이 된다. 3. 전체 코드class Solution: def trap(self, height: List[int]) -> int: ..

1. 문제 이해n명의 아이들 각각의 rating을 나타내는 정수 배열 ratings가 주어진다. 아이들에게 사탕을 나누어 줄 때, 두 조건을 만족하는 가장 적게 사탕을 나누어 주는 경우의 사탕의 개수를 리턴한다.조건 1. 모두 각각 하나 이상의 사탕을 받는다.조건 2. rating이 높은 아이가 이웃(배열 상의)보다 더 많은 사탕을 받는다. 2. 풀이 과정최소 하나씩은 사탕을 받으므로 candies 배열을 만들어 1로 초기화한다. 단일 순회의 경우, i번째 아이의 사탕을 결정하려면 i+1번째 아이의 사탕이 필요하다.하지만 i+1번째 아이의 사탕은 결정되지 않았다는 문제점이 존재한다.(결정의 미래 의존성 문제) 따라서 투 패스 그리디 알고리즘을 떠올린다. 먼저 왼쪽에서 오른쪽으로 순회하여 사탕 수를 결..

1. 문제 이해정수 배열 citations가 주어진다.citations[i]는 리서처의 i번째 paper의 citation의 수를 의미한다.리서처의 h-index를 리턴한다.(h-index: 최소 h회 이상 인용된 논문을 최소 h편 이상 발표했을 때의 h의 최댓값) 2. 풀이 과정인용 횟수를 기준으로 내림차순으로 정렬한다. 정렬된 배열의 i+1개의 논문 중 citations[i]는 가장 낮은 인용 횟수를 갖는 논문이다. 만약 이 가장 낮은 인용 횟수가 논문 개수(i+1)보다 크거나 같다면, 그룹 내의 모든 논문이 i+1회 이상 인용 조건을 만족한다. 한 번의 순회 도중 citations[i] 3. 전체 코드class Solution: def hIndex(self, citations: List..

1. 문제 이해정수 배열 nums가 주어진다.배열의 첫 인덱스에서 시작한다.각 배열의 숫자는 해당 위치에서 최대로 이동(점프)할 수 있는 거리를 나타낸다.마지막 인덱스에 도달할 수 있는 최소 점프 수를 리턴한다.(넘어가도 괜찮다.)(마지막 인덱스에 도달할 수 있는 것은 보장된다.) 2. 풀이 과정최소 점프를 하기 위해서는 매번 가장 효율적으로 멀리 뛰어야 한다. 이미 점프를 한 번 수행했다고 가정 -> current_reach는 이 점프로 도달가능한 최대 인덱스우리가 i로 순회할 때, i가 current_reach에 도달한 순간은 현재 점프 범위의 끝에 왔다는 의미이다.-> 무조건 뛰어야 한다.-> jump 횟수를 1 증가시키고 current_reach를 farthest_reach로 갱신한다. i를 순..

1. 문제 이해정수 배열 nums가 주어진다.배열의 첫 인덱스에서 시작한다.각 배열의 숫자는 해당 위치에서 최대로 이동할 수 있는 거리를 나타낸다.마지막 인덱스에 도달할 수 있는 여부를 리턴한다.(넘어가도 괜찮다.) 2. 풀이 과정마지막 인덱스에 도달할 수 있는 가장 가까운 위치(그리디 알고리즘)를 역추적한다. 3. 전체 코드class Solution: def canJump(self, nums: List[int]) -> bool: n = len(nums) # 목표 지점 goal = n - 1 # 배열의 끝에서부터 시작하여 0까지 역순회 for i in range(n - 2, -1, -1): ..

1. 문제 이해prices라는 배열이 주어진다.배열의 i번째 요소는 i번째 날의 주식 가격이다.한 번 사고 한 번 파는 거래를 할 때, 얻을 수 있는 최대 수익을 리턴한다. 2. 풀이 과정배열을 한 번만 순회하면서 최대 이익을 알 수 있을까? 배열을 순회하는 동안 현재까지의 최소 매수 가격과 최대 이익을 추적한다. 현재 판다고 가정하고 현재 얻을 수 있는 이익을 계산한다.(현재 가격 - 최소 매수 가격)현재 얻을 수 있는 이익과 현재까지의 최대 이익을 비교하여 값을 갱신한다. 3. 전체 코드class Solution: def maxProfit(self, prices: List[int]) -> int: min_p = prices[0] if prices else 0 # 첫 번째 가격으로..

1. 문제 이해정수형 배열이 주어진다.배열의 크기가 n일 때, 개수가 n/2를 초과하는 요소를 리턴한다. 2. 풀이 과정defaultdict과 Counter 객체를 사용하는 풀이를 떠올렸다.-> 하지만 딕셔너리와 Counter 객체 생성에 공간이 필요해 공간 복잡도가 O(N)이 되는 문제가 있다. 공간 복잡도 O(1)로 해결해야 한다. 배열을 순회하며 과반수 요소 하나를 선정한다.후보가 등장하면 count를 1 증가시키고, 다른 요소가 등장하면 count를 1 감소시킨다.count가 0이 되면, 현재까지의 득표가 상쇄되었다는 뜻 -> 후보를 현재 보고 있는 새로운 요소로 교체하고 count를 1로 다시 설정한다. 보이어-무어 알고리즘: "과반수 요소가 아닌 모든 요소가 서로 짝을 지어 사라져도, 과반수..

1. 문제 이해정수 배열 nums와 정수 val이 주어진다. nums 내부의 val과 같은 요소를 in-place로 제거한다. 그리고 val과 같지 않은 요소의 개수(k)를 리턴한다. 배열 nums를 변경하여 배열의 첫 k개의 요소가 val과 같지 않은 요소가 되도록 한다.(이때 nums의 나머지 요소들은 중요하지 않다. nums의 크기도 중요하지 않다.) -> k개 뒤의 요소들도 제거해야 하는 듯 2. 풀이 과정val과 같은 요소를 찾기 위해 반복문으로 처음부터 배열을 순회하는 발상을 생각했다.-> 요소를 찾아 제거를 하더라도 제거한 요소 뒤의 요소들을 당기는데 O(N)이 소요된다. 따라서 최악의 경우 O(N^2) 시간 복잡도가 나올 수 있다. 잘못된 발상이다. 요소의 이동을 최소화해야 한다. 유효한..