티스토리 뷰
https://programmers.co.kr/learn/courses/30/lessons/76502
코딩테스트 연습 - 괄호 회전하기
programmers.co.kr
문제 설명
다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.
- (), [], {} 는 모두 올바른 괄호 문자열입니다.
- 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
- 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- s의 길이는 1 이상 1,000 이하입니다.
입출력 예
s | result |
"[](){}" | 3 |
"}]()[{" | 2 |
"[)(]" | 0 |
"}}}" | 0 |
문제 풀이
괄호 짝을 맞추는 문제는 스택을 이용하여 구현하면 해결할 수 있다.
짝을 판단해주는 check 함수를 만들고 문자열을 순서대로 검사하며 여는 괄호( '(' ,'{', '[' )인 경우에 스택에 넣는다.
우선 체크함수를 검사하지 않는 조건을 찾아보면 문자열의 길이가 홀수인 경우에는 절대로 짝을 맞출 수 없다.
체크함수를 호출하기 전 입력된 문자열의 길이가 홀수면 바로 리턴한다.
체크함수에서 문자열을 검사하며 닫는 괄호가 나온 경우를 생각해보자
1. 스택이 비어 있는 경우 -> 짝을 맞출 수 없음
2. 스택에 괄호가 있는 경우 -> 스택에서 pop 시켜 닫는 괄호와 상응하는 여는 괄호인지 검사
1,2 번의 경우를 나눠서 검사하여 문자열의 괄호가 짝을 이룬다면 True를 리턴하고, 짝을 이루지 못하면 False를 리턴.
문자열을 왼쪽으로 한 칸씩 미는 코드는 다양한 방법이 있지만 문제를 풀때 바로 생각했던
리스트의 첫 번째 원소 pop -> 다시 리스트의 마지막에 append 방식을 이용했다.
def check(li):
stack = []
for c in li:
if c == '(' or c == '{' or c == '[': # 여는 괄호인 경우 스택에 넣음
stack.append(c)
else:
if len(stack) == 0:
return False
compare_c = stack.pop()
if c == ']' and compare_c != '[':
return False
elif c == ')' and compare_c != '(':
return False
elif c == '}' and compare_c != '{':
return False
return True
def solution(s):
answer = 0
if len(s) % 2 == 1:
return answer
s = list(s)
if check(s): # 오리지널(원래) 문자 처음으로 검사
answer += 1
for _ in range(len(s) - 1): # 왼쪽으로 한 칸씩 밀어낸 문자 검사
word = s.pop(0)
s.append(word)
if check(s):
answer += 1
return answer
'알고리즘' 카테고리의 다른 글
[프로그래머스] 삼각 달팽이 - 파이썬 (0) | 2022.02.08 |
---|---|
[프로그래머스] 2개 이하로 다른 비트 - 파이썬 (0) | 2022.02.08 |
[프로그래머스] 오픈채팅방 - 파이썬 (0) | 2022.01.25 |
[백준] 6609 : 로또 - Python(파이썬) (0) | 2021.08.21 |
[백준] 1780 : 종이의 개수 - Python(파이썬) (2) | 2021.08.11 |
- Total
- Today
- Yesterday
- 알림개선기
- 피움
- 네트워크
- jpa
- 알림기능개선기
- ZNS
- Spring
- 3차 데모데이
- 런칭 페스티벌
- ZNS SSD
- dm-zoned 코드분석
- 팀프로젝트
- 환경 별 로깅 전략 분리
- 우테코 회고
- java
- dm-zoned
- 스프링 Logback
- 5주차 회고
- 스프링 부트
- 우테코
- 스프링MVC
- 스프링 프레임워크
- 피움 6주차 회고
- 2차 데모데이
- 프로젝트
- CI/CD
- 백준
- 8주차 회고
- 회고
- 파이썬
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |