백준 31823 - 악질 검거 (파이썬)

https://boj.kr/31823

 

풀이

각 사람의 이름과 함께 “.” 과 “*”로 이루어진 문자열이 제공된다.

각 사람의 문자열에서 연속된 “.” 의 최대값을 구하고, 이를 기반으로 중복을 제거한 다양한 값의 개수를 출력해야한다.

for i in range(N):
    S = input().split()
    name.append(S[-1])  # 이름 저장
    S = S[:-1]  # 이름을 제외한 문자열 리스트

마지막 요소는 이름이름이므로, name.append(S[-1]) 을 통해서 따로 저장한다.

S[:-1]을 통해서 나머지 부분을 따로 저장한다.

max_count = 0
count = 0
for j in range(M):
    if S[j] == ".":
        count += 1
    if S[j] == "*":
        count = 0

    max_count = max(max_count, count)
answer.append(max_count)

“.” 이 나오면 count를 증가하고,

“*”이 나오면 count를 0으로 초기화 한다.

또한, 최대값을 계속 갱신하여 max_count를 업데이트 한다.

시간 복잡도 계산

1. 입력 처리 : O(NM)
2. 중복 제거 : O(N)
3. 출력 처리 : O(N)

즉, 총 시간 복잡도는 : O(NM)

코드

# 백준 31823 - 악질 검거
# 분류 : 구현

N, M = map(int, input().split())

answer = []
name = []
for i in range(N) :
    S = input().split()
    name.append(S[-1])
    S = S[:-1]

    max_count = 0
    count = 0
    for j in range(M) :
        if S[j] == "." :
            count += 1
        if S[j] == "*" :
            count = 0
        
        max_count = max(max_count, count)
    answer.append(max_count)

print(len(set(answer)))
for i in range(N) :
    print(answer[i], name[i])