[알고리즘]가장 짧은 문자거리

▷ 문제

한 개의 문자열 s와 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소거리를

출력하는 프로그램을 작성하세요.

* 입력

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

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

* 출력

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

▷ 입력 예시

teachermode e

▷ 출력 예시

1 0 1 2 1 0 1 2 2 1 0

▷ 풀이

1. 이중 for문을 이용하여 일일이 비교하여 연산

import java.util.Scanner;

public class Main {
    public int[] solution(String str, char c){
        int[] answer = new int[str.length()];
        char[] cArr = str.toCharArray();

        for (int i = 0; i < cArr.length; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < cArr.length; j++) {
                if(cArr[j] == c){
                    int tmp = Math.abs(i - j);
                    if (min > tmp) {
                        min = tmp;
                    }
                }
            }
            answer[i] = min;
        }

        return answer;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner kb = new Scanner(System.in);
        String str = kb.next();
        char c = kb.next().charAt(0);

        for (int x : main.solution(str, c)){
            System.out.print(x + " ");
        }
    }
}

 

2. 왼쪽부터, 그리고 오른쪽부터 각각 for문을 돌려 해당하는 문자에는 0, 나머지는 그 문자로부터 거리를 적재

import java.util.Scanner;

public class Main {
    public int[] solution(String str, char c){
        int[] answer = new int[str.length()];
        int p = 1000;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == c) {
                p = 0;
                answer[i] = p;
            } else {
                p++;
                answer[i] = p;
            }
        }
        p = 1000;
        for (int i = str.length()-1; i >= 0 ; i--) {
            if (str.charAt(i) == c) {
                p = 0;
            } else {
                p++;
                answer[i] = Math.min(answer[i], p);
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner kb = new Scanner(System.in);
        String str = kb.next();
        char c = kb.next().charAt(0);

        for (int x : main.solution(str, c)){
            System.out.print(x + " ");
        }
    }
}