BOJ 백준 9012번 문제 <괄호> python, 알고리즘 문제 푸는 방법

오늘부터 메타버스 아카데미 1기를 함께했던 (내가 가장 애정하는 AI반!) 사람들과 알고리즘 문제풀기 스터디를 하기로 하여서

내가 푸는 것마다 블로그에 포스팅을 할 예정이다. 

 

블로그를 쓸 때마다 느끼는 거지만 머리말에도 존댓말을 하자니 쓰는 내가 재미가 없고(돈 벌려고 하는 느낌이랄까), 

그렇다고 설명하는 부분 마저 전부 반말로 하자니 뭔가 공적인 느낌이 안 들고 끄적인 일기마냥 신뢰성이 떨어지는 것 같은 기분이다.

(디시인사이드, 에타 같은 가볍게 떠드는 반말 커뮤니티 같달까)

 

그래서 선택한 방안으로 머리글, 마치는 글은 내가 하고 싶은 말을 하는 것이니 반말로 작성하고,

본문 내용은 깍듯한 '습니다' 체를 사용하기로 하였으니 이상하게 생각하지 말아주길 바란다.

 

오늘 푼 것은 실버4 난이도의 백준 9012 문제이고 python으로 풀었다.

 

https://www.acmicpc.net/problem/9012

9012번: 괄호

---

첫 포스팅을 시작하며

문제풀이 언어는 대부분 python으로 작성해볼 생각이며 간혹 c++을 이용할 수도 있습니다.

 

일단 저는 관련 성적이 안 좋지는 않지만 알고리즘 대회 수상경력도 없는 현재 평범한 컴퓨터공학 대학생임을 알립니다. 그럼에도 불구하고 후술한 방식으로 설명을 붙이는 이유는 알고리즘 문제 해설을 볼 때 정답을 읽으면서 스스로 문제를 어떻게 풀었는지 알아야해서 입니다.

물론 현업자들의 이야기를 들었을 때 다른 사람의 코드를 보고 해석하는 것도 꼭 필요한 능력이지만 코드를 보고 이해하기 어려운 사람들, 혹은 접근하는 능력을 키우고 싶은 사람들을 위해 이 글을 남깁니다.

 

저는 항상 문제를 풀 때, 문제에 대한 간단한 이해 (흐름)-> 입출력에 대한 이해 -> 다시 문제에 대한 세부 이해(설계) -> 구현의 과정으로 풉니다.

앞으로 포스팅도 여유가 되는 한 이러한 과정으로 진행하겠습니다.

 

추가로 첫번째 포스팅이니 만큼 문제 푸는 방법에 대한 설명들을 추가해놓았습니다.

문제에 대한 간단한 이해 (흐름)

- PS 중에서도 특별한 VPS에 대해 설명을 하면서 VPS가 성립되는 규칙에 대해 설명합니다.

 

- 겉을 둘러싸도 vps이며 접합이 성립한다는 것을 알 수 있습니다.

 

- 예시를 보며 간단히 규칙이 성립함을 이해합니다.

입출력에 대한 이해

- 테스트 입력데이터 개수가 정수 T개이므로 작성할 코드의 첫번째 줄이 나옵니다. T = int(input())

 

- 각 테스트 데이터에는 괄호 문자열이 한 줄로 주어지므로 for문과 안의 첫번째 줄의 코드도 지금 바로 작성이 가능합니다. ps = input()

 

- 예제 입력에 따라 출력이 어떻게 나오는지 확인합니다.

문제 예시를 통해서도 아직 규칙이 이해가 안 갔다면 한번 더 확인하고 이미 이해했을 시 어떻게 나오는지 확인 후 다음 단계로 넘어갑니다.

문제에 대한 세부 이해(설계)

제대로 시작하는 첫 문제풀이 포스팅이므로 제가 생각하는 문제 이해에 대해 적어보겠습니다.

문제에 대해 자세히 이해할 때는 문제 내용을 꼼꼼히 읽어보고 조건들을 나열합니다.

주로 다음과 같은 요소들이 있습니다. (어떻게 보면 게임과 똑같습니다.)

 

1. 주어진 것

2. 구하고자 하는 것

3. 규칙

 

여기서는 순서대로

1. 괄호 문자열(두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열),

2. VPS여부,

3. "VPS를 괄호 안에 넣어도 다시 VPS이며 VPS끼리 이어붙여도 VPS이다" 가 되겠습니다.

 

항상 구하고자 하는 것을 입력값을 이용해서 어떻게 구할지 먼저 생각해 봅니다.

 

- 가장 간단한 아이디어로 규칙에 따르면 VPS안에 VPS를 넣든 VPS를 더하든 최소 단위가 VPS이므로 결국 길이가 짝수입니다.

다른 말로 길이가 홀수라면 VPS가 아님을 알 수 있습니다.

하지만 이것만으로는 "))"등의 짝수이지만 VPS가 아닌 것이 해결이 안됩니다.

 

- 다른 방법을 생각해보겠습니다.

입력값의 형식만으론 방법이 잘 생각나지 않는다면, 예시나 규칙을 보고 컴퓨터가 아닌 자신의 머리는 어떻게 판단하는지 생각해보는 것이 도움이 됩니다.

