가장 짧은 문자거리

설명

한 개의 문자열 s와 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소거리를 출력하는 프로그램을 작성하세요.

 

입력

첫 번째 줄에 문자열 s와 문자 t가 주어진다. 문자열과 문자는 소문자로만 주어집니다.

문자열의 길이는 100을 넘지 않는다.

 

출력

첫 번째 줄에 각 문자열 s의 각 문자가 문자 t와 떨어진 거리를 순서대로 출력한다.

예시 입력 1 

teachermode e

 

예시 출력 1

1 0 1 2 1 0 1 2 2 1 0

 

소스 코드 1

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static int[] solution(String s, String t) {
        int[] ans = new int[s.length()];
        Arrays.fill(ans, 101); //ans의 모든 배열을 101로 초기화 해준다. (문자열 길이가 100이 넘지 않으므로)
        //s에서 t를 찾는다.
        //s 와 t 같을 시 배열에 0 저장
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == t.charAt(0)) {
                ans[i] = 0;
            }
        }
        //왼쪽 t부터 차례대로 비교해가며 최단거리 ans 배열에 대입
        for (int i = 0; i < s.length(); i++) {
            if (ans[i] == 0) {
                for (int j = 0; j < s.length(); j++) {
                    if (i > j) {
                        if (ans[j] > i - j) {
                            ans[j] = i - j;
                        }
                    } else {
                        if (ans[j] > j - i) {
                            ans[j] = j - i;
                        }
                    }
                }
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        for (int sol : solution(s, t)) {
            System.out.print(sol + " ");
        }
    }
}

 

소스 코드 2

import java.util.Scanner;

public class Main {
    public static int[] solution(String s, char t) {
        int[] ans = new int[s.length()];
        int p = 1000; //큰 수로 초기화 해 놓는다.
        
        //t와 같은 문자가 있다면 0 대입, 아니라면 p를 1씩 증가시켜 대입한다.
        //왼쪽 t 기준으로 거리를 대입하는 알고리즘
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == t) {
                p = 0;
                ans[i] = p;
            } else {
                p++;
                ans[i] = p;
            }
        }

		//오른쪽 t 기준으로 거리를 대입하는 알고리즘
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == t) { //이미 위에서 0을 대입했으니 대입은 안 해줘도 됨
                p = 0;
            } else {
                p++;
                ans[i] = Math.min(p, ans[i]); //먼저 있던 거리와 새로운 거리중 최단거리 대입
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        char t = sc.next().charAt(0);
        for (int sol : solution(s, t)) {
            System.out.print(sol + " ");
        }
    }
}