[PCCP] Lv1: 카드 뭉치(159994) 해설

문제

- 문제 링크: 카드 뭉치

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) goal의 front와 cards1의 front 또는 goal의 front와 cards2의 front를 비교

1-1) 사용할 수 있는 카드가 있다면 해당 큐와 goal에서 pop을 수행 

1-2) 사용할 수 있는 카드가 있다면 동작하지 않음 

1-3) cards1, cards2 중 빈곳은 테크하지 않음 

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include <string>
#include <vector>

using namespace std;

string solution(vector<string> cards1, vector<string> cards2, vector<string> goal) {
    string answer = "No";
    
    int p1 = 0;
    int p2 = 0;
    int p3 = 0;
    
    while (p1 < cards1.size() || p2 < cards2.size() || p3 < goal.size()){
        if (goal[p3] == cards1[p1]){
            p1++;
            p3++;
        } else if (goal[p3] == cards2[p2]) {
            p2++;
            p3++;
        } else {
            break;
        }
    }
    
    if (p3 == goal.size())
        answer = "Yes";
    
    return answer;
}

solution 2)

- ?: while문에 q1.empty() || 를 추가할 경우 테스트 24번에서 실패(signal: segmentation fault(core dumped)) 발생, 제외할 경우 통과

#include <string>
#include <vector>
#include <queue>

using namespace std;

string solution(vector<string> cards1, vector<string> cards2, vector<string> goal) {
    string answer = "No";
    queue<string> q1, q2, q3;
    
    for (const string& s : cards1) q1.push(s);
    for (const string& s : cards2) q2.push(s);
    for (const string& s : goal) q3.push(s);
    
    // while (!q1.empty() || !q2.empty() || !q3.empty()){  : !q1.empty()로 24번에서 에러
	while (!q2.empty() || !q3.empty()){
        if (q1.front() == q3.front()){
            q1.pop();
            q3.pop();
        } else if (q2.front() == q3.front()) {
            q2.pop();
            q3.pop();
        } else {
            break;
        }
    }
    
    if (q3.empty())
        answer = "Yes";
    
    return answer;
}

solution 3)

- cards1과 cards2의 길이 N, goal의 길이 M

- 큐로 변환 시간복잡도: O(N + M)

- 반복문 goal 순회 시간복잡도: O(M)

#include <string>
#include <vector>
#include <queue>

using namespace std;

string solution(vector<string> cards1, vector<string> cards2, vector<string> goal) {
    string answer;
    queue<string> q1, q2, q3;
    
    // 1. cards와 goal을 queue로 변경
    for (const string& s : cards1) q1.push(s);
    for (const string& s : cards2) q2.push(s);
    for (const string& s : goal) q3.push(s);
    
	// 2. 큐를 순회
    while (!q3.empty()){
    	// 3. cards1의 front와 goal의 front가 일치할 경우
        if (!q1.empty() && q1.front() == q3.front()){
            cout << "1: " << q3.front();
            q1.pop();
            q3.pop();
        }
        // 3. cards2의 front와 goal의 front가 일치할 경우
        else if (!q2.empty() && q2.front() == q3.front()) {
            cout << "2: " << q3.front();
            q2.pop();
            q3.pop();
        }
        // 일치하는 카드가 없는 경우
        else {
            break;
        }
    }
    
    // 모두 완성될 경우 Yes, 미완성일 경우 No
    answer = q3.empty()? "Yes" : "No";
    
    return answer;
}

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: cards1과 cards2의 길이

- M: goal의 길이

- 각각 deque로 변환: O(N + M)

- 반복문에서 goal의 각 원소를 순회: O(M)

- 최종 시간 복잡도: O(N + M)

import java.util.ArrayDeque;
import java.util.Arrays;

