[PCCP] Lv2: 짝지어 제거하기(12973) 해설

문제

- 문제 링크: 짝지어 제거하기

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int solution(string s)
{
    int answer = 0;
    stack<char> stk;
    
    for (int i = 0; i < s.length(); i++){
        if (stk.empty() || stk.top() != s[i])
            stk.push(s[i]);            
        else
            stk.pop();
    }

    if (stk.empty())
        return 1;
    else
        return 0;
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

d

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: s의 길이

- 문자열의 모든 문자를 한 번씩 순회: O(N)

import java.util.Stack;

class Solution {
    public int solution(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            // 스택이 비어 있지 않고, 현재 문자와 스택의 맨 위 문자가 같으면
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop(); // 스택의 맨 위 문자 제거
            }
            else {
                stack.push(c); // 스택에 현재 문자 추가
            }
        }
        
        return stack.isEmpty() ? 1 : 0; // 스택이 비어 있으면 1, 그렇지 않으면 0 반환
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: s의 길이

- 문자열의 모든 문자를 한 번씩 순회: O(N)

def solution(s):
    stack = [] # 스택 초기화
    for c in s:
        if stack and stack[-1] == c: # 스택이 비어 있지 않고, 현재 문자와 스택의 맨 위 문자가 같으면
            stack.pop() # 스택의 맨 위 문자 제거
        else:
            stack.append(c) # 스택에 현재 문자 추가
    return int(not stack) # 스택이 비어 있으면 1, 그렇지 않으면 0 반환

solution 2)

def solution(s):
    answer = -1

    stack = []
    for i in s:
        stack.append(i)
        while True:
            if (len(stack) <= 1):
                break
            if (stack[-2] != stack[-1]):
                break
            else:
                stack.pop()
                stack.pop()
        
        
    if len(stack) == 0:
        answer = 1
    else:
        answer = 0
    return answer

solution 3)

import

 

(JavaScript)

solution 1)

- N: s의 길이

- 문자열의 모든 문자를 한 번씩 순회: O(N)

function solution(s) {
    const stack = []; // 스택 초기화
    
    for (const c of s) {
        // 스택이 비어 있지 않고, 현재 문자와 스택의 맨 위 문자가 같으면
        if (stack.length > 0 && stack[stack.length - 1] === c) {
            stack.pop(); // 스택의 맨 위 문자 제거
        } else {
            stack.push(c); // 스택에 현재 문자 추가
        }
    }
    
    // 스택이 비어있으면 1, 그렇지 않으면 0 반환
    return stack.length === 0 ? 1 : 0;
}

solution 2)

import

solution 3)

import