Level 2 ) 영어 끝말잇기 ⭐️

Doozuu·2023년 3월 22일
0

프로그래머스 (JS)

목록 보기
96/183

문제 설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

  1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
  2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
  3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
  4. 이전에 등장했던 단어는 사용할 수 없습니다.
  5. 한 글자인 단어는 인정되지 않습니다.
  6. 다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

  • 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
  • 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
  • 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
  • 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
  • (계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

제한 사항

끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
단어의 길이는 2 이상 50 이하입니다.
모든 단어는 알파벳 소문자로만 이루어져 있습니다.
끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
정답은 [ 번호, 차례 ] 형태로 return 해주세요.
만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

입출력 예

n	words																			result
3	["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"]	[3,3]
5	["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"]	[0,0]
2	["hello", "one", "even", "never", "now", "world", "draw"]	[1,3]

분석 및 풀이

  • 가장 먼저 탈락하는 사람의 번호차례를 반환해야 한다.
    탈락하는 위치를 이용하여 번호차례를 구하는 공식은 다음과 같다.
    번호 : index % n + 1
    차례 : Math.floor(index / n) + 1

  • 배열을 순회하면서 end point가 될 때 멈추어야 한다.
    end point : 이전에 나왔던 단어가 다시 나올 때 or 마지막 문자와 시작 문자가 일치하지 않을 때
    indexOflastIndexOf가 일치하지 않으면 중복되는 단어가 있다는 뜻이므로 뒤의 위치를 기준으로 번호와 차례를 구한다.
    slice를 이용해 마지막 문자와 시작 문자를 구해 일치하는지 확인한다.

  • 배열을 다 순회했는데 아무도 탈락하지 않으면 [0,0]을 반환.

function solution(n, words) {
    var answer = [0,0];
    for(let i=0;i<words.length-1;i++){
        let idx = words.lastIndexOf(words[i]);
        if(words.indexOf(words[i]) !== idx){
            answer[0] = idx % n + 1;
            answer[1] = Math.floor(idx / n) + 1;
            break;
        }
        if(words[i].slice(-1) !== words[i+1].slice(0,1)){
            answer[0] = (i+1) % n + 1;
            answer[1] = Math.floor((i+1) / n) + 1;
            break;
        }
    }
    return answer;
}

테스트 케이스 19에서 틀렸다.

⭐️ 반례

n = 2, words = ['ac','ca','ac','ac']
-> [1,2]

위와 같이 중복되는 문자가 2개만 나오는게 아니라 여러개가 나올 수 있다.
그럴 경우 더 앞에 있는 것을 선택해야 하는데, lastIndexOf를 이용하면 가장 뒤의 것을 선택하게 되므로 답이 [2,2] 가 나와버린다.

이를 보완하기 위해 lastIndexOf 를 이용하는 대신 for문을 중첩시켜 특정 문자열의 앞에 있는 문자열들 중 일치하는 것이 있는지 확인해준다.


보완

function solution(n, words) {
    let answer = [0,0];
    for(let i=0;i<words.length;i++){
        if(i > 0){
            for(let j=0;j<i;j++){
                if(words[i] === words[j]){
                    answer[0] = i % n + 1
                    answer[1] = Math.floor(i / n) + 1;
                    return answer;
                }
            }
        } 
        if(i < words.length -1 && words[i].slice(-1) !== words[i+1].slice(0,1)){
            answer[0] = (i+1) % n + 1;
            answer[1] = Math.floor((i+1) / n) + 1;
            break;
        }
    }        
    return answer;
}

2차 보완 (2023.11.04 업데이트)

function solution(n, words){
    let used_words = [words[0]];
    for(let i=1;i<words.length;i++){
        let cur = words[i];
        let prev = used_words[i-1];
        if(used_words.includes(cur) || prev.at(-1) !== cur[0]){
            return [i % n + 1, Math.ceil((i+1) / n)];
        }else{
            used_words.push(words[i]);
        }
    }
    return [0,0];
}



다른 풀이

index를 먼저 구하고 번호와 차례를 나중에 계산한다.
중복되는지 확인할 때 for문을 이용하지 않고 indexOf를 활용.

function solution(n, words) {
    var fail_i = -1;
    for(var i = 1; i < words.length; i++){
        var val = words[i];
        if(words[i-1].substring(words[i-1].length-1) != val.substring(0, 1)) {
            fail_i = i;
            break;
        } 
        if(words.indexOf(val) != i) {
            fail_i = i;
            break;
        }
    }

    if(fail_i == -1) return [0,0];

    var no = fail_i%n + 1;
    var turn = Math.floor(fail_i/n) + 1; 

    return [no, turn];
}

reduce를 이용한 풀이

function solution(n, words) {
    let answer = 0;
    words.reduce((prev, now, idx) => {
        answer = answer || ((words.slice(0, idx).indexOf(now) !== -1 || prev !== now[0]) ? idx : answer);
        return now[now.length-1];
    }, "")

    return answer ? [answer%n+1, Math.floor(answer/n)+1] : [0,0];
}
profile
모든게 새롭고 재밌는 프론트엔드 새싹

0개의 댓글