[문자열] 가장 짧은 문자 거리 .java

설명

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

입력

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

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

출력

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

예시 입력 1 

teachermode e

예시 출력 1

1 0 1 2 1 0 1 2 2 1 0

 

내 풀이

단순히 거리만을 구하는 것이면 간단하지만 문자 t와 떨어진 최소거리를 구하는 것이 어려웠다

그래서 왼쪽 -> 오른쪽, 오른쪽 -> 왼쪽의 두 번 탐색하는 방법을 생각했다

 

이전 find 문자가 발견된 인덱스 = pre 변수 -> -1로 초기화

 

• 왼-> 오

1. pre변수를 기준으로 오른쪽에 있는 숫자의 거리만 계산

2. pre값이 -1이면 발견안됨 -> 입력받는 문자열의 최대 길이인 100으로 설정하여 이후 탐색한 거리와 비교하여 최솟값으로 설정

3. pre값이 -1이 아니면 -> 이전의 찾은 문자가 존재함 -> 거리 계산 = 현재 i 값 - pre (항상 i값이 더 큼)

 

• 오 -> 왼

1. pre 변수 기준으로 왼쪽에 있는 숫자의 거리만 갱신

2. pre 변수가 -1이 아니면 -> 이전의 pre 값이 있다면 -> 위의 탐색의 결과와 비교해 더 작은 값 계산

3. 만약 pre 변수가 -1이면 위의 탐색 결과가 최솟값이기에 따로 구현하지 않음

  

 

처음 탐색에서 -1이 아닐때 값을 뭐로 하면 될지 고민하다 최솟값을 구하는 문제이기에 큰값으로 설정해버리면 된다는 걸

한번에 생각하지 못해 여러번 시도했던 문제였다

import java.util.Scanner;

public class Main {

    public static void main(String[] args)  {

        Scanner sc = new Scanner(System.in);
        String str = sc.next();//입력받은 문자열
        char find =sc.next().charAt(0);//찾아야하는 문자

        int[] answer = new int[str.length()];//결과 값을 저장하는 배열
        //이전에 find 문자가 발견된 인덱스(발견되지 않았다는 의미의 -1)
        int pre = -1;
        //왼쪽 -> 오른쪽 탐색
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == find) {//찾으면
                //현재 인덱스가 이전 인덱스가 됨
                pre = i;
                answer[i] = 0;//해당 문자이기 때문에 거리 0
               
            } else if (pre != -1) {//이전에 찾은 문자가 존재하면 거리 계산
                answer[i] = i - pre;//현재 인덱스와 pre문자의 차
            } else{//발견 안되었으면 문자열 길이의 최댓값으로 초기화 
                answer[i] = 100;
            }
        }
        //변수 pre 초기화
        pre = -1;
        //오른쪽 -> 왼쪽 탐색
        for (int i = str.length() - 1; i >= 0; i--) {
            if (str.charAt(i) == find) {
                pre = i;
            } else if (pre != -1) {//위 탐색의 거리와 비교해 더 작은 값 계산
                answer[i] = Math.min(answer[i], pre - i); 
            }
        }
        //결과 출력
        for(int i : answer){
            Systehttp://m.out.print(i+" ");
        }

    }


}

 

 

 

다른 풀이

내 풀이와 접근 방식은 비슷하지만 훨씬 간결한 방법이다

 

1. 거리 변수 p를 문자열 거리인 100보다 더 크게 설정한다

2. 찾는 문자가 아니면 p를 하나 증가시킨다

3. 찾는 문자이면 p를 0으로 초기화한다

=> 여기서 p가 0이 되고 이후 p가 증가한 값은 찾는 문자와 현재 문자와의 거리가 된다

4. 왼 -> 오, 오-> 왼 두 번의 탐색을 하며 마지막 탐색땐 현재 값과 기존 값 중의 최솟값으로 설정

 

이 점이 대박이다 어떻게 생각한거지..ㅠㅠ

너무 간결해서 놀랐다..

 

import java.util.Scanner;

public 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의 p인덱스 값은 이미 초기화때 0이기에 변화 없음
            } else{
                answer[i] = ++p;//p를 하나 증가시킨 뒤 저장
            }
        }
        p=1000;
        for(int i = s.length()-1; i >= 0; i--){
            if(s.charAt(i) == t){
                p=0;
            } else{
                answer[i] = Math.min(answer[i],++p);//둘 중 최솟값을 저장
            }
        }
        return answer;
    }


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


    }


}