[백준 알고리즘] 1120번 : 문자열 (Java) 문제 풀이

2 초

128 MB

16780

9306

8101

56.841%

문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

https://www.acmicpc.net/problem/1120

 

1120번: 문자열

문제에 대한 이해

어떠한 임의 문자를 추가하여 A와 B의 문자열 내에서 문자 차이가 최소로하는 것을 목표로 하는 프로그램을 코딩하는 것이다.

 

어떻게 풀 것인가?

결국에는 B와 A라는 두 문자열의 최소차이를 구하는 문제이다.

즉, 앞이나 뒤에 채워넣는 알파벳은 b와 일치하게 채워넣으면 그만이기 때문이기에, 신경 써야 할부분은 오로지 현재 A와 B의 차이점이다. A 문자열과 같은 길이의 B의 부분 문자열을 반복적으로 비교하며 최소 차이를 찾으면 된다.(브루트 포스)

시간복잡도

시간 복잡도는 O(N^2) 이다.

공간복잡도

공간 복잡도는 문자열에 대한 O(1) 이다.

풀면서 놓쳤던점

처음에는 문자를 하나하나씩 전부를 비교하여, 차이를 채워 나갔던 것 같다.

이 문제를 통해 얻어갈 것

문제를 읽고 핵심을 짚는 것을 포인트로 잡아야 할 것 같다.

내 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

// 백준알고리즘 1120번 문자열

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String A = st.nextToken();
        String B = st.nextToken();

        int result = A.length();

        for (int i = 0; i < B.length() - A.length() + 1; i++) {
            int tmp = 0;
            for (int j = 0; j < A.length(); j++) {
                if (A.charAt(j) != B.charAt(j + i)) {
                    tmp++;
                }
            }
            if (result > tmp) {
                result = tmp;
            }
        }
        System.out.println(result);
    }
}