티스토리 뷰
728x90
반응형
문제
S의 문자들을 골라 T를 만들 수 있다.
S에서의 순서대로 이어 붙여 새 문자열을 만드는 것을 반복하여 만들 수 있는 T의 최대 개수를 구하는 문제이다.
풀이
- S에서의 순서가 유지돼야 함을 유의한다.
- S문자열에서 차례대로 문자를 살펴보며 T를 만들 수 있는 개수를 별도의 리스트에서 셀 수 있다.
- 예를 들어 S가 adabccb 이고 T가 abc일 때, 다음과 같이 셀 수 있다.
- T에 해당하는 알파벳이 순서대로 개수가 확보되어 있는지 확인할 수 있는 리스트를 생성한다.
- S의 1번째 a 문자는 T에 포함되며 이전 문자의 개수가 무한으로 현재 문자(a) 개수보다 많기 때문에 현재 문자에 1을 더한다.
- 2번째 문자인 d는 T에 포함되지 않으므로 넘어간다.
- 3번째 문자인 a는 첫번째와 마찬가지이기 때문에 a에 1을 더한다.
- 4번째 문자인 b는 T에 포함되며, a(2) 보다 값이 작기에 1을 더할 수 있다.
- 마찬가지로 5번째 c도 조건을 만족함으로 증가시킬 수 있다.
- 하지만 6번째 c는 앞의 b(1) 보다 클 수 없기에 1을 더할 수 없다.
- 7번째 b는 T에 존재하며 앞의 a(2)보다 크기에 1을 더할 수 있다.
- 순차적으로 c까지 만들 수 있어야 하기 때문에 최종적으로 생성할 수 있는 T(abc)는 1개이다.
Python 코드
S = input()
t = input()
dp = [0]*(len(t)+1)
dp[0] = float("inf")
# T에 존재하는지 확인하고, 이전 단어의 위치를 빠르게 찾기 위해 사용
find_idx = {a:idx+1 for idx,a in enumerate(t)}
for s in S:
# (조건) T에 존재하는지, 이전 단어의 수가 더 큰지
if s in find_idx and dp[find_idx[s]-1] > dp[find_idx[s]]:
dp[find_idx[s]] += 1
print(dp[-1])
문제출처
728x90
반응형
'Study > Coding Test' 카테고리의 다른 글
[백준 BOJ / Python] 17070번 파이프 옮기기 1 (0) | 2023.03.08 |
---|---|
[백준 BOJ / Python] 2293번 동전 1 (0) | 2023.03.07 |
[백준 BOJ / Python] 1080번 행렬 (0) | 2023.03.02 |
[백준 BOJ / Python] 2583번 영역 구하기 (0) | 2023.03.01 |
[백준 BOJ / Python] 14503번 로봇 청소기 (0) | 2023.02.27 |
댓글