[프로그래머스 레벨2] 영어 끝말잇기 [Javascript/ 문자열, 스택]

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

프로그래머스

 

function solution(n, words) {
    var answer = [];
    // 첫 번째 단어의 마지막 알파벳 미리 넣기
    let char = words[0][words[0].length-1];
    for(let i = 0; i < words.length; i++){
        // 가장 먼저 탈락 하는 사람과 말 순서
        
         // 배열에서 해당 원소 개수 > 1 일 때 가장 먼저 중복되는 사람 체크
         if(words.indexOf(words[i]) !== i){
            answer.push(i%n+1, Math.floor(i/n) +1);
             break;
            //answer.push([i%n,i+1]);  [] 괄호 안 치고 ,(콤마) 쓰면 된다
         }

         // 첫 번째 사람은 안 들어감. 
      if(i > 0){ 
        if( words[i][0] === char){
            char = words[i][words[i].length-1];    
        }else{
             answer.push(i%n+1, Math.floor(i/n) +1);
             break;
        }
      }
           
    }
    
    return answer.length > 1 ? answer : [0,0];
}

 

내 코드 자가 진단

답은 맞았지만, 부족하다.

 

문제점 1) break 문을 남발

특정 조건을 만족하면 return 시켜도 되는데, break를 굳이 여러번 사용할 필요가 없어 보인다. 가독성이 떨어져 보인다.

 

 

문제점 2) 로직 간소화 필요성

내 코드는 처음에 맨 앞 단어의 마지막 알파벳(문자)를 미리 넣어놓고 시작한다. 따라서, for문에서 1번째 인덱스 부터 시작해도 되었다. 그렇게 처리하면, if(i > 0) 조건도 넣을 필요가 없다. 로직 자체를 2번째 단어(인덱스)부터 체크하면 if 조건문을 삭제 가능하다. for문의 초기식을 바꿔주자.

 

 

문제점 3) 스택 활용

나는 문자를 변수에 기억해두고 해당 인덱스의 원소(단어) 앞의 문자와 비교하고 indexOf 매서드로 중복 단어를 파악한다. 같은 원리로 단어를 순서대로 스택에 넣어두면서 중복 체크와 top의 문자 비교를 해보는 방법으로도 풀어보려고 한다.

 

 

 

리팩토링 코드

function solution(n, words) {
    var answer = [];
    // 첫 번째 단어의 마지막 알파벳 미리 넣기
    let char = words[0][words[0].length-1];
    for(let i = 1; i < words.length; i++){
        // 가장 먼저 탈락 하는 사람과 말 순서
        
         // 배열에서 해당 원소 개수 > 1 일 때 가장 먼저 중복되는 사람 체크
         if(words.indexOf(words[i]) !== i){
         // +1 씩 해주는 이유는 0번째 인덱스 처리
            return [i%n+1, Math.floor(i/n) +1];
            //answer.push([i%n,i+1]);  [] 괄호 안 치고 ,(콤마) 쓰면 된다
         }

         // 첫 번째 단어는 안 들어감. (시작 전에 넣음)
        if( words[i][0] === char){
        	// 새로운 문자(알파벳) 갱신
            char = words[i][words[i].length-1];    
        }else{
           // 앞 단어와 끝 문자와 현재 단어의 문자(알파벳)이 다르면 종료
            return [i%n+1, Math.floor(i/n) +1];
        }
    }
    return [0,0];
}

if문의 초기식을 2번째 단어(1번째 인덱스)부터 시작하고 break 대신 바로 return해준다. 만약 특정 조건을 충족하지 못하면, 끝말 잇기가 끝났으므로 [0,0]을 반환한다.

 

 

시간 복잡도 비교

왼쪽이 처음 코드 / 오른쪽이 리팩토링 코드

대체적으로 0.01 ~ 0.03 초 정도 단축되었다.

증가한 것은 컴퓨터 환경에서 배열의 길이가 작은 것은 조금 차이가 나지만, 테스트 20 같이 대용량 데이터에서는 0.25ms가 0.17ms로 0.08정도 감소했다.