[자바] 백준 24839 - Speed Typing (java)

문제 : boj24839

---

 

필요 알고리즘 개념

• 문자열 파싱
  • String을 character 단위로 볼 줄 알아야 한다.
• 그리디 알고리즘 (greedy)
  • I의 모든 문자가 순서대로 P에 존재해야 하는지를 매번 '그리디하게' 확인한다.
• 두 포인터 (two pointer)
  • I와 P의 시작점에 가상의 포인터를 하나씩 두고 양측이 점점 움직이면서 답을 찾아나가야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  I는 읽기 힘드므로, 이후 I는 from, P는 to 라고 하겠다(코드에서도 동일한 이유로 I를 사용하지 않았다.). from의 모든 character(이하 문자)가 순서대로 to에 존재하면 가능하고, 그렇지 않다면 IMPOSSIBLE이다.

 

  이 때, 출력해야 하는 y값은 단순히 'to의 길이 - from의 길이'가 된다. 예를들어 이하의 예시를 생각해보자.

1
ABCD
ADBCAD

위의 예시를 그림으로 그려보면 다음과 같다. 이처럼 from의 모든 문자가 순서대로 to에 존재한다면 가능한 경우이고, 회색으로 되어있는 'D'와 'A'가 제외될 것이다. 따라서 당연하게 to의 길이 - from의 길이 = 2가 답이 된다.

 

  그럼 from에 존재하는 모든 문자가 순서대로 to에 존재하는지 살펴보는 방법에 대해 알아보자.

 

 

 

 

1. from과 to의 맨 앞에 가상의 포인터(실제론 int형으로 인덱스 번호만 나타내주면 된다.)를 하나씩 둔다. 각각 a와 b라 하겠다.

 

2. a는 그대로 둔 채로, b를 움직여서 a가 현재 가르키고 있는 값('A')과 동일한 값을 찾는다. b가 현재 보고 있는 값이 해당 값이므로 마킹하고 a와 b를 전진시켜준다.

  

3. 이제 a는 'B'가 된다. b를 전진시키면서 'B'를 찾아주자. 우선 'D'는 아니므로 b를 전진시킨다.

 

4. 이제 b가 가르키는곳이 a가 가르키는 값과 동일하므로 다시 a와 b를 전진시킨다.

 

5. 이제 a는 'C'가 되고 바로 찾았다! 그러므로 마찬가지로 a와 b를 전진시킨다.

 

6. 이제 a는 'D'이다. b가 가르키는 값은 'A'이므로 b를 전진시킨다.

 

7. 그럼 a와 b가 가르키는 값이 동일하므로 다 찾았다.

 

  이 과정을 거치면서 매번 a와 동일한 값을 찾을 때 까지 b만 전진시키면서 찾게된다. 그러다가 a가 모든 문자를 보기 전에 b가 to의 길이를 넘어버리면 from의 모든 문자를 to에서 순서대로 찾을 수 없는 것이므로 IMPOSSIBLE을 출력해주면 된다.

 

  위의 과정은 사실 별다른 알고리즘 개념이 없더라도 생각해낼 수 있다. 하지만 굳이 분류를 한다면 그리디 알고리즘 + 투 포인터 알고리즘이라고 볼 수 있다. 매번 동일한 전략을 취해 진행했으므로(a를 한칸씩 전진하면서, b가 a와 동일한 값일때까지 b만 전진. 못찾는다면 그대로 IMPOSSIBLE) 그리디이고, a와 b라는 가상의 두개의 포인터를 사용했으므로 투 포인터 이다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= tc; t++) {
            String from = br.readLine();
            String to = br.readLine();
            int pt = 0;
            boolean chk = false;
            for (int i = 0; i < from.length(); i++) {
                chk = false;
                while (pt < to.length()) {
                    if (to.charAt(pt++) == from.charAt(i)) {
                        chk = true;
                        break;
                    }
                }
                if (!chk) break;
            }
            sb.append(String.format("Case #%d: ", t)).append(!chk?"IMPOSSIBLE":to.length()-from.length()).append('\n');
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}