BoJ 19829 - The Pleasant Walk [with Python / 문제 한국어로 번역]

ssook·2023년 10월 6일
0

BoJ 문제기록

목록 보기
23/29
post-thumbnail

📍 문제

안야가 살고 있는 도로에는 nn개의 집이 있으며, 각 집들은 kk가지 가능한 색 중 하나로 칠해져 있습니다.

안야는 이 도로를 걸어다니는 것을 좋아하지만, 연속된 두 집이 동일한 색상이면 싫어합니다.
따라서 연속된 두 집이 동일한 색상을 가지지 않는 가장 긴 도로 부분(세그먼트)을 선택하고자 합니다.

안야의 선택을 여러분이 도와주세요!

입력

첫 번째 줄에는 두 개의 정수 nnkk가 주어집니다. 여기서 nn은 집의 수이고, kk는 가능한 색상의 수입니다. (1n100,0001 \le n \le 100,000, 1k100,0001 \le k \le 100,000).

다음 줄에는 nn개의 정수 a1,a2,,ana_1, a_2, \ldots, a_n이 주어집니다.
이는 도로에 있는 집들의 색상입니다 (1aik1 \le a_i \le k).

출력

한 개의 정수를 출력해야 합니다.
이 정수는 도로 부분들(세그먼트) 중에서 연속된 두 집이 동일한 색상을 가지지 않는 최대 집의 수입니다.


📍 아이디어

투 포인터로 풀 수 있는 문제이지만, 그냥 그리디로 푼 문제.

현재 인덱스에 해당하는 집의 색깔과 이전의 인덱스에 해당하는 집의 색깔이 다르면 도로 길이를 카운팅해준다.
같을 경우 기존에 카운팅한 값과 지금까지 카운팅한 값 중 더 큰 값을 정답 변수에 저장하고, 루프를 빠져나온 후 정답 변수를 출력해주면 된다.


📍 제출 코드


import sys

n, k = map(int, sys.stdin.readline().rstrip().split())
road = list(map(int, sys.stdin.readline().rstrip().split()))

max_length = 1 
current_length = 1 

for i in range(1, n):
    if road[i] != road[i - 1]:
        current_length += 1
    else:
        max_length = max(max_length, current_length)
        current_length = 1

max_length = max(max_length, current_length)

print(max_length)

profile
개발자에서, IT Business 담당자로. BrSE 업무를 수행하고 있습니다.

0개의 댓글