문자 사이의 거리

18 Apr 2023 in Algorithm on Java, Coding, Test

문제

설명

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

입력

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

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

출력

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

예시 입력 1

teachermode e

해결방법

• 배열을 왼쪽부터 순차적으로 거리를 계산하여 배열에 넣고 , 그 다음 역순으로 돌아 기존 값보다 거리 값이 작은 경우 배열의 값을 현재 값으로 바꾼다.

  char[] s_copy = s.toCharArray();
  // 거리 값을 범위 보다 큰 수를 임시 지정 
  int p = 1000;
  // 순차적으로 탐색
  for (int i = 0; i < s_copy.length; i++) {
    // 찾고자 하는 문자열과 다른 경우는 +1 하여 지정
    if (s_copy[i] != c) {
      p++;
      answer[i] = p;
    } else {
      // 찾고자 하는 문자열과 같은 경우, 임시 값을 0으로 초기화.
      // 이렇게 되면, 다음 탐색 때 찾고자 하는 경우와 다른 경우 +1 씩 증가하여 실제 거리값이 됨
      p = 0;
      answer[i] = p;
    }
  }
  // 다시 초기화 하여 역순으로 탐색
  p = 1000;
  for (int j = s_copy.length - 1; j >= 0; j--) {
    if (s_copy[j] != c) {
      p++;
      // 여기서 핵심.
      // 기존 값보다 작은 경우 에만 교체.
      // 기존보다 작다는 의미는 더 가깝다는 의미이기 때문. 별도의 정의가 없다면 이렇게.
      if (answer[j] > p) {
        answer[j] = p;
      }
    } else {
      p = 0;
      answer[j] = p;
    }
  }
  

코드

import java.util.*;

class Main {
    public int[] solution(String s, char t) {
        int[] answer = new int[s.length()];
        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 = 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);
            }
        }
        return answer;
    }

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