[코딩테스트] 가장 가까운 같은 글자

문제 설명

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.
예를 들어, s="banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.
a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.
따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.

문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

제한사항

1 ≤ s의 길이 ≤ 10,000
s은 영어 소문자로만 이루어져 있습니다.

입출력 예

s				result
"banana"		[-1, -1, -1, 2, 2, 2]
"foobar"		[-1, -1, 1, -1, -1, -1]

문제 풀이

class Solution {
    public int[] solution(String s) {
        
        int[] answer = new int[s.length()];
        char[] arr = s.toCharArray();
        
        for(int i=0; i<answer.length; i++){
            answer[i] = -1;
        }
        for(int i=0; i<arr.length; i++){
            for(int j=0; j<i; j++){
                if(i==j) {continue;}
                if(arr[i] == arr[j]) {
                    answer[i] = i-j;
                }
            }
        }
        return answer;
    }
}

실행 속도

테스트 1 〉	통과 (0.03ms, 77.9MB)
테스트 2 〉	통과 (0.18ms, 73.3MB)
테스트 3 〉	통과 (0.20ms, 79.3MB)
테스트 4 〉	통과 (5.23ms, 78.4MB)
테스트 5 〉	통과 (105.43ms, 81.9MB)
테스트 6 〉	통과 (41.14ms, 88.5MB)
테스트 7 〉	통과 (115.39ms, 86.7MB)
테스트 8 〉	통과 (21.76ms, 88.4MB)
테스트 9 〉	통과 (104.56ms, 76.8MB)
테스트 10 〉	통과 (8.18ms, 74.9MB)
테스트 11 〉	통과 (101.18ms, 95.4MB)
테스트 12 〉	통과 (0.03ms, 75.3MB)
테스트 13 〉	통과 (0.02ms, 75.1MB)
테스트 14 〉	통과 (2.85ms, 78.1MB)
테스트 15 〉	통과 (0.02ms, 72.3MB)
테스트 16 〉	통과 (0.04ms, 78.1MB)
테스트 17 〉	통과 (0.05ms, 74.6MB)
테스트 18 〉	통과 (17.88ms, 80.3MB)
테스트 19 〉	통과 (12.45ms, 85.1MB)
테스트 20 〉	통과 (1.52ms, 75.6MB)
테스트 21 〉	통과 (0.08ms, 73.7MB)
테스트 22 〉	통과 (30.10ms, 88.8MB)
테스트 23 〉	통과 (2.81ms, 81.6MB)
테스트 24 〉	통과 (2.76ms, 76.2MB)
테스트 25 〉	통과 (3.60ms, 78.6MB)
테스트 26 〉	통과 (0.22ms, 72.1MB)
테스트 27 〉	통과 (3.21ms, 74.6MB)
테스트 28 〉	통과 (2.81ms, 71.5MB)
테스트 29 〉	통과 (0.02ms, 76.2MB)
테스트 30 〉	통과 (122.26ms, 78.5MB)

해당 문제는 쉽게 풀긴 했지만 테스트 5, 7, 9, 11, 22, 30의 효율성이 마음에 들지 않는다. 제한사항에 보면 s의 길이는 최대 10000자까지이기 때문에 시간복잡도가 낮게 나와야 하는데 내가 푼 방식으로는 어림도 없다. 그래도 쉽게 풀어낸 것에 의미가 있다고 본다.

문제 풀이2

class Solution {
    public int[] solution(String s) {
        
        int[] answer = new int[s.length()];
        char[] arr = s.toCharArray();

        for(int i=0; i<arr.length; i++){
            answer[i] = -1;
            for(int j=0; j<i; j++){
                if(i==j) {continue;}
                if(arr[i] == arr[j]) {
                    answer[i] = i-j;
                }
            }
        }
        return answer;
    }
}

실행 속도

테스트 1 〉	통과 (0.05ms, 68.7MB)
테스트 2 〉	통과 (0.12ms, 73.9MB)
테스트 3 〉	통과 (0.13ms, 79MB)
테스트 4 〉	통과 (5.24ms, 78.1MB)
테스트 5 〉	통과 (75.12ms, 88.1MB)
테스트 6 〉	통과 (22.90ms, 89.7MB)
테스트 7 〉	통과 (67.39ms, 77.1MB)
테스트 8 〉	통과 (16.69ms, 73.7MB)
테스트 9 〉	통과 (65.42ms, 77.5MB)
테스트 10 〉	통과 (7.98ms, 78.5MB)
테스트 11 〉	통과 (51.42ms, 80.5MB)
테스트 12 〉	통과 (0.02ms, 71.7MB)
테스트 13 〉	통과 (0.03ms, 76.8MB)
테스트 14 〉	통과 (3.17ms, 92MB)
테스트 15 〉	통과 (0.02ms, 73.5MB)
테스트 16 〉	통과 (0.03ms, 72MB)
테스트 17 〉	통과 (0.09ms, 73.4MB)
테스트 18 〉	통과 (7.08ms, 70.9MB)
테스트 19 〉	통과 (7.65ms, 75.6MB)
테스트 20 〉	통과 (2.52ms, 66.6MB)
테스트 21 〉	통과 (0.07ms, 77.4MB)
테스트 22 〉	통과 (24.23ms, 83MB)
테스트 23 〉	통과 (2.20ms, 80.1MB)
테스트 24 〉	통과 (3.84ms, 80.1MB)
테스트 25 〉	통과 (3.79ms, 73.9MB)
테스트 26 〉	통과 (0.28ms, 75.4MB)
테스트 27 〉	통과 (4.87ms, 80.9MB)
테스트 28 〉	통과 (4.09ms, 77.6MB)
테스트 29 〉	통과 (0.03ms, 76.4MB)
테스트 30 〉	통과 (83.73ms, 88.8MB)

    for(int i=0; i<answer.length; i++){
        answer[i] = -1;
    } 

이 부분을 없애고 다음 반복문 안에 answer[i] = -1;을 넣어줬다. 왜 내가 따로 반복문을 돌릴 생각을 했을까..?