[알고리즘] 가장 가까운 같은 글자

1. 조건

s의 길이가 최대일때는 10,000이고

최악의 경우를 생각한다면 (9999 + 0) * 5000 = 약 5천만 번

순회한다고 생각할 수 있다. 이때 순회중에는 단순 비교만 할 것이니

시간초과가 나지 않을것으로 생각되어 이중 반복문으로 문제를 풀기 시작했다.

 

2. 풀이 과정

바깥쪽 반복문에서는 i가 0부터 s의 길이만큼 반복하고

안쪽 반복문에서는 j가 i부터 0번까지 i만큼 반복한다.



반복하는중에는 s[i]와 s[j]가 일치하는지 확인하고

일치한다면 i - j의 값을 answer에 삽입하고

j가 0이되면 일치하는 값이 없다는것으로 -1을 answer에 삽입해주는 방법으로 풀이하였다.

 

3. 풀이

function solution(s) {
  const answer = [-1];

  for (let i = 1; i < s.length; i += 1) {
    const target = s[i];

    for (let j = i - 1; j > -1; j -= 1) {
      if (target === s[j]) {
        answer.push(i - j);
        break;
      }
      if (j < 1) {
        answer.push(-1);
        break;
      }
    }
  }

  return answer;
}