[BOJ / 백준] 백준 1120번 문제를 풀어보았다. (ft. Java)

2021년 8월 30일 월요일 - 으악 개강이다!!

오늘 올려볼 문제는 1120번 문자열 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘은 같은 건국대학교를 다니시는 누군지 모를 분이 푸신 문제를 가져왔다.

볼 때마다 대단한 사람들 많다고 느낌..

입력 예제

입력은 딱 봐도 알아볼 수 있는 입력이다.

---

풀이 및 코드

이 문제는 브루트 포스 기법을 사용해서 푸는 문제이다.

브루트 포스란 모든 경우의 수를 다 때려넣어서 정답을 구해내는 기법이다.

입력이 적고 문제를 해결하기에 마땅한 기법이 없을 때 많이 사용되는 방식이다.

백트래킹 기법과 같이 쓰이는 경우도 많다.

자 기법을 알았으니 그 기법을 어떻게 적용할지 생각해보자.

A 문자열이 항상 B 문자열보다 길이가 작으므로 A 문자열을 움직여 가장 차이가 적은 곳을 찾는다.

ex)

B: abcdef   abcdef  abcdef
A: abbb      abbb     abbb
--------------------------
차:  2         4        4

이렇게 자리만 잡아두면 A문자열 앞뒤로는 B와 같은 문자를 붙이면 되므로 2가 답이된다.

대충 감이 잡힐 것이라 믿는다..!

풀이코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력 받기
        String[] input = br.readLine().split(" ");

        // 결과값 (문자열 최대 길이가 50이므로 그것보다 큰 숫자를 저장해둠)
        int result = 55;

        // B의 길이 - A의 길이 + 1 만큼 for문을 돌면서
        for(int i = 0; i <= input[1].length() - input[0].length(); i++)
        {
            int diff = 0;

            for(int j = 0; j < input[0].length(); j++)
            {
                // 각 자리의 차이를 구한다.
                if(input[0].charAt(j) != input[1].charAt(i + j))
                {
                    diff++;
                }
            }

            // 해당 자리의 차이가 결과보다 작으면
            result = Math.min(result, diff);
        }

        // 출력
        bw.write(result + "\n");
        bw.flush();

    }

}

---

제출 화면

오늘은 사실 간단하게 생각하면 풀 수 있는 문제를 가지고왔다.

알고리즘 문제를 풀다 보면 시간복잡도를 생각해서 이런 무지막지한 방법은 아예 제외하고 생각하는 경우가 있는데 그런 관념을 박살내버리라고 말하는 문제인것 같다.