About Computer

문제 

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면

"hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

입출력

입출력 #1

문제에 나온 예와 같습니다.

입출력 #2

target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

제한 사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

코드

function solution(begin, target, words) {
    var answer = 0;
    if(words.indexOf(target)==-1) return answer;
    
    var queue = [{word:begin, searched:[]}];
    var result = [];
    while(queue.length!=0) {
        var temp = queue.shift();
        for(var i=0; i<words.length; i++) {
            var tempArr = temp.searched;
            if(tempArr.length>=words.length) continue;
            if(tempArr.length == 0 || tempArr.indexOf(i) == -1) {
                if(checkWord(temp.word, words[i])) {
                    if(words[i] == target) {
                        result.push(tempArr.length+1);
                        continue;
                    }
                    queue.push({word: words[i], searched: [...tempArr, i]});
                }
            }
        }
    }
    if(result.length==0) return answer;
    answer = Math.min(...result);
    
    return answer;
}

function checkWord(myWord, next) {
    var count = 0;
    var copy = next.split('');
    for(var i=0; i<myWord.length; i++) {
        if(copy.indexOf(myWord[i]) != -1) {
            count++;
            copy.splice(copy.indexOf(myWord[i]), 1);
        }
    }
    if(count==myWord.length-1) return true;
}

설명

이 문제에서 실수했던 2가지에 대해 설명하자면, 

입출력 예시에서 단어 길이가 3인 경우만 생각해서 "한 번에 한 개의 알파벳만 바꿀 수 있습니다." 부분을 간과하고 알파벳이 2개 일치하는지를 체크했다가 틀렸었다.

그래서 (단어의 길이-1)개의 알파벳이 일치하는지를 체크해서 해결했다. 

그렇게 해서 다른 테스트케이스는 다 통과했는데 테스트케이스 3에서 오답이 나왔다.

뭐가 문젠지 모르겠어서 질문하기 게시판에 누군가 올린 테스트케이스3과 관련한 글을 봤더니,

단어에 중복된 알파벳이 있는 경우라는 힌트를 얻게 되었다.

그래서 코드를 수정해서 제출했더니 정답. 

문제 

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

입출력

제한 사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

코드

function solution(brown, yellow) {
    var answer = [];
    var size = brown+yellow;
    
    for(var i=1; i<=Math.ceil(yellow/2); i++) {
        var first=0, second=0;
        if(yellow%i==0) {
            first = brown/2 - i;
            second = brown/2 - yellow/i;
        }
        if(first<1 || second<1) continue;
        if(first*second == size) answer = [first, second];
    }
    
    answer.sort((a,b)=>b-a);
    return answer;
}

문제 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

입출력

입출력 #1

[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

입출력 #2

[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
＊ 11과 011은 같은 숫자로 취급합니다.

제한 사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

코드

function solution(numbers) {
    var answer = 0;
    var numArr = numbers.split('');
    var stack = [{num:'', index:[]}];
    var result = [];
    
    while(stack.length!=0) {
        var temp = stack.pop();
        
        for(var i=0; i<numArr.length; i++) {
            var tempIndex = temp.index;
            
            if(tempIndex.length>=numbers.length) continue;
            if(tempIndex.length==0 || tempIndex.indexOf(i)==-1) {
                var newNum = Number(temp.num+numArr[i]);
                
                if(result.indexOf(newNum)==-1 && isPrime(newNum)) {
                    result.push(newNum);
                }
                stack.push({num:temp.num+numArr[i], index:[...tempIndex,i]});
            }
        }
    }
    answer = result.length;
    return answer;
}

function isPrime(num) {
    if(num<2) return false;
    for(var i=2; i<num; i++) {
        if(num%i==0) return false;
    }
    return true;
}