[Baekjoon] 24524 [아름다운 문자열] 입맛대로 문제풀이

카테고리

• 문자열, 그리디 알고리즘

이 문제의 경우, 주어진 문자열 S에서 순서를 유지한 채로 골라 붙여서 문자열 T를 만드는 작업을 여러 번 수행할 때, 각 문자는 한 번만 쓸 수 있다고 가정한다면, T를 최대 몇 번 만들 수 있는지를 묻는 문제입니다. T의 모든 문자가 서로 다른 것이 조건임을 인지하는 것이 핵심입니다. 쉽게 말하면, 한 번의 스캔으로 현재 매칭이 어느정도 잘 되고 있는지 관리하는 방법이 필요합니다.

시간복잡도로 인해서, \(O(S)\)정도로 문제를 푸는 것이 좋습니다.

구현 방식에는 다음과 같은 로직으로 구현했습니다.

• 문자열 매핑 만들기 (이는 T의 모든 문자열이 기본적으로 중복되지 않는다는 전제조건이 있어서 가능합니다.)
• cnt 배열 : m만큼 (T의 길이)
• S를 스캔
  • 문자에 T가 없으면 continue
  • p가 0 (즉 첫번째 T의 알파벳)일 때 count를 더해줌
  • p>0이면, p-1단계까지 매칭된 것 중 중복되지 않는지 확인

크게 다음과 같은 방식으로 구현했습니다.

S = input().strip()
T = input().strip()

m = len(T)

# 알파벳 각 문자 -> T에서의 위치 인덱스 (없으면 -1)
# ord('a') : 97 반환 <-> chr(97) : a반환
pos = [-1] * 26
for i, ch in enumerate(T):
    pos[ord(ch) - 97] = i

# T의 0..i번째까지 완성한 매칭 개수
cnt = [0] * m

for s in S:
    p = pos[ord(s) - 97]
    if p == -1:
        continue
    # 첫글자일때, 새로운 매칭 가능
    if p == 0:
        cnt[0] += 1
    # p가 0이 아닐 때, p-1단계까지 매칭된 것 중 중복되지 않게
    ## p-1단계까지 완성된 매칭 수 : cnt[p-1]
    ## p단계까지 이미 승급된 횟수 : cnt[p]
    else:
        if cnt[p] < cnt[p-1]:
            cnt[p] += 1
print(cnt[m-1])

일단 생각하는데 너무 오래걸렸습니다… 정답을 맞게 풀더라도, 시간복잡도로 인해서, 대부분 시간초과가 났어서 결국에는 도움을 좀 받아서 문제를 풀었습니다… 찾아본 결과, 많은 케이스들에서 ord를 사용해서 정렬을 시켜주고, 순서대로 매칭이 되었는지를 확인하는 방법을 사용했습니다.

다음의 코드로도 정답은 도출되었지만, 문제는 시간 초과로 인해서 풀이에 실패했습니다. 아마 한 번, 다 돌아간 후, s_list(S를 리스트로 바꾼 변수)를 다시 만들어서 생성하는 과정에서 시간초과가 발생한 것 같습니다.

S = input().strip()
T = input().strip()

count = 0
s_list = list(S)
ranks = []


while True:
    used = [False] * len(s_list)
    t = 0

    for i, s in enumerate(s_list):
        if t < len(T) and s == T[t]:
            t += 1
            used[i] = True
            if t == len(T):
                break
    if t < len(T):
        break
    s_list = [s for i, s in enumerate(s_list) if not used[i]]
    count += 1

print(count)