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

문제

문자열 s가 주어졌을 떄, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.

예를 들어 s = 'banana' 라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

• b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
• n도 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
• a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.

따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2] 가 됩니다.

입출력 예

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

 

풀이

function solution(s) {
    let answer = [];
    let lastMap = new Map();

    for (let i = 0; i < s.length; i++) {
        if (lastMap.has(s[i])) answer.push(i - lastMap.get(s[i]));
        else answer.push(-1);
        
        lastMap.set(s[i], i);
    }

    return answer;
}

 

 

핵심은 s의 문자 하나하나가 이 앞전에 존재했던 문자인지 확인하는 과정이 될 것이다.

이를 판단하기 위해 Map 자료구조를 사용하여 문자와 그 문자의 가장 최근 인덱스를 같이 저장해주고자 하였다.

 

if(lastMap.has(s[i])) 를 통해 현재 문자가 map 안에 있는 정보인지, 즉 이전에 있었던 같은 문자인지 판별하고 그 결과에 따라 answer 에 인덱스 차이값/-1 을 push 한다.

 

이후 set 메서드를 통해 map 안의 문자의 최신 인덱스를 업데이트 한다.

 

예를 들어 s가 'banana' 일 경우 시행은 다음과 같다.

i / s[i]	map	answer
0 / b	{ 'b' : 0 }	-1
1 / a	{ 'b' : 0, 'a' : 1 }	-1, -1
2 / n	{ 'b' : 0, 'a' : 1, 'n' : 2 }	-1, -1, -1
3 / a	{ 'b' : 0, 'a' : 3, 'n' : 2 }	-1, -1, -1, 2(3-1)
4 / n	{ 'b' : 0, 'a' : 3, 'n' : 4 }	-1, -1, -1, 2, 2(4-2)
5 / a	{ 'b' : 0, 'a' : 5, 'n' : 4 }	-1, -1, -1, 2, 2, 2(5-3)

 

따라서 결과는 [ -1, -1, -1, 2, 2, 2 ] 로 출력된다.

 

출력 결과