[백준] 5015번 ls _ Python

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

5015번: ls

 

 

---

 

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)