[백준] 문자열 (java) Greedy

2020-03-11

문자열 (백준> Greedy)

문제 링크

문제설명

길이가 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의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

예제 입력 1 복사

adaabc aababbc

예제 출력 1 복사

2


풀이

package Greedy;

import java.util.*;

public class beak_문자열 {

	//30min
    static public void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        String a = sc.nextLine();
        String s[] = a.split(" "); //s[0]이 s[1]보다 작다
             
        int count = 0;            	int min = 100;
        if(s[0].length() == s[1].length()){
            for(int i=0; i<s[0].length(); i++) {
            	if(s[0].charAt(i) != s[1].charAt(i))
            		count++;
            }
        }
        else{
            for(int i=0; i<s[1].length()-s[0].length()+1; i++) {
            	count = 0;
            	String ss = s[0]; int front = i-1; int back = i+ s[0].length();
            	
            	while(ss.length() != s[1].length()) {
            		if(front<0 && back <s[1].length()) {
            			ss =  ss + "*";
            			back++;
            		}
            		else if(front>=0 && back >=s[1].length()) {
            			ss= "*" + ss;
            			front--;
            		}
            		else if(front>=0 && back <s[1].length()){
            			ss = "*" + ss + "*";
            			front--; back++;
            		}
            	}//while
            	
            	
            	for(int j=0; j<s[1].length(); j++) {
            		if(ss.charAt(j) == '*')
            			continue;
                	if(ss.charAt(j) != s[1].charAt(j)) {
                		count++;
                		
                	}
                }
            	min = Math.min(count, min);
            }//for
            
            count =min;
        }
        
        System.out.println(count);
    }
}

후기 (30min)

이부분을 생각해내는데 한 3분 걸렸다!

            		if(ss.charAt(j) == '*')
            			continue;

greedy이긴 하지만 A와 B가 다르다면 A의 남는 SIZE만큼 전부 *를 넣어서 체크를 해줬다!