[TIL] 가장 짧은 문자거리

문제

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

---

입력값

첫 번째 줄에 문자열 str와 문자 c가 주어진다. 문자열과 문자는 소문자로만 주어집니다.
문자열의 길이는 100을 넘지 않는다.

teachermode e

출력값

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

1 0 1 2 1 0 1 2 2 1 0

---

해결 방법

문자열 str의 각 문자와 입력 받은 문자 c의 거리를 answer 배열에 저장한 후, 반복문을 통해 answer의 값들을 순차적으로 반환하는 방식을 사용했다.

💡 문자열 str의 n번째 문자가 입력 받은 문자 c와 같다면 n번째 문자와 입력 받은 문자 c의 거리는 0이다.

1. 순방향 순회

순방향 순회는 0번째 문자부터 시작해 입력 받은 문자 c와의 거리를 answer 배열에 저장한다.

n번째 문자가 입력 받은 문자 c와 같은 값이라면 answer[0]에 0을 저장하고, 같지 않다면 이전 Index 값의 1을 더한 값을 저장한다.

🤔 첫번째 문자는 입력 받은 문자 c과 같다면 문제가 없지만, 다를 경우에는 이전 값이 없기 때문에 문제가 발생한다. 이런 문제를 방지하기 위해 첫번째 문자에는 임의의 수를 크게 (ex, 1000) 잡아 저장한다.

1. 임의의 수 p를 선언해 문자열의 크기보다 큰 수를 입력한다.
   1-1. p는 answer 배열에 거리의 값으로 저장된다.
2. 첫번째 문자가 입력 받은 문자 c와 같다면 p=0, 같지 않다면 p++한 후 저장한다.
3. n번째 문자가 입력 받은 문자 c와 같다면 p=0, 같지 않다면 p++한 후 저장한다.

2. 역방향 순회

순방향은 왼쪽의 입력 받은 문자 c와의 거리만 측정한다. 오른쪽에 위치한 입력 받은 문자 c의 거리가 더 작을 수 있기 때문에 역방향 순회를 해준다.

1. 임의의 수 p를 선언해 문자열의 크기보다 큰 수를 입력한다.
   1-1. p는 answer 배열에 거리의 값으로 저장된다.
2. 마지막 문자가 입력 받은 문자 c와 같다면 p=0, 같지 않다면 p++한다.
3. answr 배열에 저장된 값과 p중에 더 작은 값을 저장한다.
4. n번째 문자가 입력 받은 문자 c와 같다면 p=0, 같지 않다면 p++한 후 저장한다.
5. answr 배열에 저장된 값과 p중에 더 작은 값을 저장한다.

코드

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) throws IOException {
        Main T = new Main();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String str = st.nextToken();
        char c = st.nextToken().charAt(0);

        int[] answer = T.solution(str, c);

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