가장 짧은 문자의 거리 값 찾는 알고리즘 - 자바

---

문제

testcase e 

라고 문자열이 주어지고 문자열 길이가 100을 넘지 않는다면,

문자열 testcase에 대해 각 문자들이 e라는 문자에 얼마나 거리가 있는지 체크하는 문제입니다.

 

1 0 1 2 3 2 1 0 의 결과 값이 나와야 합니다.

---

정답 소스

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    char[] c = s.toCharArray();
    int result[] = new int[s.length()];
    
    char target = sc.next().charAt(0);
    int targetIndex = 101;
    for(int i=0; i<s.length(); i++){
      if(s.charAt(i) == target){
        targetIndex = i; 
        result[i] = 0;
      }else{
        result[i] = Math.abs(targetIndex - i);
      }
    }
    for(int i=s.length()-1; i>=0; i--){
      if(result[i] == 0){
        targetIndex = i; 
      }else{
        if(result[i] > Math.abs(targetIndex - i)){
          result[i] = Math.abs(targetIndex - i);
        }   
      }
    }
    for(int i : result){
      System.out.print(i+" ");
    }
  }
}

---

풀이

입력을 Scanner로 받았습니다.

문자열 s를 받습니다.

그 문자열로 char형 배열을 생성해줍니다.

정답을 출력할 배열을 하나 더 만들어줍니다. (result)

---

두 번째로 입력되는 문자를 target에 입력받습니다.

문자열이 100을 넘지 않으니 101이라는 값을 targetIndex에 넣어줍니다.

---

두 번째 입력된 문자에 대해 왼쪽부터 반복을 합니다.

0~ 문자길이 만큼 반복합니다.

s.charAt(i) 가 target 이라면 그 문자열에 문자와 target에 문자의 거리는 0이 됩니다.

그리고 현재 그 문자가 targetIndex가 됩니다.

 

같지 않다면

결과배열에 현재 인덱스 위치에 절대값으로 바꿔주는 Math.abs()를 사용해

targetIndex - i를 해준 값을 넣어줍니다.

그러면, 현재 타겟이 있는 위치와 현재 문자열의 위치의 거리가 나옵니다.

 

이렇게 되면 현재 위에 예제로 본다면 result 배열에는

101 0 1 2 3 4 5 0 이 들어가 있습니다.

---

이제 반대로 오른쪽에서 부터 찾아줍니다.

문자열에 길이 -1 만큼해서 0 까지 반복해줍니다.

result[i] 값이 0 이면 targetIndex 위치가 됩니다.

0은 그대로 냅두면 됩니다.

 

0 이 아니라면,

그 값이 현재 targetIndex - i 한 값보다 큰지 확인해줍니다.

값이 크다면 result[i] 를 바꿔주면 되겠습니다.

---

출력해주면 결과 값이 나옵니다.