https://school.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
입출력 예 설명
입출력 예 #1
다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.
x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?
0 "[](){}" O
1 "](){}[" X
2 "(){}[]" O
3 "){}[](" X
4 "{}[]()" O
5 "}[](){" X
올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.
입출력 예 #2
다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.
x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?
0 "}]()[{" X
1 "]()[{}" X
2 "()[{}]" O
3 ")[{}](" X
4 "[{}]()" O
5 "{}]()[" X
올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.
입출력 예 #3
s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.
입출력 예 #4
s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.
문제 해결 방법
문제가 스택 자료구조로 풀어야 할 문제임에도 불구하고, 스택으로 풀 생각을 구체적으로 하지않고 그냥 단순히 함수만 쓸 생각으로 코드를 짰다. 아니나 다를까 문제는 거진 통과인데 제일 마지막 테스트케이스에서 딱 멈췄다.
아~~ 테스트케이스를 추가하고 나서 어떻게 풀지 다시 생각해봤다.
추가한 테스트 케이스는 다음과 같다.
마지막 테스트 케이스를 풀기위해서는.. 아무리 생각해봐도 ... 스택적으로 문제를 풀 방법이 없다는 것을 깨달았다...
코드를 전면 수정했다. 기존 코드는 싹 지우고 다시 시작했다.
주어진 string을 순회 시키고,
각 string에서 한자 한자씩 읽는다.
(, {, [ 를 왼쪽 괄호라고 부르겠다. 배열 하나를 새로 만들고
왼쪽 괄호가 나오면 그 배열에 왼쪽 괄호를 PUSH 한다.
), }, ] 가 나오면 그 배열에서 POP한 것과 읽고 있는 글자가 같으면 넘어가고 카운트 한다
만약 글자가 같지 않으면 올바르지 않은 괄호 문자열이라고 판단한다.
코드 구현
개선된 코드
def solution(s):
left1 = []
left2 = []
left3 = []
check = [0]*3
pass1=0
pass2=0
for i in s:
if i == '(':
check[0]+=1
elif i == '[':
check[1]+=1
elif i == '{':
check[2]+=1
elif i ==')':
check[0]-=1
elif i == ']':
check[1]-=1
elif i == '}':
check[2]-=1
if check[0] ==0 and check[1]==0 and check[2]==0:
pass1=1
mylist=list(s)
if pass1==0:
return 0
else:
thisis = 0
for i in range(len(s)):
stakk = []
word = mylist.pop()
mylist.insert(0, word)
#print(mylist)
#print("---")
breakk=0
for i in mylist:
#print(i)
if i == ']':
try:
word = stakk.pop()
if word == '[':
continue
else:
breakk=1
break
except:
breakk=1
break
elif i == ')':
try:
word = stakk.pop()
if word == '(':
continue
else:
breakk=1
break
except:
breakk=1
break
elif i == '}':
try:
word = stakk.pop()
if word == '{':
continue
else:
breakk=1
break
except:
breakk=1
break
elif i == '[':
stakk.append('[')
elif i == '(':
stakk.append('(')
elif i == '{':
stakk.append('{')
if len(stakk)==0 and len(stakk)==0 and len(stakk)==0 and breakk==0:
thisis+=1
return thisis
기존 코드
def solution(s):
left = [0] * 3
check = [0]*3
pass1=0
pass2=0
for i in s:
if i == '(':
check[0]+=1
elif i == '[':
check[1]+=1
elif i == '{':
check[2]+=1
elif i ==')':
check[0]-=1
elif i == ']':
check[1]-=1
elif i == '}':
check[2]-=1
if check[0] ==0 and check[1]==0 and check[2]==0:
pass1=1
mylist=list(s)
if pass1==0:
return 0
else:
thisis = 0
for i in range(len(s)):
left = [0] * 3
word = mylist.pop()
mylist.insert(0, word)
#print(mylist)
#print("---")
for i in mylist:
#print(i)
if i == ']':
left[0]-=1
elif i == ')':
left[1]-=1
elif i == '}':
left[2]-=1
elif i == '[':
left[0]+=1
elif i == '(':
left[1]+=1
elif i == '{':
left[2]+=1
if left[0]<0 or left[1]<0 or left[2]<0:
break
#print('left[0]', left[0], 'left[1]', left[1], 'left[2]', left[2])
if left[0]>=0 and left[1]>=0 and left[2]>=0:
thisis+=1
return thisis
시간/공간 복잡도
제한 사항을 보아하니 O(N^2)으로 구현해도 되겠다 싶었다.
구현도 O(N^2)로 맞춰서 했다.
최적화 및 개선
이렇게 되면 사실상 개선된 코드에서 짝맞추는 코드는 없애도 될 것 같다.
어려웠던 점
생각하기,, 자료구조를 적용해서 생각하기,,
'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글
| [프로그래머스 lv2]주식가격 (0) | 2024.02.01 |
|---|---|
| [프로그래머스 lv2]짝지어 제거하기 (1) | 2024.01.31 |
| [프로그래머스 lv2]방문 길이 (1) | 2024.01.30 |
| [프로그래머스 lv1]실패율 (0) | 2024.01.29 |
| [프로그래머스 lv2]피로도 (1) | 2023.12.01 |