target 이상이면서 가장 작은 조합을 구하고, 조합의 합과 target의 차이를 return 하라.
접근
N = 20이므로, 백트래킹으로 풀이하면 2 ** 20 ~= 1,000,000 정도일 것이다. 총합이 target 이상이 되면, target과의 차이를 현재 result 값과 비교하여 갱신한다.
모든 원소에 대하여 (추가하거나 / 추가하지 않거나)의 경우를 고려하고, 모든 원소를 탐색하면 result를 갱신한다.
코드
def solve(i, total):
global n, target, res
if i == n:
if total >= target:
res = min(res, total - target)
return
solve(i + 1, total + heights[i])
solve(i + 1, total)
T = int(input())
for tc in range(T):
n, target = map(int, input().split())
heights = list(map(int, input().split()))
res = 1e9
solve(0, 0)
print(f'#{tc + 1} {res}')
간단한 코드이지만, 2 * n개의 경우의 수를 고려하는 백트래킹 문제의 뼈대 코드인 듯하다.
시작점부터 도착점까지 가장 빠른 길을 찾아야 한다. -> BFS 섬(1)은 지나갈 수 없다. 소용돌이(2)는 지나갈 수 없다. 다만 한 번 통과한 경우 지나갈 수 있다. 소용돌이(2)는 0초부터 시작해서 2초 동안 유지되고 1초 동안 잠잠해지는 패턴을 반복한다.
접근
BFS 탐색을 하다가 소용돌이를 만났을 때는 판단을 해야 한다. 방문한 위치인 경우 -> 지날 수 있다 방문하지 않은 위치인 경우 time % 3 == 2인 경우, 지날 수 있다 이때 2를 0으로 바꿔야 한다. 한 번 방문한 뒤에는 언제든 지나갈 수 있기 때문에. 나머지의 경우, 지날 수 없다.
BFS 탐색을 하는 경우 큐에는 (x, y, time)이 담겨야 한다. 그래야 최단 경로를 판단할 수 있기 때문에 visited 배열은 (x, y, time)의 원소가 완벽하게 같은 경우 걸러낸다.
4방향 탐색이 아니라, 가만히 있기를 포함한 5방향 탐색이기 때문에, 방문 여부를 결정하기 위해 time이 필요하다.
코드
from collections import deque
dx = [1, -1, 0, 0, 0]
dy = [0, 0, 1, -1, 0]
def bfs(a, b, time):
q = deque()
q.append((a, b, time))
visited = []
visited.append((a, b, time))
while q:
x, y, t = q.popleft()
if x == ex and y == ey:
return t
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if matrix[nx][ny] == 1:
continue
if matrix[nx][ny] == 2:
if t % 3 == 2:
matrix[nx][ny] = 0
q.append((nx, ny, t + 1))
visited.append((nx, ny, t + 1))
else:
continue
if (nx, ny, t + 1) not in visited:
q.append((nx, ny, t + 1))
visited.append((nx, ny, t + 1))
testCase = int(input())
for tc in range(testCase):
n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]
sx, sy = map(int, input().split())
ex, ey = map(int, input().split())
result = bfs(sx, sy, 0)
print(f"#{tc + 1} {result}")
swea에서 해당 문제의 python 제출을 허용하지 않아, 정확한 정답 여부는 알 수 없다.
코테에서 유사한 문제를 풀었던 경험이 있어 어렵지 않게 풀었다.
"제자리에 있기"를 탐색 방향에 포함하는 것이 까다로운데, 시간까지 포함한 visited 배열로 관리하면 풀이할 수 있다.
from collections import deque
dx = [1, 1, -1, -1, 1, -1, 0, 0]
dy = [1, -1, 1, -1, 0, 0, 1, -1]
def openMatrix(x, y):
tmp = 0
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if matrix[nx][ny] == "*":
tmp += 1
matrix[x][y] = tmp
def clickZeroElement(a, b):
q = deque()
q.append([a, b])
matrix[a][b] = "*"
while q:
x, y = q.popleft()
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if matrix[nx][ny] == 0:
q.append([nx, ny])
matrix[nx][ny] = "*"
elif matrix[nx][ny] != "*":
matrix[nx][ny] = "*"
testCase = int(input())
for tc in range(testCase):
n = int(input())
matrix = [list(input()) for _ in range(n)]
total = 0
for i in range(n):
for j in range(n):
if matrix[i][j] == ".":
openMatrix(i, j)
for i in range(n):
for j in range(n):
if matrix[i][j] == 0:
clickZeroElement(i, j)
total += 1
for i in range(n):
for j in range(n):
if matrix[i][j] != "*":
total += 1
print(f"#{tc + 1} {total}")
전형적인 삼성 스타일의 문제인 듯하다.
그래도 아주 어렵지는 않다.
클릭 수가 최소가 되게 하는 방법을 고민하다보면, 완전 탐색으로는 불가능하다는 것을 알게 된다.
A non-empty array A consisting of N integers is given.
A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A.
The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].
Write a function:
def solution(A)
that, given an array A consisting of N integers, returns the maximum sum of any slice of A.
For example, given array A such that:
A[0] = 3 A[1] = 2 A[2] = -6
A[3] = 4 A[4] = 0
the function should return 5 because:
(3, 4) is a slice of A that has sum 4,
(2, 2) is a slice of A that has sum −6,
(0, 1) is a slice of A that has sum 5,
no other slice of A has sum greater than (0, 1).
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..1,000,000];
each element of array A is an integer within the range [−1,000,000..1,000,000];
the result will be an integer within the range [−2,147,483,648..2,147,483,647].
문제 분석
Maximum slice 유형.
번역을 한다면 '배열에서 최대가 되는 부분합' 정도가 되겠다.
배열의 길이가 1,000,000 이하이므로 반드시 O(N) 이하의 시간복잡도로 풀어야 함.
배열의 원소의 범위는 [-1,000,000 ... -1,000,000] 이다.
Codility의 교육 자료에 있는 O(N)으로 풀이하려 했으나, 추가적으로 원소가 음수인 경우를 처리해야 한다.
풀이
def solution(A):
max_ending = max_slice = A[0]
for i in range(1, len(A)):
max_ending = max(A[i], max_ending + A[i])
max_slice = max(max_ending, max_slice)
return max_slice
max_ending과 max_slice를 명확히 하고 넘어가야 이 간단한 코드를 이해할 수 있다.
max_ending: 현재 인덱스까지의 부분 배열중에서 가장 큰 합
max_slice: 현재까지 찾은 모든 부분 배열 중에서 가장 큰 합
좀 더 설명해 보자면,
max_ending은 반복문을 실행하는 각 단계에서, 현재 부분 배열(지금 배열이 최선이라고 가정하고 계산 중인)의 최대 합을 계산한다.
max_slice은 모든 max_ending을 비교하여(실제로는 모든 값을 나열하고 비교하지 않는다. 하지만 모든 max_ending은 max_slice에 게 도전하게 된다.) 최대 합을 계산한다.
한 줄씩 이해해 보자.
`max_ending = max_slice = A[0]`
초기화 하는 부분이다.
배열의 첫 번째 원소로 초기화 한다.
0으로 초기화를 하면, 모든 원소가 음수인 경우 0을 반환하는 문제가 생긴다.
`for i in range(1, len(A)):`
첫 번째 원소로 초기화 했으니, 첫 번째 원소는 건너뛴다.
`max_ending = max(A[i], max_ending + A[i])`
가장 고민을 많이 한 부분이다.
max_ending을 갱신할 때 무엇과 비교해야 하는가?
max() 함수의 두 번째 인자는 현재 부분 배열에 새로운 값을 더한 것이다. 자연스럽다.
def solution(A):
result = 0
min_value = 200001
for i in range(len(A)):
if min_value < A[i]: # 0 <= P <= Q < N일 때, A[Q] - A[P]가 양수인 경우만 판단. 음수는 어차피 0으로 반환해야 함.
result = max(result, A[i] - min_value)
min_value = min(min_value, A[i]) # 계산 이후 최솟값 갱신.
return result
# 이해
# 문자열로 된 숫자를 조합해서, 생성 가능한 숫자 중 가장 큰 수 return
# 풀이
# numbers를 문자열의 배열로 변환
# 내림차순 정렬
# 배열 내의 원소를 하나로 합침
# 문제
# 문제의 조건에 따르면 우선순위가 다음과 같아야 함. 3 > 30
# 그러나 일반적인 정렬은 다음과 같이 정렬됨. 30 > 3
# 문제의 의도대로 정렬이 되려면, 3은 33으로 취급해야 함.
def solution(numbers):
str_numbers = list(map(str, numbers))
str_numbers.sort(key=lambda x: x*3, reverse=True)
print(str_numbers)
answer = ''.join(str_numbers)
return str(int(answer))
# 이해
# 주어진 배열을 h를 기준으로 둘로 나눈다.
# 이때 h 이상인 배열의 길이가 h 이상이 된다. h 이하인 배열의 길이가 h 이하가 된다. 이것이 h-index.
# 이분탐색처럼 느껴지기도 한다.
# 그러나 n의 크기가 1000 이하 이므로 O(N ** 2)으로 완전탐색해도 되겠다.
# 풀이
# 배열을 정렬한다.
# 피봇 h를 정한다. 대략 길이의 절반쯤 위치의 인덱스로
# 피봇을 기준으로 큰 값과 작은 값을 계산한다.
# 피봇을 적당히 옮겨서 h의 최댓값을 구한다.
def solution(citations):
citations.sort()
n = len(citations)
h_index = 0
for i, citation in enumerate(citations):
h = min(citation, n - i)
h_index = max(h_index, h)
return h_index
이 문제도 꽤 오래 고민했다.
`h = min(citation, n - i)` 부분이 직관적으로 와닿지 않았다.
h-index의 정의에 따르면,
"논문 중 h번 이상 인용된 논문이 h편 이상이고, 나머지 논문이 h번 이하 인용되었을 때, h의 최대값이 h-index"이다.
이를 효과적으로 계산하기 위해 다음 두 값을 고려하자.
citation: 현재 논문의 인용 횟수
n - i: 현재 논문을 포함해서 그 이상 인용된 논문의 수. (여기서 n은 논문의 총 수, i는 현재 논문의 인덱스(0부터 시작))
예를 들어, 논문이 인용 횟수에 따라 오름차순으로 정렬된 상태에서, 특정 위치 i에서의 논문 인용 횟수가 10회라고 가정하자.
그리고 이 논문이 전체 논문 중에서 상위 15번째에 위치한다면 (n - i = 15), 다음 두 가지를 고려해야 한다.
현재 논문은 10회 인용됨.
현재 논문을 포함하여 15편의 논문이 10회 이상 인용 .
여기서 h-index의 조건을 만족시키기 위해 두 값 중 작은 값을 선택하자.
즉, min(10, 15) = 10이다.
이는 이 논문이 적어도 10번 이상 인용된 10편의 논문 중 하나임을 보장한다.
그러나 만약 이 논문의 인용 횟수가 20회이고, 같은 조건에서 n - i = 15라면, min(20, 15) = 15가 된다.
이는 15편의 논문이 최소 15회 이상 인용되었음을 보여주며, h-index가 될 수 있는 후보이다.
# 이해
# 최소 힙
# 값이 작은 2개를 pop()해서, 특정 공식으로 계산된 결과를 push()
# 최소 값이 K를 넘을 때까지 반복
# 풀이
# scoville = heapq.heapify(scoville)
# cnt = 0
# while True:
# scoville을 정렬하여, [0]번째 원소가 K보다 작으면 (heap은 subscription이 가능한가?)
# first = heapq.heappop(scoville)
# second = heapq.heappop(scoville)
# new = first + (second * 2)
# heapq.heappush(scoville, new)
# cnt += 1
# 작지 않으면 return cnt
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while len(scoville) >= 2:
if scoville[0] < K:
first = heapq.heappop(scoville)
second = heapq.heappop(scoville)
new = first + (second * 2)
heapq.heappush(scoville, new)
answer += 1
else:
return answer
return answer if scoville[0] >= K else -1
힙의 크기가 1 이하가 되면, 더 이상 계산을 진행할 수 없으므로 while의 범위를 설정한다.
while을 벗어난 뒤에도 마지막으로 조건을 만족하는지 확인한 뒤에 결과를 return한다.
# 이해 1
# 전체 작업 소요 시간의 평균이 최소가 되도록
# 매번 가능한 작업 중 소요 시간이 작은 것을 먼저 수행한다.
# 반례가 있다.
# [[0, 3], [4, 10], [5, 1], [6, 1]]
# 3, 14, 15, 16 == 11.25
# 3 + 10 + 10 + 10
# 3, 6, 7, 17 == 8.25
# 3, 1, 1, 10
# 끝나는 시간을 기준으로 해야 할 듯하다.
# 배열을 탐색하여, 원소 별로 끝나는 시간(시작 시간 + 소요 시간)을 구한다.
# 끝나는 시간이 빠른 것 순서대로 처리한다.
# 이해2
# 이해 1은 틀렸다 !! 정확히는 문제의 조건에 부합하지 않는다.
# <제한사항>의 마지막 항목: "하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다."
# 따라서 수행 가능한 작업이 있다면 즉시 실행한다.
# 수행 가능한 작업이 여러 개가 있다면 소요 시간이 짧은 것을 실행한다.
# 풀이
# 현재 시간을 표시할 변수 now = 0
# 총 대기 시간 변수 total_waiting_time = 0
# 현재 가능한 작업 큐 ready_queue = []
# 현재 index = 0
import heapq
def solution(jobs):
jobs.sort()
now = 0
total_waiting_time = 0
index = 0
ready_queue = []
while index < len(jobs) or ready_queue:
while index < len(jobs) and jobs[index][0] <= now: # 현재 시간 now보다 작은(실행 가능한) 작업 모두 추가
heapq.heappush(ready_queue, (jobs[index][1], jobs[index][0]))
index += 1
if ready_queue:
duration, start = heapq.heappop(ready_queue)
now += duration
total_waiting_time += now - start
else:
now = jobs[index][0]
return total_waiting_time // len(jobs)
3시간 이상 풀이한 듯하다 ..
적어도 1시간은 문제의 조건을 놓쳐서 헤맸다.
각 작업의 요청부터 종료 시간의 평균을 최소로 하려면, 작업이 종료되는 시간을 기준을 해야 한다고 판단했다.
가령 다음과 같은 테스트 케이스가 있다고 가정하자. `[[0, 3], [4, 10], [5, 1], [6, 1]]`
매 순간 가능한 작업 중 소요 시간이 가장 짧은 것을 선택하면 다음과 같다. `[0, 3] -> [4, 10] -> [5, 1] -> [6, 1]`
이 경우 요청부터 종료까지 3 + 10 + 10 + 10 -> 평균 8.25초가 소요된다.
끝나는 시간을 기준으로 가장 먼저 끝나는 작업을 선택하면 다음과 같다. `[0, 3] -> [5, 1] -> [6, 1] -> [4, 10]`
이 경우는 3 + 1 + 1 + 13 -> 평균 4.5초가 소요된다.
그러나 문제의 조건 중 다음을 놓쳤다. `하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.`
조건을 만족하려면, 반드시 `현재 가능한 작업 중 소요 시간이 가장 짧은 것을 선택`해서 수행하면 된다.
현재 작업의 시작 시간이 now 보다 작다면 ready_queue에 추가한다. `while index < len(jobs) and jobs[index][0] <= now:`
현재 작업의 시작 시간이 now 보다 크다면 now를 현재 작업의 시작 시간에 맞춘다. `else:`
# 이해
# 명령어를 받아서 힙을 구성
# 명령어에 따라 최솟값 혹은 최댓값을 pop()
# 모든 명령어를 수행하고 남은 힙의 최솟값과 최댓값을 return
# 풀이
# 명령어의 순서를 미리 기록한다.
# 가령 최솟값 삭제면 False, 최댓값 삭제면 True
# 힙에 추가하는 명령어를 실행할 때마다, 순서 배열을 보면서 최댓값 삭제(True)인 경우 -값을 추가한다.
# 모든 명령어는 최솟값 삭제로 실행한다.
import heapq
def solution(operations):
answer = []
heap = []
for operation in operations:
op, num = operation.split()
if op == "I":
heapq.heappush(heap, int(num))
elif heap:
if num == "-1":
heapq.heappop(heap)
else: # num == "1"
heap.remove(max(heap))
return [0, 0] if len(heap) == 0 else [max(heap), min(heap)]
O(NlogN) 풀이가 떠오르지 않아서 구글링을 했다. 다들 그냥 remove 함수를 사용한다.
O(N^2) 아닌가...? N == 10 ** 6이니까 10 ** 12로, 시간 초과 기준(10 ** 9)을 아득히 넘는다. 완성된 힙을 탐색하는 것이 아니라, 완성해가면서 탐색하는 것이기 때문에 가능한가보다.
다시 한번 느꼈다. 프로그래머스에서 문제 풀 때는 시간 복잡도는 신경 쓰는 것이 아니다. N이 1억이나 10억이면 이분 탐색 문제이고, 아니라면 일단 O(N ** 2)으로 풀이하자.
# 이해
# 스택에 연속된 숫자가 저장되면 안 됨.
# 풀이
# arr을 탐색하며 stack에 추가
# 추가하기 전, stack의 top과 같은 경우 pass, 다른 경우 push
def solution(arr):
stack = []
for elem in arr:
if stack:
if elem != stack[-1]:
stack.append(elem)
else:
stack.append(elem)
return stack
# 이해
# progresses의 원소는 100%를 달성하면 배포된다.
# 매일 speeds의 원소만큼 progress가 진행된다.
# 가장 앞에 있는 원소가 100%를 달성한 순간에, 100%를 달성한 모든 원소를 배포한다.
# 풀이
# progresses의 각 원소를 100에서 빼고, 그 값을 speeds로 나누어 남은 일자를 계산한다. remain_days: [Int]
# remain_days를 탐색하며, 내림차순으로 정렬된 경우 tmp에 더하고,
# 내림차순이 깨진 순간 tmp를 answer에 append하고, tmp를 초기화 한다.
# answer를 return한다.
import math
def solution(progresses, speeds):
answer = []
remain_days = [math.ceil((100 - progress) / speed) for progress, speed in zip(progresses, speeds)]
current_max_day = remain_days[0]
count = 0
for day in remain_days:
if day <= current_max_day:
count += 1
else:
answer.append(count)
current_max_day = day
count = 1
answer.append(count)
return answer
`zip()` 함수는 여러 개의 iterators를 인자로 받아, 인덱스를 기준으로 짝 지은 튜플을 반환하는 함수이다.
위 코드에서 math.ceil()는 필수적이지 않다. `-((progress - 100) // speed)`의 형태로 작성해도 같은 결과이다.
# 이해
# priorities 배열을 우선순위에 따라 pop() 할 때,
# location 위치에 있는 원소가 몇 번째로 pop() 되는지 return
# 풀이
# max_value = max(priorities)
# priorities_with_hash = [[i, hash(i)] for i in priorities]
# max_value_hash = priorities_with_hash[location][1]
# order = 0
# while len(priorities_with_hash) >= 0:
# current = popleft()
# current[0] >= max_value,
# if current[1] == max_value_hash:
# return order
# order += 1
# current[0] < max_value:
# priorities_with_hash.append(current)
from collections import deque
import random
def solution(priorities, location):
order = 1
priorities_with_hash = deque([[priorities[i], i] for i in range(len(priorities))])
max_value = max(priorities)
target_hash = priorities_with_hash[location][1]
while len(priorities_with_hash) >= 0:
current = priorities_with_hash.popleft()
if current[0] >= max_value:
if current[1] == target_hash:
return order
max_value = max([elem[0] for elem in priorities_with_hash])
order += 1
else: # current[0] < max_value
priorities_with_hash.append(current)
return order
더 나은 풀이
def solution(priorities, location):
queue = [(i,p) for i,p in enumerate(priorities)]
answer = 0
while True:
cur = queue.pop(0)
if any(cur[1] < q[1] for q in queue):
queue.append(cur)
else:
answer += 1
if cur[0] == location:
return answer
`any()`: 인자로 받은 iterators 중에 하나라도 True이면, 전체를 True로 반환한다.
from collections import deque
def solution(prices):
queue = deque(prices)
answer = []
while queue:
price = queue.popleft()
sec = 0
for q in queue:
sec += 1
if price > q:
break
answer.append(sec)
return answer
복잡할 것이 없는 풀이이다.
그러나 30분 동안 고민했다.
주어진 배열의 길이가 10 ** 5이어서, O(N ** 2)은 시간 초과가 발생할 수 있다고 판단했기 때문이다.
실제로는 시간 초과가 발생하지 않았다.
계속해서 queue의 크기를 줄여나가기 때문인 듯하다.
실제로 코테에서도 웬만한 크기(10 ** 4 ~ 10 ** 5)라면 일단 완전탐색으로 풀이하자.
그렇게 부분 점수 먼저 확보해 놓고, 시간복잡도를 개선하는 것이 훨씬 현실적인 코테 접근법이다.
더 나은 풀이 (스택)
# 이해
# 배열의 각 원소가 오름차순이 지속되는 길이를 각각 return
# 다음 원소와 비교하여, 값이 작아지지 않을 때마다 += 1
# 일단 지속 시간을 1초 증가시키고, 그 뒤에 오름차순 여부를 판단한다.
# 마지막 원소는 0초이다.
# 풀이
# 일단 이중 반복문으로 풀자
from collections import deque
def solution(prices):
length = len(prices)
answer = [i for i in range(length - 1, -1, -1)]
stack = [0]
for i in range(1, length):
while stack and prices[stack[-1]] > prices[i]:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answer
