안녕하세요. Message입니다.
오늘은 알고스팟의 WILDCARD(와일드카드) 문제를 Java로 풀이하는 포스팅입니다.
문제링크 : https://algospot.com/judge/problem/read/WILDCARD
1. 문제파악
이번 문제에서의 어려운 점은 교재에도 나와 있듯이 "＊" 문자를 어떻게 해결하느냐 입니다.
일반 문자와 "?" 문자는 1:1 매칭으로 해결되기 때문에 어려운점은 없습니다.
하지만 "＊" 문자가 나올 경우 크게 두가지 정도를 생각해야 합니다.
① "*" 문자가 파일명의 몇번째 인덱스까지 대응되는지 계산하는 로직
② "*******a" : "ab" 케이스처럼 많은 중복 계산이 발생하는 경우
1번은 어느정도 고민이 필요한 부분 같습니다만, 2번의 경우에는 동적계획법을 이용하면 될 것같습니다.
2. 일반문자, "?" 문자 매칭
일반문자와 "?" 문자는 1:1로 매칭해서 인덱스만 올려주면 되기 때문에 크게 어려울 건 없습니다.
하지만 이것을 반복문으로 구현할지, 재귀형태로 구현할지 선택지가 나뉘게 됩니다.
반복문으로 구현하고자 한다면, 아래와 같이 while문의 조건만 잘 성정해주면 문제 없습니다.
이후에 왜 반복문을 탈출했는지(문자 불일치, 길이초과, '*' 문자를 만난 경우 등) 확인해주면 됩니다.
|
1
2
3
4
5 |
while(wIdx < wc.length && fnIdx < fn.length
&& (wc[wIdx] == '?' || wc[wIdx] == fn[fnIdx]) ){
++wIdx;
++fnIdx;
} |
cs |
재귀로 구현하고자 할 경우에는 다음 호출되는 함수에 증가된 인덱스를 넣어주면 간단하게 처리할 수 있습니다.
교재에서는 반복문보다 재귀로 구현할 경우 시간 복잡도 측면에서 유리하다고 나와 있네요.
(잘 이해는 안가지만요..)
|
1
2
3 |
if(wIdx < wc.length && fnIdx < fn.length)
if(wc[wIdx] == '?' || wc[wIdx] == fn[fnIdx])
return cache[wIdx][fnIdx] = match(wIdx+1, fnIdx+1); |
cs |
Tip. for문에서 전위/후위 증감연산자
for문에서 전위/후위 증감연산자는 동일한 기능을 수행합니다.
하지만 내부적인 동작원리가 다르기 때문에 전위 증감연산자를 사용하는 것이 좋습니다.
- 전위 증감 연산자 : ① i=i+1 ② return i
- 후위 증감 연산자 : ① const int temp=i ② i=i+1 ③ return temp
차이점을 살펴보면, 후위 증감 연산자의 경우 임시 변수인 temp를 만들어서 리턴합니다.
따라서 후위 증감 연산자를 사용할 경우 반복문 크기가 커질수록 비효율적입니다.
3. "*" 문자 처리
"*" 문자를 처리하는 방법도 반복문과 재귀 두가지로 구현할 수 있습니다.
반복문으로 구현할 경우 와일드카드의 인덱스는 1을 높여주어서 "*" 다음의 문자를 입력합니다.
그리고 일반 문자는 파일명의 길이를 넘지 않을 때 까지(fIdx+i<=fn.length) 1씩 증가시켜서 비교합니다.
|
1
2
3
4
5
6 |
if(wc[wIdx] == '*'){
for(int i=0; fIdx+i<=fn.length; ++i){
if(match(wIdx+1, fIdx+i))
return true;
}
} |
cs |
재귀로 구현하는 케이스는 for문을 재귀함수로 고치는 과정에서 if문 안에 함수가 2개가 들어갑니다.
|
1
2
3
4
5 |
if (wc[wIdx] == '*') {
if (match(wIdx + 1, fnIdx) == 1 ||
(fnIdx < fn.length && match(wIdx, fnIdx + 1) == 1))
return cache[wIdx][fnIdx] = 1;
} |
cs |
즉, 2가지 중에 한가지만 만족해도 캐쉬에 값을 저장하고 1값을 리턴합니다.
① match(wIdx + 1, fnIdx) == 1 : 와일드 카드의 "*" 다음 문자가 파일명과 일치하는 경우 ex) r*ed vs red
② match(wIdx, fnIdx + 1) == 1 : 와일드 카드는 변동 없고, 파일명의 인덱스만 증가 ex) r*ed vs rrrrrrrrrrrrrrred
저는 반복문을 재귀로 수정하면서 2번이 왜 필요한지 약간 헷갈렸습니다만,
만약 1번만 존재한다면 다음 호출되는 재귀함수에서 "*" 다음 문자와 파일명 문자가 불일치 할 경우 바로 종료되버립니다.
따라서 와일드카드의 인덱스를 유지하면서 파일명의 인덱스만 높여주는 부분도 필요합니다.
즉, 1번이 충족한다면 다시 위에서 구현한 1:1 매칭 로직으로 갈 것이고,
2번의 경우에는 와일드카드의 인덱스를 증가시키지 않았으니 다시 if (wc[wIdx] == '*') 구문을 만나면서
결과적으로 파일명의 인덱스만 증가한 효과를 볼 수 있습니다.
3. 동적계획법 적용
위의 코드에서도 재귀 호출 부분에 적용되어 있지만,
동적계획법인 메모이제이션을 적용하여 구현한 코드는 아래와 같습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91 |
package Algospot;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class Main {
char[] wc; // 와일드카드 문자열
char[] fn; // 파일이름 문자열
ArrayList<String> fileNameArray;
/* 동적프로그래밍 저장 배열
* -1 : 계산되지 않음
* 1 : 일치
* 0 : 불일치 */
int[][] cache;
Main(String wildCard, ArrayList<String> fileNameArray){
this.wc = wildCard.toCharArray();
this.fileNameArray = fileNameArray;
this.cache = new int[101][101];
}
public int match(int wIdx, int fnIdx){
// 동적 프로그래밍
if(cache[wIdx][fnIdx] != -1)
return cache[wIdx][fnIdx];
// 1:1 대응, 일치하면 인덱스 증가 후 재귀호출
if(wIdx < wc.length && fnIdx < fn.length)
if(wc[wIdx] == '?' || wc[wIdx] == fn[fnIdx])
return cache[wIdx][fnIdx] = match(wIdx+1, fnIdx+1);
// 와일드카드와 파일명 모두 끝에 도달, 파일명도 끝에 도달했어야 일치
if(wIdx == wc.length)
return cache[wIdx][fnIdx] = (fnIdx == fn.length)? 1 : 0;
// * 문자를 만난 경우
if (wc[wIdx] == '*') {
if (match(wIdx + 1, fnIdx) == 1 ||
(fnIdx < fn.length && match(wIdx, fnIdx + 1) == 1))
return cache[wIdx][fnIdx] = 1;
}
return cache[wIdx][fnIdx] = 0;
}
public void solve(){
ArrayList<String> resFileName = new ArrayList<String>();
for(int i=0; i<fileNameArray.size(); i++){
// 캐쉬 초기화
for(int[] arr : this.cache)
Arrays.fill(arr, -1);
String temp = fileNameArray.get(i);
fn = temp.toCharArray();
if(match(0,0) == 1)
resFileName.add(temp);
}
// 정렬 후 출력
Collections.sort(resFileName);
for(String str : resFileName)
System.out.println(str);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int numTextCase = sc.nextInt();
for(int i =0; i<numTextCase; i++){
String wildcard = sc.next();
int numFileName = sc.nextInt();
ArrayList<String> fileNameArray = new ArrayList<String>();
for(int j=0; j<numFileName; j++)
fileNameArray.add(sc.next());
Main main = new Main(wildcard, fileNameArray);
main.solve();
}
}
} |
cs |
4. 마무리
C++과는 달라서 그런진 모르겠지만, Java에서는 int 형과 boolean 형의 캐스팅이 안되더군요
따라서 리턴하면서 [ ① cache에 값을 저장하기 ② fnIdx가 fn.length와 일치하는지 확인 ]
2가지 작업을 한줄에 구현하려면 2번과 같이 구현해야 합니다.
① return cache[wIdx][fnIdx] = (fnIdx == fn.length); ==> 캐스팅에러 발생, 함수 리턴형이 boolean일때 가능
② return cache[wIdx][fnIdx] = (fnIdx == fn.length)? 1 : 0;
그리고 교재에서는 코드를 최적화 하기 위해 아래와 같이 if문에 재귀함수 호출이 여러개 들어가는 경우가 많은데
if (match(wIdx + 1, fnIdx) == 1 || (fnIdx < fn.length && match(wIdx, fnIdx + 1) == 1))
저도 빨리 이런 효율적인 코드에 익숙해져야 겠군요...
posted By Message
Commit your way to the LORD, trust in him and he will do this. [PSALms 37:5]
redScreen.tistory.com Blog :(
':: 프로그래밍 > Algospot 풀이' 카테고리의 다른 글
| 알고스팟 JUMPGAME(외발뛰기) Java로 구현하기 (0) | 2017.10.04 |
|---|---|
| 순열(Permutation) 알고리즘 Java로 구현하기 (2) | 2017.09.30 |