[Python] 16588번 Substring Permutation

https://www.acmicpc.net/problem/16588

16588번: Substring Permutation

---

 

22/09/19

 

 

전형적인 문제 해석이 어려운 문제로, 실제 난이도는 그다지 어렵지는 않은 문제이다.

---

 

문제 접근 방식:

 

 

문제를 요약하면 다음과 같다.

 

문자열 S와 P를 각각 따로 준다. 이때, Π(S)는 문자열 S의 모든 순열의 집합을 나타낸 것으로, 예를 들어 S = guru라면, Π(S)는 {gruu, guru, guur, rguu, rugu, ruug, ugru, ugur, urgu, urug, uugr, uurg}가 된다.

 

우리의 목적은 S와 P가 주어져 있을 때, Π(S)의 어떤 원소 s와 Π(P)의 어떤 원소 p에 대해서 p가 s의 부분 문자열이 된다면, YES를, 아니면 NO를 출력하는 것이다.

 

간단히 문제를 요약해서 이해가 잘 안될 수도 있다.

 

하지만, 이 문제를 쉽게 풀어보자면, 다음과 같이 해석할 수 있다.

 

우리는 문자열 S의 모든 순열의 집합에서 원소 하나(s)를 뽑는다. 마찬가지로 문자열 P의 모든 순열의 집합에서 원소 하나(p)를 뽑는다.

 

만약 NO가 출력이 되려면은 모든 원소 s와 모든 원소 p에 대해서 부분 문자열이 만들어지지 않는다는 뜻이다.

 

그 말은 곧 p와 s를 비교했을 때 항상 다른 문자가 있다는 말과 같은 말이다. 혹은, 같은 문자가 있어도 p가 가지고 있는 문자가 s가 가지고 있는 문자보다 항상 많아서 부분 문자열이 될 수 없다는 말과 같은 말이다.

 

때문에, 문자열 S를 입력받고, 어떤 문자가 어떤 빈도로 나오는지를 알아내기 위해 collection 모듈의 Counter함수를 사용하여 문제를 구현했다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 16588번 Substring Permutation
# 문자열
from collections import Counter
A_string = input()
A = Counter(list(A_string))
B = sorted(Counter(list(input())).items())
flag = True
for alphabet, frequency in B:
    if alphabet not in A_string:
        flag = False
        break
    if A[alphabet] < frequency:
        flag = False
        break
if flag:
    print('YES')
else:
    print('NO')