[프로그래머스] 142086번 - 가장 가까운 같은 글자 [Java]

프로그래머스

 

 

---

 

 

문제

 

 

제출한 코드

import java.util.Arrays;

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

        char c;
        for (int i = 0; i < s.length(); i++) {
            c = s.charAt(i);
            
            if (index[c - 'a'] == -1) result[i] = -1;
            else result[i] = i - index[c - 'a'];
            
            index[c - 'a'] = i;
        }
        
        return result;
    }
}

 

 

풀이

처음 제출했던 코드는 아래와 같았다.

class Solution {
    public int[] solution(String s) {
        
        int[] result = new int[s.length()];
        result[0] = -1;
        
        char[] c = s.toCharArray();

        for (int i = 1; i < s.length(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (s.charAt(i) == c[j]) {
                    result[i] = i - j;
                    break;
                } else result[i] = -1;
            }
        }
        
        return result;
    }
}

 

for문을 중첩으로 사용하다 보니 시간복잡도가 늘어나서 성능이 좋은 코드는 아니었다.

문제를 해결한 후 다른 사람들의 풀이를 확인해 보니, 배열을 하나 더 선언하고 for문을 한 번만 사용해서 푼 코드가 있었다.

 

먼저 아래와 같이 해당 알파벳이 언제 마지막으로 나왔는가에 대한 index 를 저장하는 배열 을 선언하고,

문제에서 처음 나오는 알파벳은 -1 로 반환해야 하므로 Arrays.fill() 을 통해 배열 index를 -1로 초기화했다.

int[] index = new int[26];
Arrays.fill(index, -1);

 

이후 s의 길이만큼 result 배열을 선언하고 아래와 같이 for문을 사용했다.

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

    if (index[c - 'a'] == -1) result[i] = -1;
    else result[i] = i - index[c - 'a'];

    index[c - 'a'] = i;
}

 

만약 해당 알파벳의 index 값이 -1이면(처음 나왔다면) result에는 -1을,

그렇지 않으면 result에 현재 위치(i)에서 index에 저장된 위치(마지막으로 나온 위치)를 뺀 값을 넣어준다.

이후 해당 index 값을 현재 위치(i)로 변경해준 후 result를 반환해주면 된다.