[Programmers][Java] 프로그래머스 코딩테스트 Lv. 1 - 카드 뭉치

📝 문제

1. 문제 설명

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

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

예를 들어 첫 번째 카드 뭉치에 순서대로 ["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 함수를 완성해주세요.

---

2. 제한사항

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

---

3. 입출력 예

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"

 

---

4. 입출력 예 설명

• 입출력 예 #1
   본문과 같습니다.
  
• 입출력 예 #2
   cards1에서 "i"를 사용하고 cards2에서 "want"와 "to"를 사용하여 "i want to"까지는 만들 수 있지만 "water"가 "drink"보다 먼저 사용되어야 하기 때문에 해당 문장을 완성시킬 수 없습니다. 따라서 "No"를 반환합니다.

📝 작성한 코드

 처음엔 HaspMap을 써보려다 실패하고 작성한 코드인데, 다른 분들이 작성한 걸 보니 HashMap을 써서 푸신 분이 꽤나 있었다. 이 외에도 Queue(큐)라는 클래스를 사용하신 분들이 많았다. 큐는 선입선출법의 성격을 지닌 자료구조라고 한다. 문제의 조건에서 카드 뭉치를 순서대로 한장 씩 사용한다고 했으므로, 큐의 성격을 이용하여 문제를 풀어보면 좋을 것 같다.
 
 내가 작성한 코드는 간단히 for문을 돌려 진행되는 코드이다. 처음에는 goal[i]와 cards[i]를 비교해보면 된다고 생각했는데, 인덱스범위 오류가 나는 걸 보고 cards의 길이는 goal의 길이보다 작다는 것을 깨달았다. 그래서 cards의 인덱스 값을 따로 변수 (card1Index)로 주고 cards1[card1Index]이 goal에 들어있는 값과 일치하면 그 인덱스에 해당하는 cards의 값은 다시 사용할 수 없도록 +1을 해주었다. 그리고 answer의 초기값을 Yes로 설정해두고 if문의 조건1과 2가 제대로 실행되않으면 No를 반환하도록 하였다.
 

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        String answer = "Yes";
        int card1Index = 0;
        int card2Index = 0;
 
        for (int i = 0; i < goal.length; i++) {
            if (card1Index < cards1.length && cards1[card1Index].equals(goal[i])){
                card1Index++;
            }
            else if(card2Index < cards2.length && cards2[card2Index].equals(goal[i])){
                card2Index++;
            }
            else {
                answer = "No";
            }
        }    
                 
        return answer;
    }
}

 

📝 공부해 볼 코드

Queue(큐)를 사용한 코드.
큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태를 가진다. FIFO 형태는 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 선입선출을 의미한다.
 
<코드 설명>

1. Queue<String> queue1 및 Queue<String> queue2를 생성하고, 각각 cards1 및 cards2 배열을 큐로 변환하여 초기화
2. for (String g : goal) 루프를 통해 목표 배열을 순회한다. 루프 내에서는 peek()라는 메서드를 통해 현재 목표 g가 queue1 또는 queue2의 맨 앞에 있는 카드와 일치하는지 확인한다.
3. * queue.peek(); // queue의 첫번째 값 참조
4. 만약 g가 queue1의 맨 앞에 있는 카드와 일치한다면, queue1.poll()를 사용하여 큐에서 해당 카드를 제거한다. 이어서 continue 키워드를 사용하여 다음 목표로 이동한다.
5. * queue.poll(); // queue에 첫번째 값을 반환하고 제거 비어있다면 null
6. 만약 g가 queue2의 맨 앞에 있는 카드와 일치한다면, queue2.poll()를 사용하여 큐에서 해당 카드를 제거한다. 이어서 continue 키워드를 사용하여 다음 목표로 이동한다.
7. 만약 g가 어느 큐에도 일치하지 않는다면, "No"를 반환하며 프로그램을 종료시킨다
8. 모든 목표를 순회한다면, "Yes"를 반환한다.

import java.util.*;

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        String answer = "";

        Queue<String> queue1 = new LinkedList<>(Arrays.asList(cards1));
        Queue<String> queue2 = new LinkedList<>(Arrays.asList(cards2));

        for (String g : goal) {
            if (g.equals(queue1.peek())) {
                queue1.poll();
                continue;
            } else if (g.equals(queue2.peek())) {
                queue2.poll();
                continue;
            }
            return "No";
        }

        return "Yes";
    }
}

 

Queue(큐) 참고 주소
https://coding-factory.tistory.com/602