adamjeon2003   1년 전

저는 괄호를 숫자로 변환해서 조건을 걸어 풀었는데 여기 단계가 스택이나 큐 관련 단계문제라서 이렇게 푸는 방식이 좀 맞는지 모르겠네요

skuru   1년 전

사실 작성자님이 작성하신 코드가 스택의 원리를 이용한 것이고, 실제로 스택을 사용하는 것 보다 정수 하나로 푸는 게 더 효율적입니다.

스택의 원리를 이용해서 잘 푸신거예요.

not_strober   1년 전

이 풀이의 시간 복잡도는 O(N^2), 공간 복잡도는 O(1)입니다. 스택 풀이는 각각 O(N), O(N)입니다. (수정, 두 풀이의 공간 복잡도를 반대로 적었습니다. 스택이 O(N)입니다.)

사실 시간 복잡도가 O(N^2)이 된 건 구현 문제인데, 반복마다 strlen 함수를 호출해서 그렇습니다. 미리 길이를 변수에 저장하고 그 변수를 for문의 조건식에 넣으면 O(N)이 됩니다. 따라서 두 풀이는 공간 복잡도만 차이가 난다고 보시면 됩니다.

추가적으로, 이 문제에서는 괄호의 종류가 소괄호 하나이니 상관 없지만 https://www.acmicpc.net/proble... 이 문제처럼 괄호가 두 종류 이상이라면 이런 카운팅 풀이는 어렵습니다.

adamjeon2003   1년 전

감사합니다 확실히 괄호 두개는 stack으로 풀어야되네오

iygav1238   1년 전

괄호 문제를 스택으로 푸는 것이 대표적이긴 하지만 작성자님의 방식처럼 (를 1로, )를 -1로(혹은 그 반대) 치환하고 누적합을 이용해 판별하는 것도 잘 알려진 방법입니다(원리는 비슷하지만). 4949번처럼 괄호 종류가 여러개여도 (는 )와, [는 ]랑만 매칭이 되는 형태라면 같은 방식으로 가능합니다.

댓글을 작성하려면 로그인해야 합니다.