자바(Java) 알고리즘 문제풀이 입문 10. 문자거리

 

 

[문제 분석]

* 문자열 s (길이 100이하)

* 문자 t 

 

예시 입력1에서, 문자열 s = teachermode , 문자열 t = e

 

예시 출력 1

1       // s[0] = t 와 s[1] = e 사이의 거리 = 1
0       // s[1] = e와 s[1] = e 사이의 거리 = 0
1      // s[2] = a 와 s[1] = e 사이의 거리 = 1
2      // s[3] = c 와 s[1] = e 사이의 거리 = 2
1      // s[4] = h 와 s[5] = e 사이의 거리 = 1
0      // s[5] = e와 s[5] = e 사이의 거리 = 0
1      // s[6] = r 와 s[5] = e 사이의 거리 = 1
2      // s[7] = m 와 s[5] = e 사이의 거리 = 2
2      // s[8] = o 와 s[10] = e 사이의 거리 = 2
1      // s[9] = d 와 s[10] = e 사이의 거리 = 1
0      // s[10] = e 와 s[10] = e 사이의 거리 = 0

 

 

[문제 해결]

문자간의 최소 거리를 구하는 방법

탐색을 할 때, 해당 문자열의 앞에 있는 'e' 와의 거리 와, 문자열 뒤에 있는 'e'와의 거리를 비교해서 최소한의 거리를 구해야함

 

1. for 문  >  해당 문자열의 앞에있는 e 와의 거리 구하기 

 

2. for문 > 문자열 뒤에 있는 'e'와의 거리와 비교해서 더 적은 값

 

 

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

public class Main {
    public void solution() throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String s = st.nextToken();
        char t = st.nextToken().charAt(0); // Convert the string token to a char


        int[] answer = new int[s.length()];
        int p = 1000;   //일단 처음 값을 1000으로 두기
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == t) {
                p = 0;
                answer[i] = p;
            } else {
                p++;
                answer[i] = p;
            }
        }

        p = 1000;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == t) {
                p = 0;
            } else {
                p++;
                answer[i] = Math.min(answer[i], p);
            }
        }

        for (int i : answer) {
            System.out.print(i + " ");
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}