99클럽 코테 스터디 11일차 TIL , 카드 뭉치

문제

풀이

입력으로 카드뭉치 두 개와 목푯 값이 String 배열로 주어진다.

카드뭉치에서 목표값이 되도록 카드를 조합하면 되는데, 카드뭉치에서 카드를 꺼낼 때는 정해진 순서를 바꿀 수 없고 다른 뭉치로 넘어가려면 해당 카드뭉치에서 카드를 사용해야 한다.

 

goal 배열에서 하나씩 빼서 카드 뭉치를 살펴보고 없다면 "No"를 출력하고 goal배열에 있는 값이 모두 사용된다면 "Yes"를 출력하면 된다. 

제출 1 - 오답

import java.util.*;
class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        int idx1 = 0;
        int idx2 = 0;
        int cards1Length = cards1.length;
        int cards2Length = cards2.length;
        int cnt = 0;
        
        Deque<String> que = new ArrayDeque<>();
        for(String str : goal) que.offer(str);
        
        while(!que.isEmpty() && cnt < cards1Length + cards2Length + 1){

            while(idx1 < cards1Length && que.peek().equals(cards1[idx1])){
                idx1++;
                que.poll();
            }
            
            while(idx2 < cards2Length && que.peek().equals(cards2[idx2])){
                idx2++;
                que.poll();
            }
            
            cnt++;
        }
        
        String answer;
        if(que.isEmpty()){
            answer = "Yes";
        }else{
            answer = "No";
        }

        return answer;
    }
}

 

카드뭉치마다 idx를 선언한다.

cnt는 while문이 얼마나 도는지 확인한다. goal의 길이는 두 개의 카드뭉치의 길이와 같거나 작기 때문에 횟수가 두 개의 길이를 합친 것보다 같거나 작다.

큐를 사용해 goal을 넣고 하나씩 해결한다.

인덱스가 각 카드뭉치의 길이보다 작고 que의 최상단값이 같은 뭉치를 해결한다.

각 반복마다 적어도 하나의 goal이 해결된다. 만약 되지 않으면 해결되지 않는 문제이다.

제출2 - 정답

import java.util.*;
class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        int idx1 = 0;
        int idx2 = 0;
        int cards1Length = cards1.length;
        int cards2Length = cards2.length;
        int cnt = 0;
        
        Deque<String> que = new ArrayDeque<>();
        for(String str : goal) que.offer(str);
        
        while(!que.isEmpty() && cnt < cards1Length + cards2Length + 1){

            while(idx1 < cards1Length 
                  && !que.isEmpty()
                  && que.peek().equals(cards1[idx1])){
                idx1++;
                que.poll();
            }
            
            while(idx2 < cards2Length 
                  && !que.isEmpty()
                  && que.peek().equals(cards2[idx2])){
                idx2++;
                que.poll();
            }
            
            cnt++;
        }
        
        String answer;
        if(que.isEmpty()){
            answer = "Yes";
        }else{
            answer = "No";
        }

        return answer;
    }
}

 

peek() 할 때 que가 빈 값인 것을 확인해야 한다.

다른 풀이

import java.util.*;
class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        String answer = "Yes";
        int idx1 = 0;
        int idx2 = 0;
        
        for(int goalIdx=0;goalIdx<goal.length;goalIdx++){
            if(idx1 < cards1.length && goal[goalIdx].equals(cards1[idx1])){
                idx1++;
            }else if(idx2 < cards2.length && goal[goalIdx].equals(cards2[idx2])){
                idx2++;
            }else{
                answer = "No";
                break;
            }
        }
        
        return answer;
    }
}

 

코드가 너무 복잡한 것 같아 시간이 좀 지난 후에 다시 문제를 풀어봤다.

너무 간단하게 풀렸다..ㅋㅋ 

TIL

• 간단하게 풀자