[프로그래머스 / JS] Lv.1 가장 가까운 글자

문제 설명

  문자열 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은 영어 소문자로만 이루어져 있습니다.

---

 

풀이

function solution(s) {
    let answer = s.split('').reduce((acc, cur, idx, arr) => {
        if (idx === 0) {
            acc.push(-1)
            return acc
        }

        let arrTemp = arr.slice(0,idx);
        let idxNear = arrTemp.reverse().indexOf(cur)

        if (idxNear != -1) {
            acc.push(idxNear + 1)
        } else {
            acc.push(-1)
        }

        return acc
    }, [])

    return answer
}

 

사고과정

1. s를 배열로 바꾸고 각 인덱스 값에 접근해 결과를 만들자
2. reduce로 하면 깔끔하겠는데?
3. 첫번째 인덱스는 -1로 가고 나머지 인덱스의 경우 참조 배열을 인덱스 전까지 슬라이싱 한다음에 reverse()를 적용하고 curr에 해당하는 값의 인덱스를 찾자
4. 3에서 결과를 -1인 경우와 아닌 경우 나눠서 acc에 붙이면 되겠다.

 

평가

  코드 실행에 걸리는 시간이 3881.46ms로 너무나 많이든다. 사용된 함수들 split, reduce, slice, reverse 모두 O(n)의 시간복잡도를 가지고 있고 이걸 고려하지 않고 코드를 짜서 효율성이 너무 떨어진다.

 

개선점

1. 필요하지 않은 reverse 함수의 사용

function solution(s) {
    let answer = s.split('').reduce((acc, curr, idx, arr) => {
        if (idx === 0) {
            acc.push(-1)
            return acc
        }

        let idxNear = arr.slice(0,idx).lastIndexOf(curr)

        if (idxNear != -1) {
            acc.push(idx - idxNear)
        } else {
            acc.push(-1)
        }

        return acc
    }, [])

    return answer
}

 위 코드와 같이 수정하면 코드 실행에 걸리는 시간의 최대값이 61.28ms 까지 단축된다.

 

 

2. 가장 가까운 글자를 찾는 방식을 바꾸자. 현재는 배열을 순차적으로 탐색하지만 객체를 만들어 각 키값으로 바로바로 찾을 수 있다면 실행에 걸리는 시간이 훨씬 단축될 것이다.

function solution(s) {
    let objIdx = {};
    let answer = s.split('').reduce((acc, cur, idx) => {
        if (objIdx[cur] === undefined) {
            acc.push(-1)
        } else {
            acc.push(idx - objIdx[cur])
        }   
        
        objIdx[cur] = idx
        return acc
    }, [])

    return answer;
}

위 코드와 같이 객체 자료형을 사용할 경우 실행에 걸리는 시간의 최대값이 2.73ms 까지 단축된다.

 

알게된점

1. lastIndexOf 함수도 있다 잊지말자.
2. 탐색엔 객체 자료형이 시간이 적게든다.