class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        // cards와 goal을 deque로 변환
        ArrayDeque<String> cardsDeque1 = new ArrayDeque<>(Arrays.asList(cards1));
        ArrayDeque<String> cardsDeque2 = new ArrayDeque<>(Arrays.asList(cards2));
        ArrayDeque<String> goalDeque = new ArrayDeque<>(Arrays.asList(goal));
        
        // goalDeque에 문자열이 남아 있으면 계속 반복
        while (!goalDeque.isEmpty()) {
            // cardsDeque1의 front와 일치하는 경우
            if (!cardsDeque1.isEmpty() && cardsDeque1.peekFirst().equals(goalDeque.peekFirst())) {
                cardsDeque1. pollFirst();
                goalDeque.pollFirst();
            }
            // cardsDeque2와 front와 일치하는 경우
            else if (!cardsDeque2.isEmpty() && cardsDeque2.peekFirst().equals(goalDeque.peekFirst())) {
                cardsDeque2.pollFirst();
                goalDeque.pollFirst();
            }
            else {
                break; // 일치하는 원소를 찾지 못했으므로 종료
            }
        }
        // goal이 비었으면 "Yes" 아니면 "No"를 반환
        return goalDeque.isEmpty() ? "Yes" : "No";
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: cards1과 cards2의 길이

- M: goal의 길이

- 각각 deque로 변환: O(N + M)

- 반복문에서 goal의 각 원소를 순회하는 시간 복잡도: O(M)

- 최종 시간 복잡도: O(N + M)

from collections import deque

def solution(cards1, cards2, goal):
    # cards와 goal을 deque로 변환
    cards1 = deque(cards1)
    cards2 = deque(cards2)
    goal = deque(goal)
    
    # goal의 문자열을 순차적으로 순회
    while goal:
        if cards1 and cards1[0] == goal[0]: # card1의 front와 일치하는 경우
            cards1.popleft()
            goal.popleft()
        elif cards2 and cards2[0] == goal[0]: # card2의 front와 일치하는 경우
            cards2.popleft()
            goal.popleft()
        else:
            break # 일치하는 원소를 찾지 못했으므로 종료
    return "Yes" if not goal else "No" # goal이 비었으면 "Yes" 아니면 "No"를 반환

solution 2)

def solution(cards1, cards2, goal):
    answer = ''
    cnt = 0
    j, k = 0, 0
    for i in range(len(goal)):
        if (j < len(cards1)) and (goal[i] == cards1[j]):
            cnt += 1
            j += 1
        elif (k < len(cards2)) and (goal[i] == cards2[k]):
            cnt += 1
            k += 1
        else:
            break
    print(cnt)
    if cnt == len(goal):
        answer = "Yes"
    else:
        answer = "No"
    
    return answer

solution 3)

import

 

(JavaScript)

solution 1)

- N: cards1과 cards2의 길이

- M: goal의 길이

- 해당 배열을 큐로 변환하는 것은 메모리 참조를 이용하므로 시간복잡도: O(1)

- 반복문에서 goal의 각 원소를 순회: O(M)

- 최종 시간 복잡도: O(M)

class Queue {
    items = [];
    front = 0;
    rear = 0;
    
    // 생성자를 이용해 편하게 초기화
    constructor(array) {
        this.items = array;
        this.rear = array.length;
    }
    
    push(item) {
        this.items.push(item);
        this.rear++;
    }
    
    pop() {
        return this.items[this.front++];
    }
    
    // front에 해당하는 값 반환
    first() {
        return this.items[this.front];
    }

    isEmpty() {
        return this.front === this.rear;
    }
}

function solution(cards1, cards2, goal) {
    // cards와 goal을 Queue로 변환
    cards1 = new Queue(cards1);
    cards2 = new Queue(cards2);
    goal = new Queue(goal);
    
    // goal의 문자열을 순차적으로 순회
    while (!goal.isEmpty()) {
        // card1의 front와 일치하는 경우
        if (!cards1.isEmpty() && cards1.first() === goal.first()) {
            cards1.pop();
            goal.pop();
        // card2의 front와 일치하는 경우
        } else if (!cards2.isEmpty() && cards2.first() === goal.first()) {
            cards2.pop();
            goal.pop();
        } else {
            break;
        }
    }
    
    return goal.isEmpty() ? "Yes" : "No"; // goal이 비었으면 “Yes” 아니면 “No”를 반환
}

solution 2)

import

solution 3)

import