백준 31825 - 알파벳과 쿼리 (Easy)

https://boj.kr/31825

풀이

문자열 S와 쿼리 개수 Q가 주어진다.

두가지 유형의 쿼리가 존재한다.

1. 연속된 다른 문자 개수 세기 (t = 1)
   1. 구간 [l, r]에서 연속하는 문자 그룹을 찾아 개수를 출력.
2. 알파벳 증가 (t = 2)
   1. 구간 [l, r]에서 문자들을 다음 알파벳으로 변경 (Z → A)

if t == 1:
    count = 0
    for i in range(l, r):
        if S[i] != S[i + 1]:  # 인접한 문자가 다르면 count 증가
            count += 1
    print(count + 1)

인접한 문자들을 비교하면서 바뀌는 부분이 있는지 체크.

구간 [l, r]에서 연속된 블룩 개수 = count + 1로 출력

if t == 2:
    for i in range(l, r + 1):
        id = ord(S[i]) - ord('A')  # 현재 문자 인덱스 (0 ~ 25)
        id = (id + 1) % 26  # 다음 알파벳 (Z -> A 포함)
        S[i] = chr(id + ord('A'))

ord()를 이용해 알파벳을 숫자로 변경하여 0 ~ 25 범위로 다룬다.

(id + 1) % 26 을 사용하여 Z를 A로 순환되도록 처리한다.

시간 복잡도 분석

1. 쿼리 1번 (t = 1)
   1. 최대 O(N), 최악의 경우 모든 문자를 비교한다.
2. 쿼리 2번 (t = 2)
   1. 최대 O(N), 모든 문자를 변경할 가능성이 있다.

즉, 최대 시간 복잡도는 최악의 경우 O(Q * N) 이니,, 최적화가 필요할 수 도 있다.

코드

# 백준 31825 - 알파벳과 쿼리 (Easy)
# 분류 : 문자열

N, Q = map(int, input().split())
S = list(input())

for _ in range(Q) :
    t, l, r = map(int, input().split())
    l -= 1
    r -= 1

    if t == 1 :
        count = 0
        for i in range(l, r) :
            if S[i] != S[i + 1] :
                count += 1
        
        print(count + 1)
    
    if t == 2 :
        for i in range(l, r + 1) :
            id = ord(S[i]) - ord('A')
            id = (id + 1) % 26
            S[i] = chr(id + ord('A'))