문제링크

문제 이해

[ 입력형태 / 조건 ]

s
문자열 | "banana"

[ 문제 ]

=> 각 문자들이 해당 문자열에서 얼마나 최근에 나왔는지를 배열에 넣어서 return

[ 풀이 ]

26의 크기를 가진 알파벳 배열을 만들어서 최근 인덱스를 저장

---

코드

> [성공] 1차 시도 : 알파벳 dp배열에 인덱스 저장

• 생각한 풀이 그대로 구현

import java.util.*;

class Solution {
    public int[] solution(String s) {
        int len = s.length();
        int[] answer = new int[len];
        int[] index_arr = new int[26];
        Arrays.fill(index_arr, -1);
        for(int i=0; i<len; i++){
            int cur_idx = s.charAt(i) - 'a';
            if(index_arr[cur_idx] == -1){
                index_arr[cur_idx] = i;
                answer[i] = -1;
            }else{
                answer[i] = i - index_arr[cur_idx];
                index_arr[cur_idx] = i;
            }
        }
        return answer;
    }
}

> [성공] 2차 시도 : 알파벳 Map에 인덱스 저장

import java.util.*;

class Solution {
    public int[] solution(String s) {
        Map<Character,Integer> map = new HashMap<>();
        
        int len = s.length();
        int[] answer = new int[len];
        
        for(int i=0; i<len; i++){
            Character cur = s.charAt(i);
            Integer get_idx = map.get(cur);
            if(get_idx == null){
                map.put(cur, i);
                answer[i] = -1;
            }else{
                answer[i] = i - get_idx;
                map.put(cur, i);
            }
        }
        return answer;
    }
}

=> 조금 더 개선이 가능할 것이라 생각했는데 오히려 속도는 더 느렸음

TIP : 알파벳은 26개 이고, 변환할때는 -'A' 또는 -'a'로 한다