[CH08] WILDCARD

[wbluke]

https://algospot.com/judge/problem/read/WILDCARD

APSS_p218

[wbluke]

[Idea Point]

• 종료하는 case

  1. S[pos]와 W[pos]가 대응되지 않는다 : 대응 실패
  2. W 끝에 도달했다 : 패턴에 *이 하나도 없는 경우. W와 S의 길이가 같아야만 대응된다.
  3. S 끝에 도달했다 : 패턴은 남았지만 문자열이 이미 끝난 경우. 남은 패턴이 전부 *로 구성되어 있다면 대응. 나머지는 false.
  4. W[pos]가 인 경우 : 가 몇 글자에 대응될지 모르기 때문에, 0글자부터 남은 문자열의 길이까지를 순회하며 모든 가능성을 검사한다.

• cache를 -1로 초기화하고, bool타입이 true이면 1, false이면 0으로 표현됨을 이용해 memoization을 구현한다.

[wbluke]

[Idea Point]

• 3번 case는 4번 case를 재귀호출하면서 자연스럽게 해결된다.
• 4번 case의 경우, W의 pos+1 이후 기준으로 S의 pos+skip 이후를 재귀 호출했을 때, 답이 하나라도 참이면 답은 true.

[wbluke]

[Idea Point]

• cache배열을 101*101로 설정해야 한다. 문자열의 길이가 100일 때 설정할 수 있는 접미사는 101개이기 때문.
• memoization의 base case를 어디에 설정해야하는지 잘 체크할 것.

[New Things]

• sort(start, end) : [start, end) 범위의 요소를 오름차순 정렬해준다. algorithm헤더파일에 있다. 세번째 인자로 정렬방식이나 사용자 정의함수를 추가해서 정렬시킬 수도 있다.

[정답!]