비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.
기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다. 부분 수열의 합은 k입니다. 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다. 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.
수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.
제한 사항 1. 5 ≤ sequence의 길이 ≤ 1,000,000 2. 1 ≤ sequence의 원소 ≤ 1,000 3. sequence는 비내림차순으로 정렬되어 있습니다. 4. 5 ≤ k ≤ 1,000,000,000 5. k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
부분 수열의 합을 구할 때 사용하는 대표적인 자료구조로 먼저 누적합을 생각했습니다. 하지만 부분 구간 합을 구하고 길이가 최소인 구간까지 구하니 이중 반복문으로 시간복잡도 O(n^2)이 발생했습니다. 시간 초과가 발생했고 이는 모든 가능한 인덱스 쌍을 탐색하면서 발생하는 문제였습니다.
반면 두 포인터를 이용하여 인덱스를 탐색해 나가는 투 포인터 기법의 시간 복잡도는 O(n)입니다. 한 번의 순회로 모든 연속 부분의 구간을 탐색 + 조건을 만족하는 최소 길이 구간을 동시에 찾을 수 있기 때문입니다. 누적합이 아닌 투 포인터를 사용해야 하는 이유를 정리하면 다음과 같습니다.
연속된 구간을 다룹니다.
합이 k인 부분 수열 중 길이가 최소인 것을 찾아야 합니다. 누적합으로는 가능한 모든 구간을 구해야 하기 때문에 시간 복잡도가 O(n^2)이 되지만, 투 포인터 기법은 한번의 순회로 최소 길이 부분 수열을 찾을 수 있어 시간 복잡도가 O(n)이 됩니다.
시작 인덱스가 작은 부분 수열을 선택해야 하는데, 투 포인터는 자연스럽게 가장 앞쪽의 값을 찾아줍니다.
위 문제에서 투 포인터 기법을 사용한 문제 해결 과정은 다음과 같습니다.
left, right 포인터를 사용해 부분 수열을 더해 나갑니다.
right 포인터를 오른쪽으로 이동시키며 값을 sum_val 변수에 누적하여 더합니다.
sum_val 값이 원하는 값인 k보다 클 경우 부분 수열의 범위를 좁혀주어야 합니다.
이 때 left 포인터를 오른쪽으로 이동시키면서 sum_val에서 해당 left 이동 값을 빼줍니다.
sum_val 값이 k와 같은 경우, 현재 부분 수열의 길이를 확인하고 수열 길이 최소 값를 판별합니다.
최소 값이 업데이트 되었다면 해당 left, right 값을 정답 인덱스로 저장합니다.
반복문을 끝까지 순회하여 최소 값을 판별한 후 최종 정답 인덱스를 리턴해줍니다.
요약하면 누적합은 특정 구간의 합을 효율적으로 계산해야 하는 문제에서는 유용하게 사용됩니다. 하지만 특정 조건이 추가된다면 투 포인터나 슬라이딩 윈도우 기법 등을 함께 사용해주는 것이 효율적입니다.
💡 내가 해결한 방식은?
누적합을 이용한 풀이 (시간 초과)
def solution(sequence, k):
answer = []
p_sum = []
seq_list = []
start, end = 0, 0
# 누적합 구현
for i in range(len(sequence)):
p_sum.append(sum(sequence[:i+1]))
for start in range(len(sequence)):
for end in range(len(sequence)):
if start > end : continue
if start == end and p_sum[start] == k:
seq_list.append([0, start])
if p_sum[end] - p_sum[start] == k:
seq_list.append([start+1, end])
seq_list.sort()
temp = [sl[1] - sl[0] for sl in seq_list]
return seq_list[temp.index(min(temp))]
투 포인터 활용한 풀이
def solution(sequence, k):
answer = []
left, right = 0, 0
start, end = 0, 0
p_sum = 0
min_len = float('inf')
# fast, slow 투 포인터 순회
# outer loop right 순회
while right < len(sequence):
p_sum += sequence[right]
# right 값이 부분 수열 합보다 클 경우
while p_sum > k:
# left 값 빼주면서 이동
p_sum -= sequence[left]
left += 1
# 부분 수열의 합 k 일 경우
if p_sum == k:
# 부분 수열의 길이
curr_len = right - left + 1
# 최소 값보다 현재 길이가 짧을 경우
# 최소 값과 현재 길이가 같으면서 left 값이 start 값보다 작을 경우
# 여기서 left는 가장 최근 부분 수열, start는 기존 수열에서 left
if curr_len < min_len:
min_len = curr_len
start, end = left, right
right += 1
return [start, end]
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.
조각은 한 번에 하나씩 채워 넣습니다. 조각을 회전시킬 수 있습니다. 조각을 뒤집을 수는 없습니다. 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
다음은 퍼즐 조각을 채우는 예시입니다
위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.
3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다. 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.
다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.
최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.
현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.
제한 사항 1. 3 ≤ game_board의 행 길이 ≤ 50 2. game_board의 각 열 길이 = game_board의 행 길이 2-1. 즉, 게임 보드는 정사각 격자 모양입니다. 2-2. game_board의 모든 원소는 0 또는 1입니다. 2-3. 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다. 2-4. 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다. 3. table의 행 길이 = game_board의 행 길이 4. table의 각 열 길이 = table의 행 길이 4-1. 즉, 테이블은 game_board와 같은 크기의 정사각 격자 모양입니다. 4-2. table의 모든 원소는 0 또는 1입니다. 4-3. 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다. 4-4. 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다. 5. game_board에는 반드시 하나 이상의 빈칸이 있습니다. 6. table에는 반드시 하나 이상의 블록이 놓여 있습니다.
문제 회고
💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지
💡 내가 해결한 방식은?
✍️ TIL
두 번째 문제에서 누적합이 만능이 아니었다는 사실을 처음 알게 되었다. 반복문에서 누적합을 사용해 시간 초과를 해결했었는데 조건이 추가되면 누적합도 정답이 아니라는 것을 알았다. 투 포인터 기법을 적용했을 때 얻을 수 있는 장점과 누적합과의 차이를 명확히 알 수 있었다. 쉽지 않은 문제였던 만큼 시간을 다소 투자했지만 투 포인터에 대한 충분한 학습이 되었다고 생각한다.
