[Programmers] Lv.1 | 가장 가까운 같은 글자 | Java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/142086

 

풀이

class Solution {
    public int[] solution(String s) {

        // 정답을 넣을 배열.
        // 문자열 s의 각 위치마다 "앞에서 가장 가까운 같은 글자가 얼마나 떨어져 있는지" 넣어야 하므로
        // s와 똑같은 길이로 만든다.
        int[] answer = new int[s.length()];

        // 알파벳 소문자는 총 26개(a~z) 이므로
        // 각 문자가 마지막에 등장한 위치를 저장할 공간을 26칸 만든다.
        // 예: lastIndex[0] = 'a'의 마지막 위치, lastIndex[1] = 'b'의 마지막 위치 ...
        int[] lastIndex = new int[26];

        // 처음에는 모든 문자가 등장한 적 없으므로 -1로 초기화한다.
        // 왜 -1? → "등장한 적 없음"을 표시하기 위한 값.
        for (int i = 0; i < 26; i++) {
            lastIndex[i] = -1;
        }

        // 문자열의 첫 글자부터 끝 글자까지 차례대로 확인한다.
        for (int i = 0; i < s.length(); i++) {

            char c = s.charAt(i);   // i번째 문자를 꺼낸다.
            // 해당 문자가 lastIndex 배열에서 어느 칸을 써야 하는지 구한다.
            // 예: 'a'→0, 'b'→1 ...  (ASCII 코드 이용한 계산)
            int idx = c - 'a';

            // lastIndex[idx]가 -1이라는 뜻은?
            // → 이 문자는 지금까지 단 한 번도 등장한 적 없다.
            if (lastIndex[idx] == -1) {

                // 앞에서 같은 문자가 없으므로 규칙에 따라 -1을 넣는다.
                answer[i] = -1;

            } else {

                // lastIndex[idx]에는 "이 문자(c)가 마지막으로 등장했던 위치"가 저장되어 있다.
                // 현재 위치 i에서 마지막 등장 위치를 빼면
                // → "바로 앞에 나온 같은 문자와의 거리"가 된다.
                // 예: 이전 a가 1번 위치, 지금이 3번 위치면 3 - 1 = 2칸 차이
                answer[i] = i - lastIndex[idx];
            }

            // 이제 현재 문자의 위치(i)를
            // "이 문자의 마지막 등장 위치"로 저장해둔다.
            // 그래야 다음에 같은 문자가 나왔을 때 이 정보를 사용할 수 있다.
            lastIndex[idx] = i;
        }

        // 결과를 담은 배열을 반환한다.
        return answer;
    }
}

import java.util.*;

class Solution {
    public int[] solution(String s) {

        // 결과를 저장할 배열 (문자열 s의 각 위치마다 값 1개씩)
        int[] answer = new int[s.length()];

        // 각 문자가 '마지막으로 나온 위치'를 저장하는 Map
        // 예: map.get('a') → 'a'가 마지막으로 발견된 인덱스
        HashMap<Character, Integer> lastPosition = new HashMap<>();

        // 문자열을 왼쪽부터 끝까지 순서대로 탐색
        for (int i = 0; i < s.length(); i++) {

            char ch = s.charAt(i);   // 현재 문자 가져오기

            /*
             * map.getOrDefault(ch, i + 1)의 의미:
             *   - ch가 이전에 나왔으면: map.get(ch) → 이전 위치
             *   - ch가 처음 등장한 문자라면: 기본값 i+1을 사용
             *
             * 왜 i+1을 기본값으로? (핵심)
             *   answer[i] = i - (이전 위치 또는 기본값)
             *   만약 최초 등장이라면:
             *       i - (i + 1) = -1  → 규칙대로 "앞에 같은 글자 없음"을 뜻함
             */
            int previousIndex = lastPosition.getOrDefault(ch, i + 1);

            // 현재 위치 i에서 이전 위치 previousIndex를 빼서 거리 계산
            // 이전에 없었으면 → i - (i+1) = -1  이므로 자연스럽게 -1 처리됨
            answer[i] = i - previousIndex;

            // 현재 문자의 위치를 최신 위치로 저장하여 다음 반복에서 사용
            lastPosition.put(ch, i);
        }

        // 최종 결과 배열 반환
        return answer;
    }
}