[백준/BOJ] 1120번 : 문자열 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

1120번: 문자열

---

- 문제 -

 

난이도 실버 4 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

앞뒤로 문자를 추가한다곤 하지만 결국 주어진 값 A에서 B패턴에 맞게 최소한의 개수만 바꾸면 된다는 것이다.

예를 들어 A 가 acd이고, B가 abcdef면 추가하는거 생각하지 말고 그냥 A가 B와 비교했을때 A에서 몇개를 바꿔야 B에 알맞게 비교될 수 있는가를 본다. 보면 A 가 acd이고, B에서 연달아 제일 많이 포함된 부분으로 보면 bcd이다. 그렇담 A에 a를 b로 바꾸면 bcd로 같아진다. 그런것이다.

 

풀이로 가보자.

두 문자열을 입력 받는다. A는 B보다 문자열 길이가 짧거나 같다. 그렇다면 A를 B에 비교해보자.

비교방법은 심플하다. A를 B의 맨 앞부터 같은 길이만큼 비교하고 한칸씩 옆으로 이동시킬 거시다.

예를 들어보자. 예제4번 A : abc, B : topabccoder이다.

그럼 처음 abc를 B에 같은 길이 top와 비교를 한다. 다른 개수는 3개. 한칸 이동하자. abc, opa 다른 개수는 3개. abc, pab 다른 개수는 3개, abc, abc 다른 개수는 0개, 뒤로도 쭉 나오겠지만 여기서는 다른점이 제일 적은 개수를 구하는 것이기에 0보다 작을 것은 없으니 0으로 출력한다.

 

B길이에서 A길이를 뺀만큼 반복하는 반복문을 만든다. 바로 위에 풀이로 말한 A길이로 B의 끝자리까지 비교하기 위해 B길이에서 A길이를 뺸만큼 반복해야한다.

A길이만큼 반복하는 반복문을 만든다. 이 반복문 안에서 A 0인덱스부터 마지막 인덱스까지 B와 비교한다.

하지만 B는 처음엔 0부터 A마지막 인덱스값까지 이지만, 두번째 세번째는 1부터, 2부터이다. 그걸 염두하자.(코드로 보면  이해 할 수 있을 것이다)

두 문자열을 비교하면서 다른 개수를 체크한다. 해당 반복문이 끝날때마다 나온 개수를 이전 개수와 더 작은 값을 변수에 저장한다.

모든 반복문이 끝나고, 변수에 저장 된 최솟값을 출력한다.

 

코드로 보자.

---

-풀이-

 

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

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();
		//최솟값을 구하기 위해 처음 값을 주어질수 있는 문자열 최대 길이인 50을 저장.
		int result = 50;
		
		for(int i = 0; i <= (B.length() - A.length()); i++) {
			int count = 0;
			for(int j = 0; j < A.length(); j++) {
				if(A.charAt(j) != B.charAt(j + i)) {
					count++;
				}
			}
			result = Math.min(result, count);
		}
		System.out.println(result);
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.