코테14 - 가장 가까운 같은 글자

기존 코드

function solution(s) {
    let answer_arr = [];
    let s_str = s; // substr함수를 쓰기 위해 문자열 형태의 변수를 만들었다.
    s = s.split('');

    for(let i = 0 ; i < s.length; i++) {
        let answer = -1; //중복 문자가 없으면 -1을 반환하기 위해
        for(let j = 0; j < i; j++) {
            if(s[i] == s[j]) { //중복 문자가 있으면
                //기준 인덱스에 비교 인덱스를 뺀 값을 추출한다.
                answer = i - s_str.substr(0, i).lastIndexOf(s[j]); 
            }    
        }
        //가장 큰 인덱스가 남아 배열에 저장된다.
        answer_arr.push(answer);
    }
    return answer_arr;
}

이 코드는 s 문자열의 각 문자를 순회하면서 해당 문자가 이전에 등장했는지 확인하고, 가장 가까운 동일한 문자의 위치를 찾는 방식으로 동작합니다.

코드 분석

1. 문자열을 배열로 변환:

    let s_str = s; // 원본 문자열을 저장합니다.
    s = s.split(''); // 문자열을 문자 배열로 변환합니다.

2. 문자 순회:

    for (let i = 0; i < s.length; i++) {
        let answer = -1; // 기본값을 -1로 설정합니다.
        for (let j = 0; j < i; j++) {
            if (s[i] == s[j]) { // 현재 문자가 이전에 등장했는지 확인합니다.
                answer = i - s_str.substr(0, i).lastIndexOf(s[j]);
            }
        }
        answer_arr.push(answer);
    }

   • 외부 루프 (for (let i = 0; i < s.length; i++)):

     • 문자열 s의 각 문자를 순회합니다.
     • answer를 기본값 -1로 초기화합니다.

   • 내부 루프 (for (let j = 0; j < i; j++)):

     • 현재 문자 s[i]와 이전 문자 s[j]를 비교합니다.
     • 동일한 문자가 발견되면, answer를 업데이트합니다.

3. 가장 가까운 동일한 문자 위치 계산:

    answer = i - s_str.substr(0, i).lastIndexOf(s[j]);

   • s_str.substr(0, i): 문자열 s_str의 0부터 i-1까지의 부분 문자열을 생성합니다.
   • lastIndexOf(s[j]): 해당 부분 문자열에서 문자 s[j]가 마지막으로 등장하는 위치를 찾습니다.
   • i - ...: 현재 인덱스 i에서 마지막 등장 위치를 빼서, s[i]와 s[j]의 거리(차이)를 계산합니다.

예시

s = "banana"일 때, 내부 루프가 어떻게 동작하는지 살펴보겠습니다.

1. i = 3인 경우:
   • s[3] = 'a'
   • s_str.substr(0, 3) = "ban"
   • lastIndexOf('a') = 1 (문자 'a'가 "ban"에서 마지막으로 등장하는 위치는 1입니다)
   • answer = 3 - 1 = 2

이 과정을 통해 s[3]인 'a'는 1 칸 앞에 'a'가 있다는 것을 계산하여 answer 배열에 추가합니다.

결론

기존 코드에서는 각 문자의 이전 등장 위치를 찾기 위해 lastIndexOf를 사용하고, 그 결과를 바탕으로 가장 가까운 동일한 문자의 위치를 계산합니다. 이 접근 방식은 이해하기 어려울 수 있지만, 각 문자의 가장 가까운 동일한 문자를 찾기 위해 문자열의 부분을 계속 탐색하는 방식으로 동작합니다. 이 방법은 반복적으로 문자열을 탐색하기 때문에 효율적이지 않으며, 시간 복잡도가 O(n^2)입니다.

새로운 방법을 사용하면 시간 복잡도를 O(n)으로 줄일 수 있으며, 코드도 더 명확하고 효율적입니다. 이전 코드를 이해하는 데 도움이 되었기를 바랍니다!

function solution(s) {
    // 결과를 저장할 배열을 초기화합니다.
    let answer = [];
    // 각 문자의 마지막 위치를 저장할 딕셔너리를 초기화합니다.
    let lastIndex = {};

    // 문자열을 순회합니다.
    for (let i = 0; i < s.length; i++) {
        let char = s[i];
        if (lastIndex[char] !== undefined) {
            // 현재 문자의 이전 위치가 딕셔너리에 존재하면,
            // 현재 위치와의 차이를 배열에 추가합니다.
            answer.push(i - lastIndex[char]);
        } else {
            // 현재 문자가 처음 등장하는 경우 -1을 배열에 추가합니다.
            answer.push(-1);
        }
        // 현재 문자의 위치를 딕셔너리에 업데이트합니다.
        lastIndex[char] = i;
    }

    return answer;
}

코딩테스트에서 주어진 문제를 해결하기 위해서는 문자열을 순회하면서 각 문자에 대해 자신보다 앞에 나온 같은 문자의 위치를 찾아야 합니다. 이를 위해 효율적인 방법을 사용해야 합니다. 주어진 예제 코드가 문제를 해결하는 방법을 잘 설명하고 있지만, 조금 더 간단하고 효율적으로 해결할 수 있는 방법이 있습니다.

여기서는 가장 최근에 등장한 각 문자의 위치를 기록하는 방법을 사용하여 문제를 해결할 수 있습니다. 이를 위해 딕셔너리를 사용하여 각 문자의 마지막 위치를 저장하면서 문자열을 순회하면 됩니다.

아래는 이 문제를 해결하는 효율적인 접근법입니다:

1. 각 문자를 순회하면서 해당 문자의 마지막 위치를 기록합니다.
2. 현재 문자의 이전 위치를 기록한 딕셔너리를 확인하여 가장 가까운 같은 문자의 위치를 찾습니다.

코드 설명

1. answer 배열: 각 문자의 결과를 저장할 배열입니다.
2. lastIndex 딕셔너리: 각 문자의 마지막 위치를 저장합니다. 예를 들어, lastIndex['a']는 마지막으로 등장한 'a'의 인덱스를 저장합니다.
3. 문자열 순회: 문자열을 순회하면서 각 문자의 현재 위치와 마지막 위치를 비교합니다.
   • 만약 문자가 이전에 등장한 적이 있다면, 현재 인덱스와 마지막 인덱스의 차이를 answer 배열에 추가합니다.
   • 문자가 처음 등장하는 경우, -1을 answer 배열에 추가합니다.
   • 마지막으로, 현재 문자의 위치를 lastIndex 딕셔너리에 업데이트합니다.

이 방법은 문자열을 한 번만 순회하면서 필요한 정보를 딕셔너리에 저장하기 때문에 시간 복잡도는 O(n)으로 효율적입니다. 이 코드는 문제에서 주어진 예시뿐만 아니라, 다양한 입력에 대해 정확히 동작할 것입니다.