[문제 원본]코딩테스트 연습 - 짝지어 제거하기 | 프로그래머스 (programmers.co.kr)

괄호 문제, 짝 짓는 문제 등은 보통 Stack으로 풀릴 때가 많습니다.

같은 문자가 반복되는 짝을 계속하여 제거하였을 때, 모두 제거가 되는지 판단하는 문제입니다.
아래와 같은 논리로 접근하시면 됩니다.

• 문자열이 홀수인 경우 모두 짝을 지어도 1개는 꼭 남기때문에 바로 0을 return
• 짝을 판단할 stack 생성 (STL의 stack 컨테이너 사용)
• 문자열의 처음부터 iterator를 증가시켜가며 진행합니다.

  Stack이 비었을 경우

• Stack이 비었을 경우 현재 가리키고 있는 문자를 push

Stack이 비어있지 않은 경우

• Stack의 top과 비교하였을 때 일치하면 pop으로 제거 (짝 지어짐)
• 일치하지 않으면 push로 stack에 담기

문자열의 길이만큼 Iteration 후 stack이 비어있는지를 return하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int solution(string s) {
    if (s.size() % 2)
        return 0;

    stack<char> st;

    for (auto it = s.begin(); it != s.end(); ++it) {
        if (st.empty() || st.top() != *it)
            st.push(*it);
        else
            st.pop();
    }
    return st.empty();
}

[문제 원본] https://programmers.co.kr/learn/courses/30/lessons/12985

간단한 규칙 찾기 및 구현 문제입니다.

A 참가자와 B 참가자가 토너먼트에 참가했을때, 만나게 되는 round의 값을 리턴해주면 되는 문제입니다.

이겼을 때 다음 번호의 규칙성을 파악하면 쉽게 풀립니다.

• 1번의 참가자가 이겼을 경우) 다음 번호는 1번
• 4번의 참가자가 이겼을 경우) 다음 번호는 2번
• 3번의 참가자가 이겼을 경우) 다음 번호는 2번
• 15번의 참가자가 이겼을 경우) 다음 번호는 8번
• 16번의 참가자가 이겼을 경우) 다음 번호는 8번

-> (1) 나누기 2를 한 다음 (2) 올림을 하는 규칙임을 파악할 수 있습니다.
loop를 돌면서 a, b가 같은 번호일 때의 round를 return하면 됩니다.

1
2
3
4
5
6
7
8
9
10

#include <iostream>

int solution(int n, int a, int b) {
    for (int round = 1; round < 20; round++) {
        a = a / 2 + a % 2;
        b = b / 2 + b % 2;
        if (a == b)
            return round;
    }
}