가장 가까운 같은 글자

문제 파악 및 재정의

문자열 s가 주어졌을때 s의 각 위치마다 자신보다 앞에 나왔으며, 자신과 가장 가까운 곳에 있는 같은 글자의 위치를 int[]로 반환하라.

 

자료구조 및 알고리즘 선택

Counter Sorting(계수정렬)

문자열의 길이만큼의 정수형 배열과 알파벳에 해당하는 정수 배열을 선언

알파벳에 미리 -1값을 채워두고 주어진 문자열을 순회

아스키코드를 활용하여 해당 순번이 초기값인지 아닌지를 판별 후 반환할 배열에 대입

대입후 index를 넣어둠

 

구현

import java.util.Arrays;
class Solution {

    public static int[] solution(String s) {
        int[] location = new int[s.length()];
        int[] alpha = new int[26];

        Arrays.fill(alpha, -1);
        for (int i = 0; i < s.length(); i++) {

            if (alpha[s.charAt(i) - 'a'] > -1) {
                location[i] = i - alpha[s.charAt(i) - 'a'];
                alpha[s.charAt(i) - 'a'] = i;
                continue;
            }
            alpha[s.charAt(i) - 'a'] = i;
            location[i] = -1;
        }
        return location;
    }
}

 

회고

HashMap을 활용한 방법

import java.util.*;

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);
            answer[i] = i-map.getOrDefault(ch,i+1);
            map.put(ch,i);
        }
        return answer;
    }
}