프로그래머스 [Lv. 4] [3차] 자동완성 {언어 : JavaScript}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/17685

프로그래머스

정답 코드

function solution(words) {
    let answer = 0;
    class Node {
        constructor(alpha) {
            this.alpha = alpha;
            this.count = 1;
            this.next = [];
        }
    }
    const map = new Map();
    
    for (const word of words) {
        const len = word.length;
        let currNode = new Node(word.at(0));
        if (!map.has(word.at(0))) {
            map.set(word.at(0), currNode);
        } else {
            currNode = map.get(word.at(0));
            currNode.count++;
        }
        for (let i = 1; i < len; i++) {
            const a = word.at(i);
            const aNode = new Node(word.at(i));
            if (currNode.next.length === 0) {
                currNode.next.push(aNode);
                currNode = aNode;
            } else {
                let isFound = false;
                for (const v of currNode.next) {
                    if (v.alpha === a) {
                        v.count++;
                        currNode = v;
                        isFound = true;
                        break;
                    }
                }
                if (!isFound) {
                    currNode.next.push(aNode);
                    currNode = aNode;
                }
            }
        }
    }
    for (const word of words) {
        const len = word.length;
        let curNode = map.get(word.at(0));
        let isFound = 1;
        for (let j = 1; j < len; j++) {
            const a = word.at(j);
            if (curNode.count === 1 || curNode.next.length === 0) {
                break;
            } else {
                isFound++;
                let isMatched = false;
                for (const v of curNode.next) {
                    if (v.alpha === a) {
                        curNode = v;
                        isMatched = true;
                    }
                }
                if (!isMatched) {
                    break;
                }
            }
        }
        answer += isFound;
    }
    return answer;
}

풀이 방법

 

1. map 생성 및 Node 클래스 정의
   • 알파벳을 키로 하는 map을 생성한다.
   • 단어의 첫 번째 문자를 키로 설정한다.
   • Node 클래스를 정의하며, Node는 자신의 알파벳(alpha), 다음 알파벳 리스트(next), 그리고 자신이 호출된 횟수(count)를 저장한다.
2. 단어 저장 및 Node 연결 처리
   1. words 배열에 있는 모든 단어를 순회하며 저장한다.
   2. 각 단어의 첫 번째 문자를 map에서 검색한다.
      • 첫 번째 문자가 map에 존재하지 않는 경우, 새로운 Node를 생성하고 map에 저장한다.
      • 존재한다면 새로 저장하지 않고, currNode를 map에 저장된 값으로 변경한다.
   3. 단어의 두 번째 문자부터는 현재 Node의 next 리스트에 저장하거나, 이미 존재하는 경우 해당 Node를 참조한다.
3. 얕은 복사 및 참조값 공유 주의
   • Node 객체를 참조할 때 얕은 복사(shallow copy)가 발생한다.
   • 이는 Node를 복사하거나 다른 변수에 할당하더라도 실제 객체의 참조값을 공유한다는 의미이다.
   • 예를 들어
     1. const stack = [];으로 정의한 후
     2. const tmpStack = stack;으로 할당하면
     3. tmpStack.push(1)과 stack.push(1)은 동일한 결과를 갖는다.
4. 저장된 데이터를 기반으로 단어 탐색 및 최소 입력 횟수 계산
   1. 각 단어를 다시 순회하며, map에서 첫 번째 문자의 Node를 가져와 탐색을 시작한다.
   2. 탐색 중 현재 Node의 count가 1이거나, next 리스트가 비어 있으면 탐색을 멈춘다.
      • 이 경우 해당 단어를 고유하게 구분할 수 있기 때문이다.
   3. 탐색을 계속할 때마다 최소 입력 횟수를 1씩 증가시킨다.
   4. next 리스트에서 현재 알파벳과 일치하는 Node를 찾고, 참조를 이동하며 탐색을 이어간다.
   5. 모든 단어에 대해 계산된 입력 횟수를 누적하여 answer를 반환하면 끝!.

 

느낀점

• 문제를 풀고 내 코딩 실력이 는다고 생각했는데 오늘 면접을 보고 생각이 변했다.
• 물론 알고리즘 역량 또한 개발에 있어서 중요하지만 풀스택 개발자가 되기 위해서 공부를 한다고 하기에는 여기에 너무 많은 시간을 투자하고 있는게 아닌가 싶다.
• 앞으로는 30분에서 최대 1시간 까지만 소요하고 나머지는 프로젝트에 시간을 투자하려고 한다.
• 선택과 집중이 필요한 만큼 지금은 1분 1초가 너무 소중하다.