[인프런 자바/java] 10. 가장 짧은 문자거리 _디버깅의 눈물

체크 포인트

 

1. (1)왼쪽에서 오른쪽 탐색과 (2)오른쪽에서 왼쪽 탐색

 

 

예제)

teachermode e

 

 

-문자열 s의 각문자와, 문자 t 간의 최소거리를 어떻게 구할지에 생각하면서 다소 시간이 걸렸다.

-추론한 방법은

(1)문자열 s의 첫번째 문자 't'에서부터 끝 문자'e'까지 하나씩 탐색하며 e와의 거리를 구한 후,

(2)문자열 s의 마지막 문자 'e'에서부터 첫번째 문자't'까지 다시 하나씩 탐색해, 둘 중 더 작은 수를 최소거리로 입력하는 것이다.

 

 

t e a c h e r m o d e    e

// (1)왼쪽에서 오른쪽으로 진행하면서 이전 e와의 거리 탐색
0 0 1 2 3 0 1 2 3 4 0

// (2)오른쪽에서 왼쪽으로 진행하면서 이전 e와의 거리 탐색
1 0 3 2 1 0 4 3 2 1 0

 

 

 

-추론 과정을 살펴보면, 위와 같이 진행된다. 이후 (1)배열과 (2)배열의 결과를 비교해, 더 작은 값을 입력해 '최소 거리' 배열을 만들면되는 것이다.

 

 

// (1)과 (2)를 비교해 최소 거리 값을 배열의 값으로 입력한 결과
0 0 1 2 1 0 1 2 2 1 0

// 정답
1 0 1 2 1 0 1 2 2 1 0

 

 

-하지만 (1)과 (2)를 비교한 배열은 실제 정답과 다르다. 여기에는 한가지 문제가 존재한다. 문자열 s의 첫번째 값은 t인데 e와의 거리가 0으로 입력된 것이다.

 

 

 

 

1. 문자 e를 만나기 전에 값을 1000으로 초기화!

-이를 방지하기 위해 처음 문자 e를 만나기 전의 최소 거리값을 int count=1000으로 초기화해준다. 1000으로 초기화한 이유는 문자열s의 최대 길이가 100인데 이보다 크게 설정하기 위한 것 이다. 해당 문제에서 int count=100으로 설정해도 정답처리가 된다.

 

 

  t  e a c h e r m o d e    e

// (1)왼쪽에서 오른쪽으로 진행하면서 이전 e와의 거리 탐색
1000 0 1 2 3 0 1 2 3 4 0

// (2)오른쪽에서 왼쪽으로 진행하면서 이전 e와의 거리 탐색
  1  0 3 2 1 0 4 3 2 1 
  
// (1)과 (2)를 비교해 최소 거리 값을 배열의 값으로 입력한 결과
  1  0 1 2 1 0 1 2 2 1 0

// 정답
  1  0 1 2 1 0 1 2 2 1 0

 

 

-'처음 문자 e를 만나기 전의 최소 거리값을 int count=1000으로 초기화'한 후 위의 과정을 다시 진행한 결과, 정답을 제대로 도출해낼 수 있었다.

 

 

 

 

 

 

풀이

 

 

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

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(), " ");
    	
    	// 문자열의 길이 s
    	String s = st.nextToken();
    	// 비교할 문자 t
    	String t = st.nextToken();
    	
    	// 탐색 시작
    	solution(s,t);

    	
    } // end of main
    
    
    static void solution(String s, String t){

    	// t로부터의 거리를 카운팅해주는 변수 count
    	// 1000으로 초기화하는 이유는 
    	// 문자열 s의 시작이 t가 아닌 경우를 처리하기 위한 것
    	int count = 1000;
    	
    	// 문자 t와의 거리를 담아주는 배열 선언
    	int[] arr = new int[s.length()];
    	
    	// 왼쪽 끝에서 오른쪽 끝 방향으로 문자열 s 탐색
    	for(int i=0; i<s.length(); i++){
    		// 문자 t인 경우,
    		if(s.charAt(i)==t.charAt(0)){
    			// 0으로 초기화
    			count = 0;
    			arr[i] = count;
    		}
    		// 문자 t가 아닌 경우,
    		else{
    			// 문자 t와의 거리 1증가,
    			count++;
    			arr[i] = count;
    		}
    		
    	}
    	
    	// 왼->오 탐색 후 초기화
    	count = 1000;
    	
    	// 오른쪽 끝에서 왼쪽 끝 방향으로 문자열 s 탐색
    	for(int i=s.length()-1; i>=0; i--){
    		
    		// 문자 t인 경우,
    		if(s.charAt(i)==t.charAt(0)){
    			// 0으로 초기화
    			count = 0;
    		}
    		// 문자 t가 아닌 경우,
    		else{
    			// 문자 t와의 거리 1증가,
    			count++;
    			// 기존에 입력된 거리값 arr[i]와 새로운 거리값 count 중 최소 거리를 입력 
    			arr[i] = Math.min(arr[i], count);
    		}
    		
    	}
    	
    	// 문자 t와의 최소거리 배열 출력
    	for(int i=0; i<s.length(); i++){
    		System.out.print(arr[i] + " ");
    		
    	}
    	
    }
    
} // end of Main