파이썬 알고리즘 18일차
지금까지 풀었던 문제 중에서 가장 오래 걸리지 않았나... 뭔가 머리로 로직은 있는데 이걸 제대로 풀어내지 못하고... 계속 터미널이랑 충돌하고 해서 난리부르스 ^^...
9012: 괄호
1. 첫 번째 풀이: 실패
복잡하게 생각하지 말고 단순하게 가자! 는 호기 때문에... 장렬히 실패를 맛봤다. 근데 뭐 장렬히가 아니라 그냥 당연한 거임...
import sys
N = int(sys.stdin.readline())
right = '('
left = ')'
for _ in range(N):
input = sys.stdin.readline().strip()
right_cnt = input.count(right)
left_cnt = input.count(left)
if right_cnt != left_cnt:
print('NO')
else:
print('YES')
풀이를 살펴보면 right와 left 괄호의 갯수를 세어서 같으면 YES ~ 다르면 NO ~
정~말 단순하고도 바보 같은 생각이었다. 나는 약간 이런 문제 풀 때 반례를 제대로 생각하지 못하는 게 큰 문제인 듯하다. 이 풀이의 반례는
) (
이다. 네... 바보 인정합니다... 그래서 이렇게 풀지 말고 다르게 풀어야겠다고 생각해서 다양한 방법으로 접근해보았다.
2. 두 번째 풀이: 성공
정~말 다양한 방법으로 접근했는데 계속해서 YES가 떠야할 곳에 NO가... NO가 떠야할 곳에 YES가 떴다... ^^
그래도 작정하고 끝까지 푼 덕분에 영광의 '맞았습니다' 를 받아냈다! 하 뿌듯해 ;;;
import sys
N = int(sys.stdin.readline())
right = 0
left = 0
result = ''
for _ in range(N):
input = list(sys.stdin.readline().strip())
for i in range(len(input)):
if input[i] == '(':
right += 1
else:
left += 1
if left > right:
result = 'NO'
if (result == ''):
if (left == right):
result = 'YES'
else:
result = 'NO'
right, left = 0, 0
print(result)
result = ''
사실 중간에 주석이 하나 있었다. 바로 생각하다 포기한 일부...
for i in range(1,len(input)):
if (input[i-1]==right) and (input[i]==left):
input[i-1], input[i] = 'True', 'True'
이 풀이를 생각하게 된 건, ()의 VPS를 마주하게 되면 이를 리스트에서 빼버리는 것이었다. 이 과정을 반복하면 (()())에서 멀리 떨어진 ()도 만나게 될 것이므로 이렇게 풀면 백퍼 된다!!! 라는 생각이 머리를 지배했다. 그런데 이 풀이의 문제점은 for문의 range가 미리 정해지게 되어서 결국 index error가 난다는 것이었다. index error... 지긋지긋해... 그래서 이 방법 말고 새로운 방법으로 접근해야겠다라는 생각이 들었고, 그 결과가 바로 성공한 풀이!
성공한 풀이를 떠올리게 된 포인트는,
무슨 일이 있어도 ' ) '가 먼저 나오면 안된다!
라는 것이었다. 닫는 괄호가 먼저 나오게 되면, 무슨 짓을 해도 VPS가 될 수 없기 때문에... 이걸 지금에서야 알다니!
그래서 로직을 설명해보면,
- 각각 괄호를 세주는 left와 right 변수를 0으로 초기화 해준다.
- right과 left를 각각 세주고, 만약 left가 right보다 커진다!!! 하면 바로 result에 NO를 추가하도록 한다.
- 만약 다 돌았는데, result가 여전히 빈 문자열이다? 이 말은 right가 더 크거나 둘이 같다는 말이다.
- 그러면 둘이 개수가 같으면 VPS일 거고,
- 다르면 VPS가 아닐 것이다.
- 마지막으로 저장된 result 값을 출력한다!
추가로 만약 result가 빈 문자열인지 검사하는 부분이 없다면, 총 left와 right으로만 VPS를 따질 것이다. 즉 이 문자열이 '(())'이어도 '))(('이어도 똑같은 left와 right을 가지니 YES를 출력하게 되는 것이다. 결국 첫 번째 풀이와 다를 게 없다는 것... 그래서 NO라는 문자열이 지금 result에 할당되었는지 아닌지 확인이 필요한 것이다.
여기까지가 나의 풀이에 대한 설명이고, 이제 다른 풀이를 살펴보자!
3. 다른 풀이
a = int(input())
for i in range(a):
b = input()
s = list(b)
sum = 0
for i in s:
if i == '(':
sum += 1
elif i == ')':
sum -= 1
if sum < 0:
print('NO')
break
if sum > 0:
print('NO')
elif sum == 0:
print('YES')
(출처: https://pacific-ocean.tistory.com/70)
백준 파이썬 풀이로 유명하신 깨지고 부서져라님... 정말 똑똑하시다. 이걸 수학적으로 접근할 생각을 하다니... 우와라는 감탄 밖에 나오지 않군... 역시 더 발전해야겠어...
오늘도 신기한 알고리즘의 세계 끝!
Author And Source
이 문제에 관하여(파이썬 알고리즘 18일차), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@drizzle0171/파이썬-알고리즘-18일차저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)