https://www.acmicpc.net/problem/5015
5015번: ls
첫째 줄에 패턴 P가 주어진다. P는 1글자~100글자이고, 알파벳 소문자와 '.', '*'로만 이루어져 있다. 둘째 줄에는 디렉토리의 파일 개수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개의 줄에는 디렉토리에
www.acmicpc.net
1. Preview
시간 복잡도: p * n (= 패턴 길이 * 문자열 길이)
공간 복잡도: n
유형
: DP, 문자열(✋ 유형에는 없지만 문자열로 풀었다)
2. 초기 접근 방법
"문자열" 탐색으로 풀었다.
'패턴'에 문자 중 '*'은 무엇이든 들어갈 수 있으니 무시하고, 알파벳 문자와 '.' 이 순서대로 있는지 파악했다.
1. 먼저 '*'을 기준으로 패턴을 split 한다.
2. 패턴 끝이 '*' 이거나, 문자일 경우 입력 문자열의 끝 범위와 같은 경우
입력 문자열에 대한 검사를 진행하도록 했다.
3. 입력 문자열에서 "split화 된 조각 패턴" 을 찾는다.
없다면, 유효 문자가 아니다.
string.find("찾는 문자", "탐색 시작 인덱스", "탐색 끝 인덱스")
3. 생각
패턴 끝만 생각하고 있다가, 앞에 있는 패턴 조건을 놓쳤다.
# 패턴 앞에 '*'가 아닌 일반 문자가 왔을 때
if pattern[0] != '' and pattern[0] != string[:len(pattern[0])]:
return False
아래와 같은 테스트케이스에서 main에서 어긋났지만 조건 처리를 해주지 않아
".c.c"로 인해 유효 문자로 인식해버린다.
.*.c
main.c.c
4. 코드
def check():
idx = 0
isFind = True
# 패턴 앞에 '*'가 아닌 일반 문자가 왔을 때
if pattern[0] != '' and pattern[0] != string[:len(pattern[0])]:
return False
# 패턴 끝이 '*' 이거나, 문자일 경우 string의 끝 범위와 같은 경우
elif pattern[-1] == '' or pattern[-1] == string[len(string)-len(pattern[-1]):]:
for p in pattern:
if p == '':
continue
# p 문자 찾기
idx = string.find(p, idx, len(string))
# 해당 문자가 없다면
if idx == -1:
isFind = False
break
idx += len(p) # 그 다음 인덱스부터 탐색
return isFind
# 틀리면 False
else:
return False
# 패턴
pattern = input()
pattern = pattern.split("*") # '*'을 기준으로 split
# 디렉토리 파일 갯수
N = int(input())
result = []
for _ in range(N):
string = input()
if check():
result.append(string)
for r in result:
print(r)
'Algorithm > DP' 카테고리의 다른 글
[백준] 7579번 앱 _ Python (0) | 2024.02.23 |
---|---|
[백준] 14925번 목장 건설하기 _ Python (1) | 2024.01.30 |
[백준] 2228번 구간 나누기 _ Python (0) | 2023.11.24 |
[백준] 17626번 Four Squares _ Python (0) | 2023.11.23 |
[백준] 5557번 1학년 _ Python (1) | 2023.11.21 |