[String] 가장 짧은 문자거리

 

가장 짧은 문자거리

 

 

설명

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

 

 

입력

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

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

 

 

출력

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

 

 

예시 입력

teachermode e

 

 

예시 출력

1 0 1 2 1 0 1 2 2 1 0

 

 

풀이

이 문제의 핵심은 왼쪽부터 탐색한 후, 오른쪽으로부터도 탐색해야 한다는 것이다.

 

 

문자열은 다음과 같은 상태이다.

 

 

1. 정답으로 리턴할 정수형 배열을 선언하고 문자열의 길이만큼의 크기를 할당한다. 변수 p를 아주 큰 수로 둔다. 여기서는 1000으로 작성했다.

 

2. 왼쪽부터 탐색하는 경우의 로직은 다음과 같다.

• 문자열의 길이만큼 반복문을 돈다.
• 문자열의 현재 위치 문자가 입력받은 문자와 같다면 변수 p를 0으로 두고 p 값을 answer의 현재 인덱스 위치에 저장한다.
• 문자열의 현재 위치 문자가 입력받은 문자와 같지 않다면 변수 p를 1 증가시키고 p 값을 answer의 현재 인덱스 위치에 저장한다.

 

왼쪽부터 탐색하는 경우가 끝나면 아래와 같은 그림이 된다.

 

 

3. 변수 p를 다시 1000으로 초기화한다.

 

4. 오른쪽부터 탐색하는 경우의 로직은 다음과 같다.

• 문자열의 현재 위치 문자가 입력받은 문자와 같다면 변수 p를 0으로 둔다. (p 값을 answer의 현재 인덱스 위치에 저장하지 않는 이유는 이미 왼쪽부터 탐색할 때 0을 넣었기 때문이다.)
• 문자열의 현재 위치 문자가 입력받은 문자와 같지 않다면 변수 p를 1 증가시키고 answer의 현재 인덱스 위치에 있는 값과 비교하여 더 작은 값을 저장한다. 이 때 더 작은 값을 찾기 위해 Math.min(int a, int b) 를 이용한다.

 

오른쪽부터 탐색하는 경우가 끝나면 아래와 같은 그림이 된다.

 

 

코드

package solve;

import java.util.Scanner;

public class Main_1_10 {

    public int [] solution(String s, char t) {

        // 배열 할당
        int [] answer = new int[s.length()];

        // p의 초기값은 큰 값
        int p = 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 변수 다시 초기화
        p = 1000;

        // 오른쪽부터 탐색
        for(int i = s.length()-1; i >= 0; i--) {
            if (s.charAt(i) == t) {
                p = 0; // answer[i] = p; 할 필요가 없음 이미 0 이기 때문
            } else {
                p++;
                answer[i] = Math.min(answer[i], p); // 작은 값 찾기
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Main_1_10 T = new Main_1_10();
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        char c = scanner.next().charAt(0);
        for(int x : T.solution(str,c)) {
            System.out.print(x + " ");
        }
    }

}