사실 작성자님이 작성하신 코드가 스택의 원리를 이용한 것이고, 실제로 스택을 사용하는 것 보다 정수 하나로 푸는 게 더 효율적입니다.
스택의 원리를 이용해서 잘 푸신거예요.
9012번 - 괄호
이 풀이의 시간 복잡도는 O(N^2), 공간 복잡도는 O(1)입니다. 스택 풀이는 각각 O(N), O(N)입니다. (수정, 두 풀이의 공간 복잡도를 반대로 적었습니다. 스택이 O(N)입니다.)
사실 시간 복잡도가 O(N^2)이 된 건 구현 문제인데, 반복마다 strlen 함수를 호출해서 그렇습니다. 미리 길이를 변수에 저장하고 그 변수를 for문의 조건식에 넣으면 O(N)이 됩니다. 따라서 두 풀이는 공간 복잡도만 차이가 난다고 보시면 됩니다.
추가적으로, 이 문제에서는 괄호의 종류가 소괄호 하나이니 상관 없지만 https://www.acmicpc.net/proble... 이 문제처럼 괄호가 두 종류 이상이라면 이런 카운팅 풀이는 어렵습니다.
감사합니다 확실히 괄호 두개는 stack으로 풀어야되네오
댓글을 작성하려면 로그인해야 합니다.
adamjeon2003 1년 전 1
저는 괄호를 숫자로 변환해서 조건을 걸어 풀었는데 여기 단계가 스택이나 큐 관련 단계문제라서 이렇게 푸는 방식이 좀 맞는지 모르겠네요