문제 링크
문제 요약
‘벽력일섬’이라는 독특한 규칙에 따라 주어진 수열의 원소들을 베어내는 문제입니다.
벽력일섬은 현재 원소를 베고 다음 원소로 이동하는데, 다음 원소가 현재 원소보다 크거나 같으면 기존의 벽력일섬을 이어서 사용합니다. 그렇지 않으면 현재 벽력일섬을 종료하고 새로운 벽력일섬을 시작합니다.
수열의 마지막 원소를 베면 벽력일섬은 자동으로 종료됩니다. 이 규칙에 따라 사용된 총 벽력일섬의 횟수와 한 번의 벽력일섬으로 베어낸 원소의 최대 개수를 구해야 합니다.
풀이
이 문제는 주어진 규칙에 따라 수열을 순회하며 두 가지 값을 추적하는 Simulation 문제입니다. 구해야 할 값은 총 벽력일섬 사용 횟수(cnt)와 한 번의 벽력일섬으로 베어낸 원소의 최대 개수(mx)입니다.
문제의 규칙에 따르면, 수열의 첫 번째 원소는 항상 새로운 벽력일섬의 시작이 됩니다.
따라서 cnt는 최소 1이 될 것이고, 현재 벽력일섬의 길이를 나타내는 current 변수도 1로 초기화하여 시작할 수 있습니다.
수열의 두 번째 원소부터 마지막 원소까지 순회하면서 이전 원소(l[i-1])와 현재 원소(l[i])를 비교합니다.
l[i] >= l[i-1]인 경우: 현재 벽력일섬이 이어지는 경우입니다.current변수를 1 증가시켜 현재 벽력일섬의 길이를 늘려줍니다.l[i] < l[i-1]인 경우: 현재 벽력일섬이 종료되고 새로운 벽력일섬이 시작되는 경우입니다.- 먼저, 방금 종료된 벽력일섬의 길이
current를mx와 비교하여 최댓값을 갱신합니다. - 총 벽력일섬 횟수
cnt를 1 증가시킵니다. - 새로운 벽력일섬이 시작되므로
current를 1로 초기화합니다.
- 먼저, 방금 종료된 벽력일섬의 길이
모든 원소를 순회한 후에는 마지막 벽력일섬이 아직 mx와 cnt에 반영되지 않은 상태일 수 있습니다. 이는 마지막 벽력일섬이 수열의 끝에 도달하여 자연스럽게 종료되기 때문입니다. 따라서 반복문이 끝난 뒤에 mx를 current로 한 번 더 갱신하고, cnt를 1 증가시켜 마지막 벽력일섬까지 최종 결과에 포함시켜야 합니다.
이러한 방식으로 수열을 한 번만 순회하므로, 시간 복잡도는 O(N)이 됩니다.
정답 코드
def solve():
n = int(input())
l = [*map(int, input().split())]
mx = 0 # 한 번의 벽력일섬으로 베어낸 원소 개수의 최댓값
cnt = 0 # 벽력일섬을 사용한 총 횟수
current = 1 # 현재 진행 중인 벽력일섬으로 베어낸 원소의 개수. 첫 원소는 항상 새로운 벽력일섬의 시작이므로 1로 초기화.
for i in range(1, n): # 두 번째 원소부터 마지막 원소까지 순회
if l[i] >= l[i-1]: # 다음 원소가 현재 원소보다 크거나 같으면 벽력일섬을 이어서 사용
current += 1
else: # 다음 원소가 현재 원소보다 작으면 벽력일섬을 종료하고 새로운 벽력일섬 시작
mx = max(mx, current) # 현재까지의 벽력일섬 길이 중 최댓값 갱신
cnt += 1 # 벽력일섬 횟수 증가
current = 1 # 새로운 벽력일섬 시작, 길이 1로 초기화
# 반복문 종료 후, 마지막 벽력일섬에 대한 처리
# 마지막 벽력일섬은 루프 내에서 종료 조건을 만나지 않았으므로 별도 처리 필요
mx = max(mx, current) # 마지막 벽력일섬의 길이로 최댓값 갱신
cnt += 1 # 마지막 벽력일섬 횟수 추가
print(cnt, mx)
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()