무브

오르비

아톰

내 태그

내 태그 설정

입시
학습
생활
클럽
직업·취업
Epioptimus
Centurion

✨컴공주✨ [1052682] · MS 2021 (수정됨) · 쪽지

2025-01-19 02:29:54
조회수 467

컴공 일기265

게시글 주소: https://orbi.kr/00071396715

https://school.programmers.co.kr/learn/courses/30/lessons/76502



프로그래머스 문제입니다.


스택을 이용해, 입력된 괄호끼리 짝을 다 맞출 수 있는지를 판단하는 겁니다.

‘짝’이라는 것을 어떻게 프로그래밍 언어로 표현할 것이냐를 묻고 있는데, 가장 일반적인 접근은 조건문이죠.


if(stack.top == ‘(‘ && input == ‘)’) // true

if(stack.top == ‘{ && input == ‘}’) // true

if(stack.top == ‘[‘ && input == ‘]’) // true


이런 식으로요.


실제로 제가 기술했던 코드에서도 조건문에 기반하여 짝을 확인하고 있습니다.


하지만, 조금 더 멋있게 푸는 방법이 있으니 그것은.. C++ STL(standard library)에서 지원하는

unordered_map 자료구조를 이용하는 겁니다.


맵은 일종의 순서쌍이라고 생각하면 되는데 굳이 조건절 반복해서 쓰지말고, 아예 통째로

unordered_map 자료구조에 (’{‘, ’}‘) (’[‘, ’]‘) (’(‘, ’)‘)를 미리 저장해 두고 확인만 해보면 된다는 논리죠.


제가 아래 기술한 풀이보다 unordered_map 자료구조를 이용한 풀이가

readability가 더 좋을 겁니다.


다만 뭐… 이 풀이도 나쁜 건 아니죠.



#include <iostream>

#include <string>

#include <stack>

using namespace std;


void answer(string& s, int& ans)

{

    stack<char> st;

    int size = s.size();


    for(int i=0; i<size; i++)

    {

        //열린 괄호만을 스택에 push

        if(s[i] == '(' || s[i] == '[' || s[i] == '{')

        {

            st.push(s[i]);

        }


        else

        {

            //스택이 비어있는 상태라면 짝을 맞출 수 없으므로 종료

            if(st.empty()) return;

  

            //괄호끼리 짝을 지을 수 있는지 확인

            if(s[i] == ']' && st.top() == '[') st.pop();

            else if(s[i] == ')' && st.top() == '(') st.pop();

            else if(s[i] == '}' && st.top() == '{') st.pop();

        }

    }   


    //문자열 끝까지 확인한 후 스택이 비어있다면 그 문자열은 괄호끼리 짝을 전부 맞출 수 있음

    if(st.empty()) ans++;

}

void left_rotation(string& s)

{

    int size = s.size();


    char first = s[0];

    for(int i=0; i< size-1; i++)

    {

        s[i] = s[i+1];

    }


    s[size-1] = first;

}

int solution(string s) 

{

    int size = s.size();

    int ans = 0;

    for(int i=0; i<size; i++)

    {

        answer(s, ans);

        left_rotation(s);

    }


    return ans;

}


0 XDK (+0)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

✨컴공주✨ [1052682]

쪽지 보내기

글쓰기
오르비 1373790번째 회원 가입
ddna
1,422,072 건의 게시물이
블록체인에 디지털 공증되었습니다.
901,751
497,321
22,267
574
159

오르비 캐스트

2026 수능D - 297

오르비 플레이

오르비 RARE

오르비 과외시장
Move
our corporate site
Orbi Class
on-line classes
Atom
educational books & resources
Gae9
humor and fun

© 2000-2025 Move Inc.

orbisoptimus (v17-7e2515)