[Programmers] 가장 가까운 같은 글자 - Java

문제 

프로그래머스

 

풀이

최신에 나왔던 인덱스를 기록해야한다. 

최신에 나왔던 인덱스를 기록하기 위해, HashMap을 사용했다. 

HashMap 컬렉션 생성자 설명

여기에서 보면, 디폴트 크기로 16개의 양을 생성한다고 되어있다.

알파벳의 전체 갯수는 26개이지만, 26개의 key(a ~ z)를 저장한 int 배열을 모두 저장할 필요는 없다고 생각이 들어서, HashMap을 사용했다.

 

1. HashMap에서는 (문자, 정수) 쌍으로 현재 문자가 나온 최신 인덱스를 기록한다.

2-1. HashMap key에 문자가 없을 경우, 처음 나온 것이므로, -1을 넣어준다.

2-2. HashMap key에 문자가 있을 경우, 현재인덱스에서 문자가 나온 최신 인덱스를 빼서 간격을 넣는다.

3. 현재 인덱스에 해당하는 문자에 대한 최신 인덱스를 갱신한다.

 

HashMap  vs int[]

하지만, 무엇이 더 좋은 판단이었을지 알아보니, HashMap과 int 배열 중, character, Integer값과 같은 Wrapper 객체로 저장하면, 객체에 대한 오버헤드(해시 버킷, 오토박싱)과 같은 추가 메모리 소요가 존재한다.

int와 같은 Primitive타입은 4바이트 배열만 저장되어, 메모리가 더 효율적이다.

또한 이 문제는 문자 종류가 매우 적어서 int 배열이 유리하다.

소스코드

HashMap 풀이

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int[] solution(String s) {
        Map<Character, Integer> indexMap = new HashMap<>();
        
        int len = s.length();
        int[] answer = new int[len];
        
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            
            if (indexMap.containsKey(ch)) {
                answer[i] = i - indexMap.get(ch);
            } else {
                answer[i] = -1;
            }
            
            //가장 가까운 인덱스 기록
            indexMap.put(ch, i);
        }
        
        return answer;
    }
}

 

int[] 풀이

import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;

class Solution {
    public int[] solution(String s) {
        int len = s.length();
        
        int[] answer = new int[len];
        int[] lastIndex = new int['z' - 'a' + 1];
        
        Arrays.fill(lastIndex, -1);
        
        for (int i = 0; i < len; i++) {
            int idx = s.charAt(i) - 'a';
            
            answer[i] = lastIndex[idx] == -1 ? -1 : i - lastIndex[idx];
            
            lastIndex[idx] = i;
        }
        
        return answer;
    }
}