[종만북] WILDCARD - Wildcard (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

• 문제 : aoj-WILDCARD
• 풀이
• 코드 : github

문제 : aoj-WILDCARD

 

 

풀이

  우선 '*'이 연속으로 있는 경우는 처리만 어렵게 만들고 하나만 있는 경우와 동일하다. 따라서 입력받은 W에서 '*'이 연속으로 있다면 하나로 변경해줬다. 즉, "ab********c" 라면 "ab*c"로 변경해준다.

private String compressContinuousAsterisk(String w) {
    while (w.indexOf("**") != -1) {
        w = w.replace("**", "*");
    }
    return w;
}

 

  그럼 이제 연속된 '*'이 하나로 합쳐진 W와 현재 보고 있는 문자열 cur에 대해 각각 포인터를 두고 움직인다고 해보자. 이 경우 두 개의 포인터가 가르키는 문자열이 동일하거나, W에서 현재 가르키는 문자열이 '?' 라면 둘다 포인터를 움직여줘도 된다.

while (pt1 < w.length() && pt2 < cur.length() && (w.charAt(pt1) == '?' || w.charAt(pt1) == cur.charAt(pt2))) {
    pt1++;
    pt2++;
}

 

  위처럼 진행하다가 멈추는 경우는, W의 끝에 포인터가 도달했거나, W에서 '*'인 문자열을 가르키는 경우이다. 만약 W의 마지막에 '*'이 있었다면 그냥 그대로 가능한 경우이고, W의 끝에 도달했다면 cur도 포인터 끝에 도달했다면 가능한 경우이다. 혹은 현재 W의 포인터가 '*'을 가르키는게 아니라면 cur과 매칭이 안된 것이므로 불가능한 경우이다.

if (pt1 == w.length() - 1 && w.charAt(pt1) == '*') {
    chk = true;
    return;
}

if (pt1 == w.length()) {
    chk = pt2 == cur.length();
    return;
}

if (w.charAt(pt1) != '*')
    return;

 

  그럼 이제 남은 경우는 W에서 맨 끝에 있지 않은 '*'을 가르키고 있는 경우이다. 그렇다면 W에서 그 다음 문자와 매칭되는 모든 위치에서부터 다시 탐색을 진행해주면 된다.

pt1++;	// 다음 문자 보기
int pt1Tmp = pt1;	// 파라미터로 인덱스를 넘기지 않고 있으므로 현재 위치 기억
for (int i = pt2; !chk && i < cur.length(); i++) {

    if (w.charAt(pt1Tmp) == '?' || w.charAt(pt1Tmp) == cur.charAt(i)) {	// 매칭 가능하다면
        pt1 = pt1Tmp;
        pt2 = i;
        match();	// 거기서부터 다시 진행
    }
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static List<String> ans;
    int pt1, pt2;
    String w, cur;
    boolean chk;

    public static void main(String[] args) throws Exception {
        int c = Integer.parseInt(br.readLine());
        while (c-->0) new Main().solution();
    }

    private void solution() throws Exception {
        String w = br.readLine();
        w = compressContinuousAsterisk(w);
        ans = new ArrayList<>();

        int n = Integer.parseInt(br.readLine());
        while (n-->0) {
            String cur = br.readLine();
            if (isMatch(w, cur))
                ans.add(cur);
        }

        Collections.sort(ans);
        StringBuilder sb = new StringBuilder();
        for (String cur : ans) {
            sb.append(cur).append('\n');
        }
        System.out.print(sb);
    }

    private String compressContinuousAsterisk(String w) {
        while (w.indexOf("**") != -1) {
            w = w.replace("**", "*");
        }
        return w;
    }

    private boolean isMatch(String w, String cur) {
        this.w = w;
        this.cur = cur;
        chk = false;
        pt1 = pt2 = 0;

        match();

        return chk;
    }

    private void match() {

        if (chk) return;

        while (pt1 < w.length() && pt2 < cur.length() && (w.charAt(pt1) == '?' || w.charAt(pt1) == cur.charAt(pt2))) {
            pt1++;
            pt2++;
        }

        if (pt1 == w.length() - 1 && w.charAt(pt1) == '*') {
            chk = true;
            return;
        }

        if (pt1 == w.length()) {
            chk = pt2 == cur.length();
            return;
        }

        if (w.charAt(pt1) != '*')
            return;

        pt1++;
        int pt1Tmp = pt1;
        for (int i = pt2; !chk && i < cur.length(); i++) {

            if (w.charAt(pt1Tmp) == '?' || w.charAt(pt1Tmp) == cur.charAt(i)) {
                pt1 = pt1Tmp;
                pt2 = i;
                match();
            }
        }
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.