목록안정적인 문자열 C++ (1)

1일1알

백준 4889번 안정적인 문자열 C++

괄호 관련 문제가 나오면 거의 대부분은 스택 자료구조로 푼다고 생각하면 된다. 우선 문자열에 있는 문자들을 스택에 차례로 넣기 시작한다. 차례로 넣다가 스택의 top이 '{'이고 다음으로 넣을 문자가 '}'라면 안정적인 문자열이기 때문에 pop을 해주고 문자를 넣지 않고 넘어간다. 이런 방식으로 스택을 다 채운 뒤 위에서 2개씩 빼가면서 만약 2개가 '{', '{' 이거나 '}', '}'이면 하나만 뒤집으면 안정적인 문자열이기 때문에 cnt를 1 증가시킨다. 만약 2개가 '}', '{' 라면 둘 다 뒤집어야 안정적인 문자열이기 때문에 cnt를 2 증가시킨다. 이런 방법으로 스택이 빌 때까지 반복하면 답을 구할 수 있다. #include #include #include #include #include #i..
알고리즘 2021. 11. 30. 11:58
이전 Prev 1 Next 다음