백준(BOJ) 24524 아름다운 문자열(Python)

문제 내용.

 

그리디 문제.

문제에서 요구하는 조건을 만족하기 위해서는 각각의 T를 골라내기 위해서는 T의 첫 번째 문자를 찾고, 그 뒤에서 두 번째 문자를 찾고, 이 과정을 마지막 문자까지 반복해야 한다.

그러기 위해서 먼저 T에 들어있는 문자의 인덱스를 해싱으로 각각 큐에 모아준다.

그 후 T에 있는 문자의 인덱스 중 가장 먼저인 인덱스를 기록해둔다.

그리고 그다음 문자의 인덱스 중에서 기록된 인덱스보다 크면서 제일 작은 인덱스로 기록된 인덱스를 변경한다.

이때 이미 체크한 인덱스는 모두 pop해준다.

이 과정을 반복해나가고, 만약 T의 문자들 중 하나라도 더 이상 큐에 인덱스가 남아있지 않으면 반복문을 종료한다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
#input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

S=input().rstrip()
T=input().rstrip()
D={i:deque() for i in T}
for i in range(len(S)):
    if S[i] in D:
        D[S[i]].append(i)
ans=0
flag=1
while True:
    p=-1
    c=0
    for i in T:
        if len(D[i])==0:
            flag=0
            break
        k=D[i].popleft()
        while k<p and D[i]:
            k=D[i].popleft()
        if k>p:
            c+=1
        p=k
        if len(D[i])==0:
            flag=0
    if flag:
        ans+=1
    else:
        if c==len(T):
            ans+=1
        break
print(ans)

설명하는 게 아직 어렵다.