[백준] 알고리즘 분류(문자열,JAVA)1120번, 문자열

문제 링크

1120번: 문자열

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 문자열 A와 B가 주어지며 A의 길이는 B보다 작거나 같습니다.

2. A에는 앞이나 뒤에 아무 알파벳을 추가할 수 있습니다.

3. A와 B가 길이가 같으면서 차이가 최소인 개수를 결과로 출력합니다.

4. 문자열의 차이는 각 위치에 대한 글자수가 다른 수입니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. A문자열이 B문자열에 차이를 모두 구해서 가장 작은 값을 구합니다.

 

3. 가장 작은 값을 결과를 출력합니다.

 

문자열 차이 구하기.

 

※이 문제에서 A문자열에 알파벳을 추가할 수 있으나 문제에서는 차이가 최소로 되어야 하기 때문에 B문자열과 동일한 문자만 추가되어야 합니다.

 

예를 들어A = "abc"B = "abcd"최소를 구하는 것으로써 A는 항상 'd'만 추가되는 것으로써 기존의 있던 A와 B의 차이가 최소 값이 결과가 됩니다.

 

차이를 구하는 방법

a	b	c	d
a	b	c		0
	a	b	c	3

B에 A가 들어갈 수 있는 위치에서 각 글자들을 비교하여 다른 횟수를 구합니다.

 

예제입력 3.

 

1. 입력된 정보를 저장합니다.

 

A : "koder"

B : "topcoder"

 

2. A문자열이 B문자열에 차이를 모두 구해서 가장 작은 값을 구합니다.

t	o	p	c	o	d	e	r
k	o	d	e	r				4
	k	o	d	e	r			5
		k	o	d	e	r		5
			k	o	d	e	r	1

 

가장 작은값 : 1

 

3. 가장 작은 값을 결과를 출력합니다.

 

1 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용해서 띄어쓰기 기준 A와 B를 나누었습니다.
• A와 B의 문자열의 길이가 같으면 문자열의 차이를 구합니다.
• A와 B의 문자열의 길이가 다르면 완전 탐색으로 문자열의 차이를 비교하여 최소값을 구합니다.
• 문자열의 차이의 최소값을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        String A = st.nextToken();
        String B = st.nextToken();
        int answer = 51;
        //A와 B의 길이가 같을 때 1번만 비교.
        if(A.length() == B.length()){
            answer = 0;
            for(int i=0;i<A.length();i++) {
                if (A.charAt(i) != B.charAt(i))
                    answer++;
            }
        }
        //A와 B의 길이가 다를 때 완전 탐색 진행
        else{
                for(int i=0;i<B.length();i++){
                    if((B.length() - i) - (A.length()) >= 0){
                        int temp = 0;
                        int index = 0;
                        //차이 탐색
                        for(int j=i;j < i + A.length();j++){
                            if(A.charAt(index++) != B.charAt(j))
                                temp++;
                        }
                        //차이 최소값 구하기
                        answer = Math.min(temp, answer);
                    }
                }
            }
        bw.write(answer + "");	//차이 최소값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}