백준 4889번 : 안정적인 문자열 - 파이썬 (python)

www.acmicpc.net/problem/4889

4889번: 안정적인 문자열

 

* 방법1 → X

아이디어: '{' 가 있으면 다음에 '}' 가 존재하는 것이 최소값이라고 가정한다.

0부터 시작해서 짝수 인덱스가 '{' 가 아니면 result 값을 1 증가시키고

홀수 인덱스가 '}' 가 아니면 result 값을 1 증가시키는 방법을 처음 생각했다.

 

⑴ }{ 인 경우

: 인덱스 0번의 경우 {가 아니므로 result+1

인덱스 1번의 경우 }가 아니므로 result+1

 

⑵ {}{}인 경우

: 인덱스 0번, 2번의 경우 { 이므로 result 값 증가 x

인덱스 1번, 3번의 경우 } 이므로 result 값 증가 x

 

⑶ {{{}인 경우

: 인덱스 0번, 2번의 경우 { 이므로 result 값 증가 x

인덱스 1번, 3번의 경우 1번이 { 이므로 result+1

 

⑷ {{}{}}인 경우

→ 안정적인 문자열이나 위와 같은 방법으로 풀이할 경우 0이 아닌 다른 값을 출력하게 됨

 

제출 시 런타임 에러가 발생

while True:
    s = input()
    data.append(s)
    if s[0] == '-':
        break

for i in range(len(data)-1):
    result = 0
    s = data[i]
    for x in range(0, len(s), 2):
        if s[x] != '{':
            result += 1
        if s[x+1] != '}':
            result += 1
    print("{}. {}".format(i+1, result))
    result = 0

 

* 방법2 → X

아이디어: '{' 의 개수를 세고 '}' 의 개수를 센다.

(총 문자열의 길이/2) - min('{'의 개수, '}'의 개수) 를 출력한다.

 

⑴ }{ 인 경우

'{' 의 개수: 1

'}'의 개수: 1

총 문자열의 길이 / 2: 1

{ 와 } 의 수와 동일한 경우 안정적인 문자열 조건을 만족하지 못함에도 0이 출력된다.

 

⑵ {}{}인 경우

'{' 의 개수: 2

'}'의 개수: 2

총 문자열의 길이 / 2: 2

→ 2 - 2 = 0

 

⑶ {{{}인 경우

'{' 의 개수: 3

'}'의 개수: 1

총 문자열의 길이 / 2: 2

→ 2 - 1 = 1

 

* 방법 3 → O

아이디어: 스택(stack)을 이용한다.

파이썬은 스택 자료구조는 따로 제공하지 않으므로 list를 이용하여 스택처럼 사용한다.

⑴ '{' 를 저장할 스택(리스트)을 만든다.

⑵ 입력받은 문자열을 탐색해서 스택이 비어있고 '}'를 만나면 count를 1 증가시키고 스택에 '{'를 push한다.

스택이 비어있지 않고 '}'를 만나면 스택에서 '{'를 pop한다.

'{'를 만나면 스택에 push한다.

⑶ (스택의 길이 / 2)를 count에 더하고, result 배열에 추가한다.

⑷ result 배열 출력

result = []

while True:
    stack = []
    count = 0
    s = input()
    if '-' in s:
        break
    for i in range(len(s)):
        if not stack and s[i] == '}':
            count += 1
            stack.append('{')
        elif stack and s[i] == '}':
            stack.pop()
        else:
            stack.append(s[i])
    count += len(stack)//2
    result.append(count)

for i in range(len(result)):
    print(i+1, '. ', result[i], sep='')

 

 

 

github.com/501501/baekjoon/blob/master/%EA%B7%B8%EB%A6%AC%EB%94%94/4889.py

501501/baekjoon