#20 😂 프로그래머스 - 카드 뭉치(Level 1) / Queue 사용해보기

[문제]

출처 : https://school.programmers.co.kr

출처 : https://school.programmers.co.kr

※ 주의

- goal의 원소는 cards1, cards2의 원소들로만 이루어져 있다.

- 하지만 card1, cards2에는 goal에 없는 원소도 있을 수 있다.

- cards1과 cards2에는 서로 다른 단어만 존재한다.(중복되는 단어가 없다는 얘기다.)

 

cf) 추가 테스트 케이스

card1 : [a, b, c]
card2 : [d, e]
goal  : [b, c, d, e]

---

[해설]

- 이러쿵 저러쿵 하면서 어떻게든 풀어보려 했는데 결국 못 풀었다.

- 다른 사람의 풀이를 참고하며 오답 정리를 해보자

1.

import java.io.*;

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        int index1 = 0;
        int index2 = 0;

        for(int i = 0; i < goal.length; i++){
            String tmp = goal[i];

            if(index1 < cards1.length && tmp.equals(cards1[index1])) index1++;
            else if (index2 < cards2.length && tmp.equals(cards2[index2])) index2++;
            else return "No";
        }

        return "Yes";
    }
}

1-1. (index1 < cards1.length) / (index2 < cards2.length) 부분이 있어야하는 이유

- 아래의 케이스를 봐보자

cards1 : ["i", "water", "drink"]
cards2 : ["want", "to"]
goal : ["i", "want", "to", "drink", "water"]

(i = 0)
String tmp = "i"
int index1 = 0;
int index2 = 0;

if(index1 < cards1.length && tmp.equals(cards1[0])) index1++;
true --> index1 = 1

else if (index2 < cards2.length && tmp.equals(cards2[0])) index2++;
false --> index2 = 0

(i = 1)
String tmp = "want"
int index1 = 1;
int index2 = 0;

if(index1 < cards1.length && tmp.equals(cards1[1])) index1++;
false --> index1 = 1

else if (index2 < cards2.length && tmp.equals(cards2[0])) index2++;
true --> index2 = 1

(i = 2)
String tmp = "to"
int index1 = 1;
int index2 = 1;

if(index1 < cards1.length && tmp.equals(cards1[1])) index1++;
false --> index1 = 1

else if (index2 < cards2.length && tmp.equals(cards2[1])) index2++;
true --> index2 = 2

(i = 3)
String tmp = "drink"
int index1 = 1;
int index2 = 2;

if(index1 < cards1.length && tmp.equals(cards1[1])) index1++;
false --> index1 = 1

else if (index2 < cards2.length && tmp.equals(cards2[2])) index2++;
false --> index2 = 2
==> Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2

- (cards2.length = 2) 이므로 마지막 원소는 cards2[1]이다.
- 그렇기에 cards2[2]를 하면 오류가 나는 것이다.
- 따라서 참조할려는 index 변수(index1, index2)의 값이 각각 cards1, cards2 array의 범위를 넘지 않는지 체크해줘야한다.

 

2. 

- Queue와 LinkedList를 사용한 문제 풀이가 있기에 적어본다.

- Queue는 FIFO(First In First Out) 알고리즘으로서 먼저 들어온 것이 먼저 나간다는 규칙을 가지고 있다.

https://coding-factory.tistory.com/602

- java에서 Queue는 LinkedList를 이용해 생성할 수 있다.

import java.util.Queue;
import java.util.LinkedList;
Queue<자료형> queue = new LinkedList<자료형>();

cf)
Queue<자료형> queue = new Queue<자료형>() --> 이런 식으로 생성할 수 없다.

- Queue에서 사용할 수 있는 method는 아래와 같다.

Queue 삽입 : Enqueue
- add(e)   : 삽입 성공 시 true 반환, 사용 가능 공간이 없어 삽입 실패 시 IllegalStateException 발생
- offer(e) : 삽입 성공 시 true 반환, 사용 가능 공간이 없어 삽입 실패 시 false 반환

Queue 삭제 : Dequeue
- remove() : 헤드 요소를 조회(출력 가능)하고 제거, Queue가 비어 있다면 예외 발생
- poll()   : 헤드 요소를 조회(출력 가능)하고 제거, Queue가 비어 있다면 null 반환
ㄴpoll()은 데이터를 조회하면서 동시에 Queue에서 데이터를 꺼낸다.

Queue 조회
- size() : Queue 사이즈 확인
- element() : 헤드 요소 조회 및 반환, Queue가 비어 있다면 예외 발생
- peek() : 헤드 요소 조회 및 반환, Queue가 비어 있다면 null 반환
ㄴpeek()는 데이터를 조회만 하는거지 Queue에서 데이터를 꺼내지는 않는다.

cf) 헤드 요소 = Queue의 가장 첫 번째에 있는 데이터(= 가장 먼저 들어온 놈)

- Queue를 이용하면 아래와 같이 풀 수 있다.

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        Queue<String> goalQ = new LinkedList<String>();
        Queue<String> cards1Q = new LinkedList<String>();
        Queue<String> cards2Q = new LinkedList<String>();

        for(String s1 : goal) goalQ.offer(s1);
        for(String s2 : cards1) cards1Q.offer(s2);
        for(String s3 : cards2) cards2Q.offer(s3);

        while(goalQ.size() > 0) {
            String tmp = goalQ.poll();
            if(tmp.equals(cards1Q.peek())) cards1Q.poll();    
            else if(tmp.equals(cards2Q.peek())) cards2Q.poll();
            else return "No";
        }
        return "Yes";
    }
}

https://coding-factory.tistory.com/602

[Java] 자바 Queue 클래스 사용법 & 예제 총정리

https://velog.io/@kwon/JAVA-Queue%EC%9D%98-%EA%B0%9C%EB%85%90-%EB%B0%8F-%EC%82%AC%EC%9A%A9-%EC%A0%95%EB%A6%AC

[JAVA] Queue의 개념 및 사용 정리