BAEKJOON Online Judge(BOJ) 문제입니다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
문제
https://www.acmicpc.net/problem/14727
14727번: 퍼즐 자르기
히스토그램을 구성하는 직사각형의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 이어 N개의 줄에 걸쳐 각 직사각형의 높이인 정수 Hi(1 ≤ Hi ≤ 1,000,000)가 주어진다.
www.acmicpc.net
내가 작성한 코드
import sys
from collections import defaultdict
read = sys.stdin.readline
def find(group, i):
if group[i] == -1:
return -1
elif group[i] == i:
return i
group[i] = find(group, group[i])
return group[i]
def union(group, x, y):
group_x = find(group,x)
group_y = find(group,y)
if group_x < group_y:
group[y] = group_x
else:
group[x] = group_y
N = int(read().rstrip())
nums = []
for _ in range(N):
nums.append(int(read().rstrip()))
group = [-1 for i in range(N)]
all = defaultdict(list)
mx = 0
for i, num in sorted(enumerate(nums), reverse=True, key=lambda x: x[1]):
group[i] = i
all[i] = [num, 1]
if i + 1 < N and find(group, i + 1) != -1:
union(group, i, i+1)
all[i][0] = min(all[i][0], all[i+1][0])
all[i][1] += all[i+1][1]
if i - 1 >= 0 and find(group, i - 1) != -1:
grp_left = find(group,i-1)
union(group, i-1, i)
all[grp_left][0] = min(all[i][0], all[grp_left][0])
all[grp_left][1] += all[i][1]
grp = find(group, i)
mx = max(mx, all[grp][0] * all[grp][1])
print(mx)
- 최대값부터 순차 탐색
- 정렬 전 인덱스도 함께 저장
- 인덱스로 인접한 직사각형 확인
- 유니온파인드 사용
다른 사람이 작성한 코드
None
기억해야할 것
- 시간초과를 많이 함
- 매 loop마다 min * len을 계산해서 max를 계산하니 시간초과
- min과 len을 저장하는 방식으로 변경
'코딩테스트' 카테고리의 다른 글
[프로그래머스][KAKAO_BLIND][2018] 뉴스 클러스터링 (0) | 2021.09.01 |
---|---|
[프로그래머스][KAKAO_BLIND][2018] 추석 트래픽 (0) | 2021.09.01 |
[백준][그리디] 휴먼 파이프라인 (0) | 2021.08.30 |
[프로그래머스][KAKAO_BLIND][2020] 기둥과 보 설치 (0) | 2021.08.30 |
[프로그래머스][KAKAO_BLIND][2019] 후보키 (0) | 2021.08.30 |