반응형
밑의 링크는 프로그래머스에서의 문제 링크입니다.
코딩테스트 연습 - 괄호 회전하기
programmers.co.kr
주의해야 할 점
문제에서는 올바른 괄호 문자열이 되게 하는 x의 개수라고 표현했는데
제가 생각하기엔 조금 헷갈리게 만들 수도 있다는 표현이라고 생각합니다.
그냥 한 번씩 회전하면서 올바른 괄호 문자열의 개수를 세면 됩니다.
올바른 괄호 문자열의 조건을 잘 읽어봐야 합니다.
대부분의 테스트 케이스들은 통과하는데 몇 개의 테스트를 통과하지 못한다면
아마 올바른 괄호 문자열의 조건을 제대로 이해하지 못하고 짠 코드일 것입니다.
저도 제대로 이해하지 못한 상태로 코드를 짜서 틀린 결과를 계속 봤었습니다.
생각한 풀이 과정
- 올바른 괄호 문자열의 개수를 저장할 변수를 하나 만들어줍니다.
- 문자열 s를 왼쪽으로 한 번씩 회전해봅니다.
- 올바른 괄호 문자열인지를 판단하기 위한 스택을 하나 만들어줍니다.
- 왼쪽으로 회전한 문자열 s에서 괄호 하나씩 반복해봅니다.
- 현재 괄호가 '(', '[', '{' 중 하나라면 스택에 현재 괄호를 넣어줍니다.
- 현재 괄호가 ')', ']', '}' 중 하나라면 스택에서 맨 끝에 있는 괄호가 무엇인지 판단해봅니다. 만약 스택이 비어 있다면 올바른 괄호 문자열이 아닙니다.
- ')'라면 스택 맨 끝의 괄호가 '(', ']'라면 스택 맨 끝의 괄호가' '[', '}'라면 스택 맨 끝의 괄호가 '{'여야 올바른 괄호 문자열이 될 수 있습니다. 아니라면 올바른 괄호 문자열이 아닙니다.
- 왼쪽으로 회전한 현재 문자열을 하나씩 반복해서 올바른 괄호 문자열 조건에 만족한다면 현재 문자열은 올바른 괄호 문자열이 맞습니다.
- 문자열을 다 읽어봤다면 또 한 번 왼쪽으로 회전시키고 과정 3 ~ 과정 8까지 반복해봅니다.
제출한 파이썬 코드
# 대괄호, 중괄호, 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다.
def solution(s):
# 올바른 괄호 문자열이 되게 하는 x의 개수를 저장할 변수를 선언합니다.
# x의 개수는 올바른 괄호 문자열의 개수입니다.
correct_brace_cnt = 0
# 문자열 s의 길이를 저장하는 변수를 선언합니다.
s_len = len(s)
# 문자열 s의 길이만큼 왼쪽으로 x칸 회전합니다.
for x_cnt in range(s_len):
# 현재 x칸 회전한 문자열 s가 올바른 괄호 문자열인지 아닌지를 구별하기 위한 괄호 스택을 만들어줍니다.
brace_stack = []
# 현재 x칸 회전한 문자열 s가 올바른 괄호 문자열인지 아닌지를 저장할 변수를 선언합니다.
# 처음에는 올바른 괄호 문자열이 맞다는 뜻인 True로 초기화합니다.
is_correct_brace = True
# 현재 x칸 회전한 문자열 s에서 한 문자씩 반복해봅니다.
for idx in range(s_len):
# 현재 괄호 문자를 저장하는 변수를 선언합니다.
cur_brace = s[idx]
# 현재 괄호 문자가 '(', '[', '{' 중 하나라면
if cur_brace in ['(', '[', '{']:
# brace_stack에 현재 괄호 문자를 넣어줍니다.
brace_stack.append(cur_brace)
# 현재 괄호 문자가 ')'라면
elif cur_brace == ')':
# try문을 시도해봅니다.
try:
# brace_stack의 맨 끝 문자가 '('라면
if brace_stack[-1] == '(':
# 맨 끝 문자인 '('를 빼냅니다.
brace_stack.pop()
# 예외가 발생한다면
except:
# 현재 x칸 회전한 문자열 s는 올바른 괄호 문자열이 아니므로
# is_correct_brace에 False를 저장합니다.
is_correct_brace = False
# 올바른 괄호 문자열이 아니라고 확정되었으므로 반복문을 탈출합니다.
break
# 현재 괄호 문자가 ']'라면
elif cur_brace == ']':
# try문을 시도해봅니다.
try:
# brace_stack의 맨 끝 문자가 '['라면
if brace_stack[-1] == '[':
# 맨 끝 문자인 '['를 빼냅니다.
brace_stack.pop()
# 예외가 발생한다면
except:
# 현재 x칸 회전한 문자열 s는 올바른 괄호 문자열이 아니므로
# is_correct_brace에 False를 저장합니다.
is_correct_brace = False
# 올바른 괄호 문자열이 아니라고 확정되었으므로 반복문을 탈출합니다.
break
# 현재 괄호 문자가 '}'라면
elif cur_brace == '}':
# try문을 시도해봅니다.
try:
# brace_stack의 맨 끝 문자가 '{'라면
if brace_stack[-1] == '{':
# 맨 끝 문자인 '{'를 빼냅니다.
brace_stack.pop()
# 예외가 발생한다면
except:
# 현재 x칸 회전한 문자열 s는 올바른 괄호 문자열이 아니므로
# is_correct_brace에 False를 저장합니다.
is_correct_brace = False
# 올바른 괄호 문자열이 아니라고 확정되었으므로 반복문을 탈출합니다.
break
# is_correct_brace가 True이고, brace_stack이 빈 리스트라면
if is_correct_brace and brace_stack == []:
# 현재 x칸 회전한 문자열 s는 올바른 괄호 문자열이므로 correct_brace_cnt에 1을 더해줍니다.
correct_brace_cnt += 1
# 문자열 s를 왼쪽으로 1칸 회전해줍니다.
s = s[1:] + s[0]
# 문자열 s를 왼쪽으로 x칸만큼 회전하면서 생긴 올바른 괄호 문자열의 개수를 반환합니다.
return correct_brace_cnt
제출 결과
느낀 점
처음에 풀었을 때는 테스트 14번을 계속 통과하지 못해서 뭐가 문제인지 몰랐는데,
문제를 다시 읽어보니 아예 잘못 짠 코드였습니다.
실제 코딩 테스트에서 이번 문제 사태와 같은 경험을 하게 된다면 백퍼센트로 탈락하겠더라고요...
※ 궁금한 부분, 이상한 점 및 오타는 댓글에 부탁드립니다.
※ 더 효율적이고 빠른 정답을 환영합니다.
반응형
댓글