[백준] 5015번: ls

🔈 문제

현진이는 집에서 취미로 운영 체제를 만들고 있다. 오늘은 디렉토리 안의 파일 리스트를 보여주는 "ls"를 구현해야 할 차례이다. 현진이는 사용자들이 와일드카드(*)를 이용해서 패턴과 일치한 파일 이름을 보여주게 하려고 한다. 와일드 카드는 어떤 문자의 0개 또는 그 이상에 해당한다.

 

 

📝입력

첫째 줄에 패턴 P가 주어진다. P는 1글자~100글자이고, 알파벳 소문자와 '.', '*'로만 이루어져 있다. 둘째 줄에는 디렉토리의 파일 개수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개의 줄에는 디렉토리에 있는 파일의 이름이 한 줄에 하나씩 주어진다. 파일의 이름은 1글자~100글자이고, 알파벳 소문자와 '.'으로만 이루어져 있다.

 

📑출력

패턴 P와 일치하는 파일의 이름을 입력으로 주어진 순서를 따라서 한 줄에 하나씩 출력한다.

 

📚 문제 풀이

 

재미있는 다이나믹 프로그래밍 문제였다. dp[i][j]가 의미하는 것은 패턴문자[i]와 파일문자[j] 까지의 매치여부이다. 

dp[i][j] 가 -1 이면 아직 계산되지 않은 것이고, dp[i][j] = 0 이면 매칭되지 않음을 의미하고, dp[i][j] = 1 이면 매칭됨을 의미한다. 

 

패턴문자와 파일문자가 동일할 때까지 i와 j 를 하나씩 증가시킨다. 

 

if p_idx < p.len() && s_idx < s.len() && p.as_bytes()[p_idx] == s.as_bytes()[s_idx] {
        dp[p_idx][s_idx] = solve(dp, p, s, p_idx + 1, s_idx + 1);
        return dp[p_idx][s_idx];
}    

 

 

그러다 만약 패턴문자 끝까지 도달했을 때, 파일문자도 끝까지 도달했다면 dp[i][j] = 1이되고, 파일문자가 아직 끝나지 않았다면 dp[i][j] = 0이 된다. 

 

if p_idx == p.len() {
        dp[p_idx][s_idx] = if s_idx == s.len() { 1 } else { 0 };
        return dp[p_idx][s_idx];
}

 

그리고 이제 핵심인데, 만약 패턴문자가 * 라면 두가지를 시도해보아야 한다. 하나는 *가 빈 문자열이 되는 경우 다른 하나는 *가 현재 문자를 포함하는 경우다. 

 

*가 빈문자열일때, 매칭되는지 확인하려면 i의 인덱스만 하나 증가시켜서 재귀를 통해 확인할 수 있고, *가 현재 문자를 포함하는 경우는 j의 인덱스를 증가시켜 재귀를 통해 확인할 수 있다. 

 

 

if p.as_bytes()[p_idx] == b'*' {
    if solve(dp, p, s, p_idx + 1, s_idx) == 1 || (s_idx < s.len() && solve(dp, p, s, p_idx, s_idx + 1) == 1) {
        dp[p_idx][s_idx] = 1;
        return dp[p_idx][s_idx];
    }
}

 

 

시간복잡도는 $O(n^2)$ 이 된다. 

 

 

💻 코드

use std::io::{self, BufRead};
 
fn solve(dp: &mut Vec<Vec<i8>>, p: &str, s: &str, p_idx: usize, s_idx: usize) -> i8 {
    if dp[p_idx][s_idx] != -1 {
        return dp[p_idx][s_idx];
    }
 
    if p_idx < p.len() && s_idx < s.len() && p.as_bytes()[p_idx] == s.as_bytes()[s_idx] {
        dp[p_idx][s_idx] = solve(dp, p, s, p_idx + 1, s_idx + 1);
        return dp[p_idx][s_idx];
    }
 
    if p_idx == p.len() {
        dp[p_idx][s_idx] = if s_idx == s.len() { 1 } else { 0 };
        return dp[p_idx][s_idx];
    }
 
    if p.as_bytes()[p_idx] == b'*' {
        if solve(dp, p, s, p_idx + 1, s_idx) == 1 || (s_idx < s.len() && solve(dp, p, s, p_idx, s_idx + 1) == 1) {
            dp[p_idx][s_idx] = 1;
            return dp[p_idx][s_idx];
        }
    }
 
    dp[p_idx][s_idx] = 0;
    dp[p_idx][s_idx]
}
 
fn main() {
    let stdin = io::stdin();
    let mut input = stdin.lock().lines();
 
    let p = input.next().unwrap().unwrap();
    let n: usize = input.next().unwrap().unwrap().parse().unwrap();
    let m = 100;
    let mut res = Vec::new();
 
    for _ in 0..n {
        let mut dp = vec![vec![-1; m + 1]; m + 1];
        let s = input.next().unwrap().unwrap();
        if solve(&mut dp, &p, &s, 0, 0) == 1 {
            res.push(s);
        }
    }
 
    for r in res {
        println!("{}", r);
    }
}

 

 

color scipter에서 rust 포맷은 제공해주지 않아서 다른 걸 찾아봐야 겠다...ㅠ 

 

여담으로 파이썬에서는 fnmatch라는 개쩌는 라이브러리를 제공해주기도 한다,,,

 

import sys, fnmatch
input = sys.stdin.readline
 
p = input().rstrip()
n = int(input())
res = []
for _ in range(n):
    s = input().rstrip()
    if fnmatch.fnmatch(s, p):
        res.append(s)
print(*res,sep='\n')

 

 

다행이(?) dp 사용해서 직접 구현하는 것보다는 느리다. 

 

🍭 시행착오

 

 

🔗 문제링크