[자바] 백준 9241 - 바이러스 복제 (java)

목차

문제 : boj9241

 

 

필요 알고리즘

• 그리디 알고리즘
  
  • 그리디 풀이는 바로 보일 것 같다!

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

 

 

풀이

  개인적으로 약간 선 넘는 문제였다. 일단 입력받은 문자열이 A, B 라고 한다면 A와 B 각각 앞부터와 뒤부터 동일한 부분이 어디까지인지 파악한다. 선 넘는다고 생각한 부분은, 당연히 하나 이상의 DNA는 바꿔야 된다고 생각했다. 예를들어

입력이 AAA와 AA일 경우 'AA' 를 제거 후 'A'를 추가해 AA가 되는 형태로 생각했는데, 그냥 추가 안하고 지우기만 해도 된다! 이 부분에 대한 판단은 사실 문제만 보고 파악이 힘든 것 같다.

 

  추가하지 않고 삭제만 해도 된다는걸 깨달았다면 로직이 상당히 변경되는데, 예를들어서

AA와 AAAA 라면 2가 답이고, AAAA와 AA라면 0이 답이다. 따라서 A와 B의 길이에 따라서도 로직이 변경되어야 한다. 아무튼 로직은 다음과 같다.

 

1. A와 B를 앞부분부터 동일한 부분까지 찾는다. 이게 코드에서 s이다.

2. A와 B를 뒷부분부터 동일한 부분까지 찾는다. 코드에서 e 이다.

3. e가 A와 B 중 작은 길이에서 e를 뺀게 동일하지 않은 부분의 끝 인덱스에 해당한다. 해당 값이 s크다면 B의 길이에서 e와 s를 뺀게 답이다.

4. 그렇지 않다면 A의 길이가 더 크다면 0, 아니라면 B의 길이 - A의 길이가 답이 된다.

 

 

코드 : github

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        String a = br.readLine();
        String b = br.readLine();

        int s = 0;
        int minLen = Math.min(a.length(), b.length());
        while (s<minLen && a.charAt(s) == b.charAt(s)) {
            s++;
        }

        int e = 0;
        while (e<minLen && a.charAt(a.length()-1-e) == b.charAt(b.length()-1-e)) {
            e++;
        }

        System.out.println(s>=minLen-e?(a.length()>b.length()?0:b.length()-a.length()):b.length()-e-s);
    }
}