Skip to main content

[Java] 142086 가장 가까운 같은 글자

1. 문제

가장 가까운 같은 글자

2. 정답코드

해시맵

import java.util.*;

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[s.length()];
        Arrays.fill(answer, -1);
        Map<Character, Integer> lastIndex = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (lastIndex.containsKey(c)) {
                answer[i] = i - lastIndex.get(c);
            } 
            lastIndex.put(c, i);
        }
        
        return answer;
    }
}
  1. s의 길이만큼 answer 배열 생성
  2. -1초 로 초기화한다.
  3. 알파벳이랑 나중에 등장한 인덱스 담아줄 해시맵 선언
  4. 문자열 순회하면서 키가 있으면 인덱스를 가져와서 i-마지막 인덱스 한 값으로 answer[i] 값 변경

단, 이 때 lastIndex.put(c, i)하는 코드 위치가 중요하다. 처음에는 if문 위에 써서 틀렸다.
반드시 키값을 조회해서 가져오는 코드 다음에 인덱스를 업데이트 하는 코드가 와야 한다.
그렇지 않으면 lastIndex값이 현재 인덱스가 되어 결과 배열이 모두 0이 담김

알파벳 배열만으로 푼 코드

첫번째시도

import java.util.*;

class Solution {
    public int[] solution(String s) {
        int n = s.length();
        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        
        // a~z 마지막 등장 위치 저장
        int[] lastIndex = new int[26];
        // 여기서 -1해주는 이유
        // 배열 초기값 -1 = 아직 등장하지 않음
        // 초기값 0 = 첫 글자가 0번째 인덱스라고 잘못 판단됨
        // Arrays.fill(lastIndex, -1);
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int idx = c - 'a'; // a~z -> 0~25
            if (lastIndex[idx] != 0) {
                answer[i] = i - lastIndex[idx];
            }
            lastIndex[idx] = i;
        }
        
        return answer;
        
    }
}

image.png

틀린 이유

  • lastIndex 배열 -1로 초기화 안해서이다.

원래 int[] 배열은 0으로 초기화된다. 첫 번째 글자가 'a'라고 해보자.

int i = 0;         // 첫 번째 글자 인덱스
int idx = 'a' - 'a'; // 0
  • 초기값을 -1로 안 했으면 lastIndex[0] = 0 (기본값)
  • 계산: i - lastIndex[idx] = 0 - 0 = 0
  • 그런데 'a'는 처음 등장한 글자이기 때문에 결과는 -1이 돼야 함
  • 따라서 정답과 다르게 0이 들어가 버림
  • Arrays.fill(lastIndex, -1); 추가해서 해결해 주었다.

수정한코드

import java.util.Arrays;

class Solution {
    public int[] solution(String s) {
        int n = s.length();
        int[] answer = new int[n];
        Arrays.fill(answer, -1);

        // a~z 마지막 등장 위치 저장, -1로 초기화
        int[] lastIndex = new int[26];
        Arrays.fill(lastIndex, -1);

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            int idx = c - 'a'; // a~z -> 0~25
            if (lastIndex[idx] != -1) {
                answer[i] = i - lastIndex[idx];
            }
            lastIndex[idx] = i;
        }

        return answer;
    }
  1. a-z까지 담을 26칸짜리 배열 선언 후 -1로 초기화
  2. s를 한 글짜씩 순회하면서 c - 'a' 아스키값으로 인덱스 구하기
  3. 만약 인덱스를 담은 lastIndex[idx]값이 -1이 아니라면,
    • 최종 인덱스가 업데이트 된 것이므로
    • 그 업데이트된 마지막 인덱스를 가져온다
    • (i - 마지막 인덱스) = 가까운 거리
  4. 만약 인덱스를 담은 lastIndex[idx]값이 -1 이라면
    • 해당 알파벳은 처음 등장한 것이므로 lastIndex[idx] 배열에 해당 인덱스를 담는다.


Back to top