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

 

입출력 예

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

 

< 나의 풀이 >

function solution(s) {
    let arr = s.split('');
    let len = arr.length;
    let answer = Array(len).fill(-1);
    for ( let i = 0 ; i < arr.length ; i++ ){
        for ( let j = 0 ; j < i ; j++){
            if( arr[i] == arr[j] ){
                answer[i] = i - j;    
            }
        }
    }
    return answer;
}

 

 

실행 시간이 느려서 개선이 필요하다. ( 성능 요약 - 메모리 : 38MB , 시간 : 369.72 ms )

 

 

< 다른 사람의 풀이 >

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

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

// 최종적으로 hash = { b: 0, a: 5, n: 4 }

 

- 이해를 위해서 출력을 해 보았다.

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

    return [...s].map((v, i) => {
        // 각 문자의 인덱스를 계산하기 전에 현재 hash 상태를 출력
        console.log(`Before processing character '${v}' at index ${i}:`, JSON.stringify(hash));

        let result = hash[v] !== undefined ? i - hash[v] : -1;
        hash[v] = i;

        // 문자를 처리한 후 hash 상태를 출력
        console.log(`After processing character '${v}' at index ${i}:`, JSON.stringify(hash));
        
        return result;
    });
}

// 테스트 실행
console.log(solution("banana"));

 

// Before processing character 'b' at index 0: {}
// After processing character 'b' at index 0: {"b":0}
// Before processing character 'a' at index 1: {"b":0}
// After processing character 'a' at index 1: {"b":0,"a":1}
// Before processing character 'n' at index 2: {"b":0,"a":1}
// After processing character 'n' at index 2: {"b":0,"a":1,"n":2}
// Before processing character 'a' at index 3: {"b":0,"a":1,"n":2}
// After processing character 'a' at index 3: {"b":0,"a":3,"n":2}
// Before processing character 'n' at index 4: {"b":0,"a":3,"n":2}
// After processing character 'n' at index 4: {"b":0,"a":3,"n":4}
// Before processing character 'a' at index 5: {"b":0,"a":3,"n":4}
// After processing character 'a' at index 5: {"b":0,"a":5,"n":4}
// [ -1, -1, -1, 2, 2, 2 ]

 

ex) s = "banana"  출력 : [ -1, -1, -1, 2, 2, 2 ]

hash 객체는 각 문자가 마지막으로 등장한 인덱스를 저장한다.

[...s]는 문자열 "banana"를 배열로 변환하는 것이고, map 함수는 문자열의 각 문자에 대해 실행된다.

• hash[v] !== undefined : 문자가 이전에 등장한 적이 있는 경우, result = i - hash[v]
• hash[v] === undefined : 문자가 처음 등장하는 경우 , result = -1

 

[ 추가 학습 ]

• 문자열을 문자배열로 바꾸는 방법

let s = "banana";
console.log([...s]); // [ 'b', 'a', 'n', 'a', 'n', 'a' ]

 

• undefined vs null  

          1. undefined : 변수가 선언되었지만 값이 할당되지 않은 상태

let x;
console.log(x); // undefined

function foo(y) {
  console.log(y);
}

foo(); // undefined

 

          2. null : 변수에 명시적으로 "값이 없음"을 나타내는 특별한 값

let obj = null;
console.log(obj); // null

 

• 객체 : 키 - 값 쌍으로 구성된 데이터 구조 ( '{}'로 정의 )

let person = {
    name: "Alice",
    age: 30,
    profession: "Engineer"
};

console.log(person); 
// 출력: { name: 'Alice', age: 30, profession: 'Engineer' }

// 객체 접근하기
// 점 표기법
console.log(person.name); // "Alice"
person.age = 31;
console.log(person.age); // 31

// 대괄호 표기법
console.log(person["profession"]); // "Engineer"
person["country"] = "USA";
console.log(person["country"]); // "USA"