문제 소개
모든 값이 0으로 초기화된 n × m 크기의 행렬이 있다고 가정해 보겠습니다. 그리고 특정 행 위치와 열 위치를 담고 있는 쌍(pair)들의 목록이 주어집니다. 목록의 각 항목 i에 대해, 행 번호가 해당 항목의 행 값보다 작고, 열 번호가 해당 항목의 열 값보다 작은 모든 셀의 값이 1씩 증가합니다.
목록의 모든 요소를 순회한 후에는, 행렬에서 최댓값을 포함하는 셀이 몇 개인지 구해야 합니다. (행과 열 인덱스는 0부터 시작합니다.)
예를 들어 입력이 input_list = [[3, 5], [4, 6], [5, 3]]이라면 출력은 9가 됩니다. 이를 위해 5 × 6 크기의 행렬을 생각해 봅시다.
동작 과정 살펴보기
처음에는 행렬의 모든 값이 0입니다.
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
첫 번째 요소 [3, 5]를 처리하면 행 번호가 3 미만(0~2행), 열 번호가 5 미만(0~4열)인 셀들이 1씩 증가합니다.
1 1 1 1 1 0
1 1 1 1 1 0
1 1 1 1 1 0
0 0 0 0 0 0
0 0 0 0 0 0
두 번째 요소 [4, 6]를 처리하면 다음과 같이 됩니다.
2 2 2 2 2 1
2 2 2 2 2 1
2 2 2 2 2 1
1 1 1 1 1 1
0 0 0 0 0 0
마지막으로 세 번째 요소 [5, 3]을 처리하면 최종 상태는 다음과 같습니다.
3 3 3 2 2 1
3 3 3 2 2 1
3 3 3 2 2 1
2 2 2 1 1 1
1 1 1 0 0 0
행렬의 최댓값은 3이며, 이 값을 포함하는 셀은 정확히 9개입니다.
해결 접근 방법
핵심 아이디어는 간단합니다. 모든 연산은 왼쪽 위 영역을 기준으로 적용되므로, 모든 항목의 행 값 중 최솟값과 열 값 중 최솟값으로 만들어지는 교집합 영역이 매번 증가 연산의 대상이 됩니다. 따라서 이 영역이 곧 최댓값을 갖는 영역이며, 그 넓이를 계산하면 됩니다.
- xpos := 0, ypos := 0으로 초기화
- input_list의 각 항목에 대해 반복
- xpos가 0이면(첫 번째 항목)
- xpos := item[0]
- ypos := item[1]
- 그렇지 않으면
- xpos := min(xpos, item[0])
- ypos := min(ypos, item[1])
- xpos가 0이면(첫 번째 항목)
- (xpos * ypos)를 반환
구현 예제
아래 코드로 더 잘 이해해 볼 수 있습니다.
def solve(input_list):
xpos = 0
ypos = 0
for item in input_list:
if xpos == 0:
xpos = item[0]
ypos = item[1]
else:
xpos = min(xpos, item[0])
ypos = min(ypos, item[1])
return (xpos * ypos)
print(solve([[3, 5], [4, 6], [5, 3]]))
입력
[[3, 5], [4, 6], [5, 3]]
출력
9
마무리
이 문제는 실제로 행렬을 생성하고 각 셀을 일일이 업데이트하지 않아도 해결할 수 있습니다. 모든 좌표 쌍의 최솟값만 구하면 최댓값을 포함하는 영역의 크기를 O(n) 시간 복잡도로 바로 계산할 수 있어, 매우 효율적인 풀이가 가능합니다.