[자바] 백준 14254 - 비밀번호 변경 (java)

목차

문제 : boj14254

 

 

필요 알고리즘

• 애드 혹 (ad hoc)
  
  • 특정한 알고리즘 없이 이 문제를 위한 로직을 찾는 애드혹 문제이다.

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

 

 

풀이

* 애드혹 문제의 경우 별다른 알고리즘이 필요한 문제가 아니라서, 풀이의 아이디어를 보게되면 그냥 다 푼거나 다름없다. 따라서 정말 열심히 생각해봤는데도 진짜 모르겠고, 그냥 넘어가긴 싫고 너무 억울해서 풀이를 꼭 보고싶다면 풀이를 보자.

 

 

 

 

 

  예제 입력 4를 가지고 생각해보자.

amavckdkz
7

 

  얼핏 아래처럼 한 자리씩 매칭시킨 후 다른게 있다면 바꾸면 될 것 같이 생겼다!

 

  근데 한번 그려보고 해보면 알겠지만, 예를들어 2번째인 m과 v가 서로 다르다고 변경하게 되면 다른 문자에도 영향을 끼쳐버리게 된다. 그렇다면 뒤에 영향을 끼친 부분이 원래는 동일했는데, 이전값을 바꿔버리면서 다른 문자가 되버릴수도 있다. 따라서 영향도 파악을 해서 어떤 문자로 바꾸는게 가장 효율적일지 파악해야 한다.

 

 

    이 때 문자 변경으로 인한 영향이 어디까지 전파되는지를 생각해보자. 위 문자열의 a를 변경할 경우 아래와 같이 '전체 문자열의 길이 - k = 2' 개씩 건너띄며 영향을 끼치게 된다. (첫번째 문자를 바꿀 시 그와 매칭되는 아래쪽의 3번째 문자가 바뀌고, 3번째 문자가 바뀌면 그와 매칭되는 5번째 문자가 바뀌고...)

 

  그렇다면 위에서 말한대로 '전체 문자열의 길이 - k' 씩 건너띄면서 그 중 가장 많이 나온 문자로 전부 바꿔버리는 식으로 하면 영향도를 파악해 가장 효율적인 방식으로 바꾼게 된다. 이걸 영향도 파악이 되지 않은 문자갯수만큼 진행하면 된다. 영향도 파악이 되지 않은 문자갯수또한 '전체 문자열의 길이 - k'개 이다. 예제 입력 4의 경우 9개 문자 중 k가 7이므로, 앞에서 2개의 문자까지만 2개씩 건너띄며 진행하면 된다.

 

 

코드 : github

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

import static java.lang.Math.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

    private void solution() throws Exception {
        char[] str = br.readLine().toCharArray();
        int k = Integer.parseInt(br.readLine());

        int answer = 0;
        int gap = str.length-k;

        for (int i = 0; i < gap; i++) {
            int sum = 0;
            int max = 0;
            int[] cnt = new int['z'-'a'+1];

            for (int j = i; j < str.length; j+=gap) {
                sum++;
                max = max(max, ++cnt[str[j]-'a']);
            }

            answer += sum-max;
        }

        System.out.println(answer);
    }
}