[인프런 알고리즘] Chapter 1, 10번 문제(가장 짧은 문자거리)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec01_10 {
    public static int[] solution(String s, char t) {
        int[] numArr = new int[s.length()];
        int ptr = 1000;
        for(int i = 0; i < s.length(); ++i){
            if(s.charAt(i) == t)
            {
                ptr = 0;
                numArr[i] = ptr;
            }
            else numArr[i] = ++ptr;
        }

        for(int i = s.length() - 1; i >= 0; --i){
            if(s.charAt(i) == t) ptr = 0;
            else
            {
                ++ptr;
                numArr[i] = (numArr[i] < ptr) ? numArr[i] : ptr; //Math.min(numArr[i], ptr)
            }
        }
        return numArr;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String s = st.nextToken();
        Character t = st.nextToken().charAt(0);
        for (int i : solution(s, t))
        {
            System.out.print(i + " ");
        }
    }
}

 

설명

• 입력: 문자열 s와 문자 t
• 출력: 각 문자에 대해 가장 가까운 t 문자와의 거리를 나타내는 배열
• 로직
  -numArr 배열을 초기화하여 각 문자의 거리를 저장한다.
  -ptr 변수를 1000으로 초기화하여 충분히 큰 값으로 설정한다.
  -첫 번째 루프: 왼쪽에서 오른쪽으로 이동하면서 t 문자가 발견되면 ptr을 0으로 설정하고, 그렇지 않으면 ptr을 증가시켜 numArr에 저장한다.
  -두 번째 루프: 오른쪽에서 왼쪽으로 이동하면서 t 문자가 발견되면 ptr을 0으로 설정하고, 그렇지 않으면 ptr을 증가시켜 기존 값과 비교하여 더 작은 값을 numArr에 저장한다.