프로그래머스 가장 가까운 같은 글자 JAVA 풀이 (해시맵, 문자열)

📌 문제 개요

문자열의 각 위치마다 자신보다 앞에 등장했던 같은 문자 중 가장 가까운 위치와의 거리를 구하는 문제

• 처음 등장한 문자는 -1
• 이전에 등장한 문자는
  현재 인덱스 - 이전 인덱스

banana

[-1, -1, -1, 2, 2, 2]

---

📌 접근 방법

문자를 순서대로 탐색하면서
각 문자의 마지막 등장 위치를 저장

• 처음 등장한 문자 : -1
• 이미 등장했던 문자 : 현재 위치 - 이전 위치 계산
• 이후 현재 위치로 갱신

---

📌 핵심 아이디어

핵심은 가장 최근 위치만 저장하면 된다는 점

예를 들어 "banana"에서 마지막 a를 처리할 때:

a의 이전 위치 = 3
현재 위치 = 5
거리 = 2

가장 가까운 문자만 필요하므로
이전 모든 위치를 저장할 필요가 없다

HashMap<Character, Integer>

 

형태로 관리하면 됩니다.

---

📌 전체 코드

import java.util.HashMap;

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

        int[] answer = new int[s.length()];
        HashMap<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {

            char ch = s.charAt(i);

            // 처음 등장한 문자
            if (!map.containsKey(ch)) {
                answer[i] = -1;
            } else {
                // 현재 위치 - 이전 위치
                answer[i] = i - map.get(ch);
            }

            // 현재 위치 저장
            map.put(ch, i);
        }

        return answer;
    }
}

---

📌 나의 오답 / 실수 포인트

처음에는 문자열을 매번 뒤로 탐색해서 이전 문자를 찾으려고 했습니다.

O(N²)

이 되어 비효율적입니다.

HashMap으로 마지막 위치를 저장하면
문자 하나당 O(1)로 처리할 수 있어 전체 O(N)에 해결 가능합니다.

---

📄 정리

• 가장 가까운 이전 문자 = 가장 최근 등장 위치
• HashMap으로 마지막 위치 저장
• 문자열 한 번 순회로 해결 가능
• 시간복잡도 O(N)