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

 

✏️ 문제 설명

문자열 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
지문과 같습니다.

입출력 예 #2
설명 생략

 

---

 

✏️ 문제 풀이

rkio.log

어떻게 풀어야 할지 몰라 이 분의 풀이를 참고해 풀었다. Level 1이상 가니 본격적으로 자료 구조 개념이 적용되기 시작했다.

function solution(s) {
    let stack = [];
    let ans = [];

    for (let i = 0; i < s.length; i++) {
        if (!stack.includes(s[i])){
            ans.push(-1);
            stack.push(s[i]);
            continue;
        }

        if (stack.includes(s[i])){
            ans.push(stack.length - stack.lastIndexOf(s[i]));
            stack.push(s[i]);
            continue;
        }
    }
    return ans;
}

stack과 답 array를 만들어주고 각 문자열 char마다 stack에 해당 문자가 없다면 -1을 답에 넣고, 스택에 해당 문자를 넣어준다.

continue로 뒤에 과정은 스킵해준다.

stack에 해당 문자가 있다면 ans에 stack.length(진행된 문자열 수) - stack.lastIndexOf(s[i]) 스택에 가장 최근에 들어간 같은 문자의 인덱스(가장 가까운 같은 글자)를 빼줘 가장 가까운 문자의 거리를 넣어준다.

역시 스택에 해당 문자를 넣어준다.

이렇게 스택을 적용하면 가장 가까운 글자의 거리를 찾기 쉽다.

 

FILO 책 더미처럼 가장 먼저 놓은 책이 아래에 깔려 가장 늦게 꺼내지는 스택 개념을 이용해 풀 수 있는 문제. Stack을 적용할 때는 push와 pop 메서드로 구현한다.

 

- 다른 풀이

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

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

 

const solution = (s) =>
  [...s].map((char, i) => {
    const count = s.slice(0, i).lastIndexOf(char);
    return count < 0 ? count : i - count;
  });

 

 

공부하면서 정리하는 글입니다. 잘못된 점이 있다면 피드백 남겨주시면 감사합니다 🙂