[백준] 5015번 ls _ Python

2024. 3. 14. 23:13·Algorithms/DP
목차
  1. 1. Preview
  2. 2. 초기 접근 방법
  3. 3. 생각
  4. 4. 코드

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
  1. 1. Preview
  2. 2. 초기 접근 방법
  3. 3. 생각
  4. 4. 코드
'Algorithms/DP' 카테고리의 다른 글
  • [백준] 7579번 앱 _ Python
  • [백준] 14925번 목장 건설하기 _ Python
  • [백준] 2228번 구간 나누기 _ Python
  • [백준] 17626번 Four Squares _ Python
wch_t
wch_t
  • wch_t
    끄적끄적(TIL)
    wch_t
  • 글쓰기 관리
  • 전체
    오늘
    어제
    • 분류 전체보기 (169)
      • Architecture (0)
      • Algorithm (67)
        • Math (5)
        • Simulation (1)
        • Data Structure (4)
        • DP (7)
        • Brute Fource (10)
        • Binary Search (6)
        • Greedy (2)
        • Graph (11)
        • Mst (1)
        • Shortest path (10)
        • Two Pointer (1)
        • Tsp (3)
        • Union Find (2)
        • Mitm (1)
      • CS (2)
        • 데이터베이스 (5)
        • 네트워크 (5)
      • DB (7)
      • DevOps (15)
        • AWS (9)
        • Docker (1)
        • CI-CD (5)
      • Error (1)
      • Project (0)
        • kotrip (0)
      • Spring (59)
        • 끄적끄적 (5)
        • 기본 (9)
        • MVC 1 (7)
        • MVC 2 (11)
        • ORM (8)
        • JPA 1 (7)
        • JPA 2 (5)
        • Spring Data Jpa (7)
      • Test (2)
      • TIL (5)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    aws secrets manager
    spring-cloud-starter-bootstrap
    애플
    백준 17299 파이썬
    response_mode
    Merge
    TempTable
    Jenkins
    백준 17289 파이썬
    apache poi
    form_post
    scope
    view algorithm
    Sxssf
    docker: not found
    docker
    spring-cloud-starter-aws-secrets-manager-config
    백준 3015 파이썬
  • 최근 댓글

  • hELLO· Designed By정상우.v4.10.3
wch_t
[백준] 5015번 ls _ Python
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.