[Java] 카드 뭉치 (programmers)

Haeun Noh·2023년 7월 17일

Java programmers 카드 뭉치

programmers

목록 보기

56/64

0718

문제 설명

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

원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
한 번 사용한 카드는 다시 사용할 수 없습니다.
카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.
예를 들어 첫 번째 카드 뭉치에 순서대로 ["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의 길이 ≤ cards1의 길이 + cards2의 길이
1 ≤ goal[i]의 길이 ≤ 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"`

입출력 예 설명

입출력 예 #1

본문과 같습니다.

입출력 예 #2

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

풀이 방식

이 문제는 순서대로 cards1과 cards2의 문자열을 나열했을 때 goal의 배열과 똑같아질 수 있는가를 묻는 문제입니다.

저는 처음에 이중 for문을 사용하여 풀려고 하였으나 조금 더 간소화하여 풀 수 있는 방법이 있을 것 같았고 이내 다음의 방법으로 문제를 풀 수 있었습니다.

cards1의 현재 인덱스와 cards2의 현재 인덱스를 나타내는 idx1과 idx2를 준비합니다.
for문을 통해 모든 goal의 문자열을 돕니다.
만약 현재 goal배열의 문자열이 cards1의 문자열 또는 cards2문자열과 같은 것이 없다면 "No"를 리턴하여 종료합니다.

그럼 더 자세히 코드를 뜯어보도록 하겠습니다.

    public String solution(String[] cards1, String[] cards2, String[] goal) {
        int idx1 = 0, idx2 = 0;

cards1의 현재 인덱스와 cards2의 현재 인덱스를 가지는 idx1과 idx2을 준비합니다.
각각의 변수는 배열의 시작 인덱스인 0으로 초기화를 시켜줍니다.

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

goal에 들어있는 문자열이 cards1또는 cards2에 있는지를 판별해야 하기 때문에 goal배열의 전체를 돌 수 있는 for문을 만들어줍니다.

기준 문자열인 goal[i]은 중복사용이 될 것이므로 편리하게 변수로 선언해주었습니다.

            if ( (idx1 < cards1.length) && str.equals(cards1[idx1]) ) {
                idx1++;
            } else if ( (idx2 < cards2.length) && str.equals(cards2[idx2]) ) {
                idx2++;
            } else {
                return "No";
            }
        }
        return "Yes";

이 문제의 핵심이 되는 "Yes"와 "No"를 판별하는 부분입니다.

여기서 제가 빠뜨려 고심했던 부분은 크게 두 가지가 있었습니다.

cards1과 cards2의 인덱스가 실제 인덱스를 초과하지는 않았는가?
인덱스를 초과했는지를 먼저 물어보았는가?

먼저 첫 번째 부분을 보도록 합시다.
처음에는 str.equals(cards1[idx1])로 비교하기만 했습니다.
그 결과는 Exception에러였습니다.
보통 위의 에러가 발생하는 이유는 인덱스 허용범위를 넘어섰기 때문입니다.

고민을 해본 결과 cards1 또는 cards2의 인덱스 범위를 고려하지 않고 무조건적으로 idx1 또는 idx2의 값을 증가시켰기 때문에 해당 에러가 발생했다는 사실을 깨달을 수 있었습니다.

따라서 str.equals(cards1[idx1]) && (idx1 < cards1.length)로 바꿔주었고 이제는 됐겠지 싶었지만 또 다시 같은 에러가 발생하게 되었습니다.

이 것이 바로 두 번째 부분입니다. 또 다른 Exception에러가 발생한 것입니다.

이 Exception에러가 나는 이유는 바로 str.equals(cards1[idx1]) &&부분때문이었습니다.
분명 저는 인덱스를 초과했는지를 물어보았지만 그것은 str.equals(cards1[idx1]) &&가 실행된 후의 일이었습니다.
다시 말해 str.equals(cards1[idx1]) && 이 실행된 후에야 idx1이 Exception에러를 발생시켰는지 시키지 않았는지를 판단을 한다는 말입니다.

이렇게 되면 비교하는 부분에서는 인덱스가 허용범위를 넘어설 수 있기 때문에 Exception에러가 발생하게 된 것이었습니다.

이를 해결하기 위해 문자열 비교보다 앞에서 인덱스가 허용범위를 넘어섰는지를 판단해주었습니다.

이렇게 goal배열 안에 cards1의 문자열 또는 cards2의 문자열이 없다면 "No"를 리턴시켜 프로그램을 종료하고,

goal배열을 만들 수 있어 for문이 정상적으로 종료된다면 "Yes"를 리턴하여 문제를 해결하게 되었습니다!

소스 코드

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