카드 뭉치 [프로그래머스]

문제

 

코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.

 

• 원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
• 한 번 사용한 카드는 다시 사용할 수 없습니다.
• 카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
• 기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.

예를 들어 첫 번째 카드 뭉치에 순서대로 ["i","drink","water"], 두 번째 카드 뭉치에 순서대로 ["want","to"]가 적혀있을 때 ["i","want","to","drink","water"] 순서의 단어 배열을 만들려고 한다면 첫 번째 카드 뭉치에서 "i"를 사용한 후 두 번째 카드 뭉치에서 "want"와 "to"를 사용하고 첫 번째 카드 뭉치에 "drink"와 "water"를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있습니다.

 

문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때, cards1과 cards2에 적힌 단어들로 goal를 만들었다면, "Yes"를, 만들 수 없다면 "No"를 return하는 solution함수를 완성해주세요.

 

 

 

 

 

 

제한사항

 

• 1 <= cards1의 길이, cards2의 길이<= 10
• 1 <= cards1[i]의 길이, cards2[i]의 길이 <= 10
• cards1과 cards2에는 서로 다른 단어만 존재합니다.
• 2<= goal의 길이 <= 10
• goal의 원소는 cards1과 cards2의 원소들로만 이루어져 있습니다.
• cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 이루어져 있습니다.

 

 

 

 

 

 

입출력 예

 

cards1	cards2	goal	result
["i","drink","water"]	["want","to"]	["i", "want","to" ,"drink","water"]	"Yes"
["i","water" ,"drink",]	["want","to"]	["i", "want","to" ,"drink","water"]	"No"

 

 

 

 

 

 

 

나의 풀이

 

문제 좀 잘 읽자.

 

처음에는 문제를 대충 읽고 넘겨서 바로 풀어버렸다. 잘못 이해했다.

처음 이해한 바로는 '두 개의 cards를 이용해 그 안에 있는 card로 goal이라는 문장을 만들 수 있는가'였다.

문제를 제대로 읽지 않은 내 잘못이다.

 

그렇게 나온 내 결과물들...

지우긴 아까우니까 여기 적어놓을래,,,,

 

function solution(cards1,cards2,goal) {
    const result = goal.map((el)=>{
        return cards1.includes(el) || cards2.includes(el)
    })
    
    const answer = result.reduce((acc,el)=>{
        return acc + el;
    })

    if(answer===5){
        return "Yes"
    } else {
        return "No"
    }
};


let cards1 = ["i", "drink", "water"];
let cards2 = ["want", "to"];
let goal = ["i","want","to","drink","water"];
console.log(solution(cards1,cards2,goal));

function solution(cards1,cards2,goal) {
    let total = 0;
    
    goal.forEach((el)=>{
        if(cards1.includes(el) || cards2.includes(el)===true){
            total +=1;
        }
    })
    
    if(total ===5){
        return "Yes"
    } else {
        return "No"
    };

};


let cards1 = ["i", "drink", "water"];
let cards2 = ["want", "to"];
let goal = ["i","want","to","drink","water"];
console.log(solution(cards1,cards2,goal));

 

하나는 map과 reduce를 함께 사용해봤고 다른 하나는 forEach를 사용해 풀어보았다.

 

 

여담이 길었지만 본 문제로 넘어가보겠다.

 

문제를 보고 든 풀이방법은 두 가지였다.

 

<방법1>

1. 배열1의 첫 번째 요소가 goal의 첫 요소와 다르다면 배열2의 요소와 goal 요소를 비교.

    (그 중 둘 다 같지 않으면 false를 출력)

2. 같은 요소가 있던 배열의 다음 요소를 goal의 요소와 비교하고 없으면 다른 배열로 이동

3.  ... 반복

4. goal의 끝까지 모든 요소가 존재할 경우 Yes를 리턴, 존재하지 않을 경우 No를 리턴

 

<방법2>

배열 1 = [1,2,3,4,5]라고 하면 그 사이사이에 배열 2의 요소를 넣는 방법을 생각해봤다.

배열 1 = [①,1,②,2,③,3,④,4,⑤,5] 

배열 2 = [a,b] 라고 할 때 배열2를 배열 1에 넣는 경우의 수는 반복문을 여러번 돌릴 때보다 좋다고 생각했기 때문에 효율으로 따졌을 때 좋다고 생각했기 때문에 구상해봤다.

더군다나 배열2의 순서를 지키며 넣어야 했기 때문에 배열2의 첫 번째 요소의 경우의 수가 i개라면 두 번째 요소의 경우의 수는 i-1개이기 때문에 경우의 수는 더 적어질 수 있었다.

 

<방법2>는 구상에만 그치고 실제로 코드를 완성시키지 못했기 때문에 첫 번째 방법으로 설명해보려고 한다.

 

 

 

<방법 1>은 우여곡절이 많았다.

 

[우여곡절 1]

배열 1의 첫 번째 요소가 goal과 같을 경우 배열1의 두 번째 요소와 goal 비교. ...3,4,5번째
                                                   같지 않을 경우 배열2로 이동.

배열 2의 첫 번째 요소가 goal과 같을 경우 배열2의 두 번째 요소와 goal 비교,,, 3,4,5번째

                                                   같지 않을 경우 "No"를 리턴

 

위와 같이 가지뻗기가 너무 심하게 되는 것이었다.

재귀함수를 이용해 배열1과 배열2를 왔다갔다 해보고 싶었지만 같을 경우 배열을 바꾸지 않고 요소의 순서만 바꿔주어야 했기 때문에 재귀함수를 사용한 코드도 실패했다.

 

[우여곡절 2]

배열을 자유 자재로 바꾼다고 해도 '배열의 순서'를 보장하기 어려웠다.

예를 들면 goal의 n번째 요소를 배열1의 n+1213번째에서 찾아야 할 수도 있고 배열2의 첫 번째 요소에서 찾아야 할 수도 있었다.(과장해서)

 

 

아무튼, 우여곡절 끝에 shif를 사용해서 비교가 끝난 요소들은 배열에서 내보냄으로써 배열의 순서를 유지할 수 있었고 forEach와 조건문을 같이 적어줌으로써 각 요소를 조건에 맞게 나눠줄 수 있었다.

 

코드의 결과는 다음과 같다.

function solution (cards1,cards2,goal) {
    let answer = "Yes"

    goal.forEach((el)=> {
        if(el === cards1[0]){
            cards1.shift();
        } else if(el === cards2[0]){
            cards2.shift();
        } else {
            answer = "No"
        }
    })

    return answer;
}

let cards1 = ["i", "drink", "water"];
let cards2 = ["want", "to"];
let goal = ["i","want","to","drink","water"];
console.log(solution(cards1,cards2,goal));

 

여기서 조금 더 생각해서 코드의 효율을 따져본다면 '반복문 한 바퀴를 돌 때마다 shift를 사용해주고 있기 때문에 효율이 매우 떨어지지 않을까?'라는 생각이 들었다. 

 

만약 조금 더 효율적으로 코드를 사용하기 위해서는 '배열을 반대로 정렬한 뒤에  pop을 사용해서 하나씩 제거해주면 되지 않을까?'라는 생각을 해봤다.

(shift라는 것이 실행할 때마다 배열의 모든 요소를 한 칸씩 앞당겨 줘야 하기 때문에 '반복문과 함께 쓸 경우 매우 비효율적이지 않나' 라는 생각을 했다)