[프로그래머스 JS] 가장 가까운 같은 글자

📖 문제 설명

문자열 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]

 

---

⌨️ 나의 풀이 (코드)

 

먼저 의사 코드를 작성해 코드 풀이에 필요한 과정을 정리해 보았다..

 

1. s의 각 글자를 순회 
2. s를 순회하며 같은 글자가 있다면 가장 가까운 거리값 반환할 배열에 추가
3. 같은 글자가 없다면 -1을 배열에 추가

 

의사 코드를 기반으로 코드를 작성했으나, 코드 작성 중 몇 가지 고려하지 못한 부분들이 있다는 것을 알게 되어 의사 코드를 수정했다.

 

1. s의 각 글자를 순회 => 객체로 해당 글자들의 인덱스(배열)를 기록 
2. s를 순회하며 같은 글자가 있다면 가장 가까운 거리값을 배열에 추가 (이때, 배열의 요소가 2개 이상이라면 거리를 비교해 가장 가까운 거리를 반환값에 추가)
3. 같은 글자가 없다면 -1을 배열에 추가

 

 

이후 수정된 의사 코드를 기반으로 코드를 작성했다.

 

function solution(s) {
  const answer = [];
  const charLib = {};

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

    if (charLib[currentChar] === undefined) {
      charLib[currentChar] = [i];
      answer.push(-1);
    } else {
      let closest = i - charLib[currentChar][0];
      if (charLib[currentChar].length > 1) {
        charLib[currentChar].forEach((charIdxVal) => {
          const distance = i - charIdxVal;
          if (distance < closest) {
            closest = distance;
          }
        });
      }
      answer.push(closest);
      charLib[currentChar].push(i);
    }
  }

  return answer;
}

 

이를 통해 기본 테스트와 추가 테스트 케이스들을 모두 통과했다.

 

---

📝 Note

 

다른 사람의 풀이에서 좀 더 효율적인 정답을 찾았다.

 

function solution(s) {
    const hash={};

    return [...s].map((v,i)=>{
        let result = hash[v] !== undefined ? i - hash[v] : -1;
        hash[v] = i;
        return result;
    });
}

 

로직의 방향성은 비슷하지만 알고리즘 풀이에 있어 가독성이 더 좋고, 논리의 흐름을 이해하기 더 합리적이라고 생각했다.

 

1. spread 문법( [...s] )과 .map() 함수를 활용해 배열을 반환하는 방식으로 불필요한 변수의 선언 및 할당을 줄였다.
2. 삼항 연산자 활용을 통해 if 문을 생략하고 비교가 필요한 조건과 각각의 조건에 따른 값을 알 수 있어 구조를 이해하기 더 편하다.
3. 객체의 키-값을 실시간으로 업데이트해 요소에 따라 비효율적이었던 거리 비교 과정을 생략했다.