"(())()"이 VPS라는 것을 판단할 때 먼저 기본 VPS인 2번째 '(' 3번째 ')' 문자열을 확인하고, (내부에 괄호를 신경쓰지 않은 채) 바로 다음 바깥 쪽 괄호가 VPS인지 확인하며, 다음으로 (왼쪽에 있는 괄호들을 신경쓰지 않은 채) 오른쪽에 VPS가 있는것을 확인합니다.

모두 확인이 끝나고 남는 문자 없이 짝이 맞으면 VPS입니다.

 

- 정리하자면 기본 VPS '()'를 찾고 계속 지워 나가다, 모두 확인이 끝났는데 남는 문자가 없다면 VPS이고, 이것이 VPS확인 알고리즘이라고 생각할 수 있습니다.

구현

컴퓨터로 구현을 하는 것은 문제를 푼 것과는 또 다른 느낌이 필요합니다.

컴퓨터 언어에 대한 숙련도, 수많은 구현 경험, 감각적인 코드 작성 실력에 따라 수준이 다르겠지만

큰 그림을 그리고 하나씩 차근 차근 작성하다 보면 결국 원하는 것에 도달할 수 있다고 생각합니다.

 

- 설계 부분에서 확인 알고리즘을 생각해 놓았으니 필요한 작업을 나열(큰 그림 그리기)합니다. 작은 단위 작업부터 작성하는 것이 조금 더 오래걸리지만 더 쉽습니다.

1. 주어진 문자열에서 기본 VPS를 찾아서 제거합니다.

2. 주어진 문자열에서 VPS를 모두 제거하고 난 최종 문자열을 도출합니다.

3. 최종 문자열이 비어있다면 YES, 남아있다면 NO를 출력합니다.

4. 가장 작은 단위를 먼저 작성하고 해결되었다면 for문을 이용해 테스트 케이스 여러번을 실행할 수 있도록 작성합니다.(이전 작업이 이후 테스트 케이스에 영향을 미치는 문제는 이런 방식을 사용하면 안됩니다.)

 

- 컴퓨터는 사람과 달리 문자 여러개를 보지 못하고 하나씩 보아야 하므로 ps내부 문자를 하나씩 도는 for문을 선언합니다. for c in ps:

 

- 문자를 하나씩 돌면서 VPS여부를 비교하자니 괄호의 쌍이므로 문자 하나만 가지고 판단할 수 없습니다. 현재 문자와 함께 이전 문자를 확인해서 ()인지 확인해야 하므로, '이전 문자를 저장할 변수'가 필요합니다.

하지만 어차피 최종 문자열을 저장할 변수도 필요하고 또 VPS확인 시 결국 이 최종 문자열의 끝인 '('를 지워주어야 하므로, 최종 문자들을 저장할 final_ps변수를 선언하고 이 변수의 끝 문자를 '이전 문자를 저장할 변수' 대용으로 사용합니다. (참고로 입력값으로 주어진 ps는 왠만하면 건드리지 않습니다. 이후 쓰일 수 있거나 for문을 돌 때 꼬일 수 있기 때문에 차라리 새로운 변수를 선언해서 copy하는 것이 좋습니다.)

 

- final_ps의 마지막 문자와 이번에 넣을 문자를 비교하면서(기본 VPS인지 확인을 위해) 하나씩 final_ps로 옮깁니다.

 

- final_ps의 마지막 문자를 비교해야 하는데 당연히 final_ps가 비어있으면 성립되지 않으므로 그냥 넣을 문자를 넣어주고 다음 문자로 넘어갑니다.

 

- final_ps의 마지막 문자와 이번에 넣을 문자가 각각 '(', ')'라면 기본 VPS이므로 final_ps의 끝을 잘라내고 이번에 넣을 문자는 추가하지 않습니다.(기본 VPS삭제와 같은 효과)

 

- 위 두 경우에 해당되지 않는다면 이번 문자를 final_ps에 더해줍니다.

 

- 마지막으로 if, else를 사용해서 final_ps가 비어있으면 YES, 아니면 NO를 출력합니다.

테스트 케이스만큼 for 문이 돌 수 있도록 작성합니다.

 

4번째 줄부터 6번째 줄까지는 홀 수 일 때 바로 NO를 출력하는 것인데, 실제 채점 시에 여러개의 테스트 케이스가 들어가므로 그 중에서 짧게 갈 수 있는 것은 줄이고자 넣어 보았습니다. 물론 테스트 케이스에 들어있는 입력값들의 길이가 모두 짝수일 경우에는 이 코드로 시간이 줄지 않고 오히려 하나의 if문과 그 안의 %때문에 시간을 잡아먹는 요인이 되므로 넣고 안 넣고는 선택의 문제인 것 같습니다.

T = int(input())
for i in range(T):
    ps = input()
    if len(ps) %2 != 0:
        print('NO')
        continue
    final_ps = ''
    for c in ps:
        if final_ps == '':
            final_ps = c
            continue
        # vps 발견 시 final_ps 잘라
        if (final_ps[-1] == '(') & (c == ')'):
            final_ps = final_ps[:-1]
        else :
            final_ps += c
    if len(final_ps) != 0:
        print('NO')
    else:
        print("YES")

 

---

첫 포스팅이라 힘이 들어가서 너무 길게 적었는데(거의 두시간) 앞으로는 최대한 각 단계 당 5줄이 안 넘어가도록 할 예정이다ㅠㅠ

 

이대로 꾸준히 해서 딱 100개 이상만 작성할 수 있었으면 좋겠다...