[Google Kick Start] 2021 구글 킥스타트 Round B Increasing Substring 풀이

 

 

문제

---

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435a5b/000000000077a882

Kick Start - Google’s Coding Competitions

 

 

나의 풀이

---

DP를 사용하여 푸는 간단한 문제이다. 문자열의 길이 n만큼의 dp 배열을 만들어서 모두 1로 초기화 한다. 이 배열은 해당 인덱스까지의 가장 긴 increasing substring 길이이다. 인덱스 1부터 n-1까지를 탐색하면서 검사하면 되는데 이 때, dp[i]는 s[i]와 sp[i-1]을 비교해 s[i]가 더 큰 알파벳이면 dp[i]=dp[i-1]+1을 해주고 아닌 경우 그냥 넘어간다.

예시에서 주어진대로 s = "ABACDA"라면 처음 dp=[1, 1, 1, 1, 1, 1]이다. 그 뒤 인덱스 1번을 검사하면 B는 A보다 크니까 dp[1] = dp[0]+1이 된다. 이 과정을 끝까지 반복하면 dp = [1, 2, 1, 2, 3, 1]을 얻을 수 있다.

 

코드

---

# https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435a5b/000000000077a882

T = int(input())

for t in range(T):
    n = int(input())
    s = input()
    dp = [1] * n
    for i in range(1, n):
        if ord(s[i]) > ord(s[i-1]):
            dp[i] = dp[i-1] + 1
    dp_str = list(map(str, dp))
    print(f"Case #{t+1}: " + " ".join(dp_str))