섹션1. 문자열 - 10. 가장 짧은 문자 거리

📌 문제 설명

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

• 문자열 s와 문자 t는 소문자로만 구성됩니다.
• 문자열 s의 길이는 최대 100입니다.

---

📝 입력 & 출력

🔹 입력

• 첫 번째 줄: 문자열 s와 문자 t (공백으로 구분)

🔹 출력

• 첫 번째 줄: 각 문자에 대해 t와 떨어진 최소 거리를 출력 (공백으로 구분)

🔸 예제 입력 1

teachermode e

🔸 예제 출력 1

1 0 1 2 1 0 1 2 2 1 0

---

💡 해결 방법

1. 왼쪽에서 오른쪽으로 순회하면서 t와의 거리 계산
   • p = 1000 (큰 값)으로 초기화 후, t가 나오면 p = 0으로 변경
   • t가 아니면 p를 1씩 증가시키며 거리 계산
2. 오른쪽에서 왼쪽으로 순회하면서 최소 거리 갱신
   • t가 나오면 p = 0으로 변경
   • p를 1씩 증가시키면서 기존 값과 비교하여 최소 거리 저장

---

💻 코드 구현 (Java)

package partString;

import java.util.*;

public class Problem10 {

    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;
            } else {
                p += 1;
            }
            answer[i] = p;
        }
        
        // 오른쪽에서 왼쪽으로 거리 계산 (최소값으로 갱신)
        p = 1000;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == t) {
                p = 0;
            } else {
                p += 1;
            }
            answer[i] = Math.min(answer[i], p);
        }
        
        return answer;
    }
    
    public static void main(String[] args) {
        Problem10 T = new Problem10();
        Scanner kb = new Scanner(System.in);
        String s = kb.next(); // 문자열 입력
        char c = kb.next().charAt(0); // 문자 입력
        
        for (int x : T.solution(s, c)) {
            System.out.print(x + " ");
        }
        kb.close();
    }
}

---

📖 코드 설명

1️⃣ int[] answer = new int[s.length()]; 배열의 역할

• 문자열 s의 길이와 같은 크기의 배열을 생성하여 각 문자에서 t와 떨어진 최소 거리를 저장
• 모든 원소는 기본값 0으로 초기화되며, 이후 거리 값을 계산하여 업데이트됨

2️⃣ 왼쪽에서 오른쪽으로 거리 계산

int p = 1000;
for (int i = 0; i < s.length(); i++) {
    if (s.charAt(i) == t) {
        p = 0;
    } else {
        p += 1;
    }
    answer[i] = p;
}

• p를 큰 값(1000)으로 초기화 → t를 만나면 p = 0으로 변경
• t가 아닌 경우 p를 증가시키며 거리를 저장

3️⃣ 오른쪽에서 왼쪽으로 거리 계산 (최소값 갱신)

p = 1000;
for (int i = s.length() - 1; i >= 0; i--) {
    if (s.charAt(i) == t) {
        p = 0;
    } else {
        p += 1;
    }
    answer[i] = Math.min(answer[i], p);
}

• p를 다시 1000으로 초기화하고 오른쪽에서 왼쪽으로 순회
• t를 만나면 p = 0, 아니면 p 증가
• 기존 값과 비교하여 최소 거리만 저장 (이전 계산과 비교하여 업데이트)

---

⏳ 시간 복잡도 분석

• O(n) (n: 문자열 길이)
• 문자열을 두 번 순회(왼쪽 → 오른쪽, 오른쪽 → 왼쪽) 하므로 O(2n) = O(n)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

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