★백준 10799번 쇠막대기 C#으로 문제 풀어보기★

안녕하세요 박민성입니다.

 

오늘은 백준 10799번 쇠막대기를 풀어 보겠습니다.

문제를 보면

입력은 괄호들만으로 입력이 들어옵니다. 괄호 문자의 개수는 최대 100,000입니다.

 

출력은 괄호대로 했을 때 쇠막대기의 개수를 출력해 줍니다.

 

저는 처음에 문제를 보고 이해를 못 하고 있다가 천천히 보며 이해를 하기 위해 노력했습니다.

()은 이렇게 괄호가 열리고 바로 닫히면 레이저입니다. 레이저는 괄호를 잘라서 두 동강 낼 수 있습니다.

만약 괄호가 열리고 ( 바로 닫히지 않는다면 그건 쇠막대기가 됩니다. )은 쇠막대기의 마지막을 의미합니다.

 

모든 문제 기믹? 들을 이해했으니 입력을 생각? 예제를 보면서 혼자서 방식을 적용해서 예제 출력을 보지 않고

적용시켜 봅니다. 

 

( ) ( ( ( ( ) ( ) ) ( ( ) ) ( ) ) ) ( ( ) ) 예제 입력 1처럼 들어왔을 때 생각을 해보겠습니다.

일단 ( )은 레이저이지만 아직 쇠막대기가 없어서 아직 쇠막대기는 0개입니다.

그리고 ( ( ( ( ) ( )을 보면서 문제에 특성을 생각해 봤습니다. 쇠막대기가 여러 개 들어왔지만 문제에서 쇠막대기 위에 아래보다 작은 쇠막대기를 올릴 수 없다는 걸 보고 ) 이 닫혔을 때에는 나중에 들어온 쇠막대기의 끝인걸 알았습니다. 그래서 저는 스택을 사용하기로 합니다.

다시 돌아와 ( ( ( ( ) ( ) 은 쇠막대기 3개 주어졌을 때 두 번 레이저를 쏘니 일단 3+3을 해주었습니다 원래는 3을 더 더해주어야 한다고 생각하지만 그 남은 것들은 끝났을 때, 입력상 끝났을 때 더해줄 거라 잘린 만큼만 더해주었습니다.

그리고 ) 왔으니 쇠막대기 1개를 더해줍니다. 현재까지 쇠막대기를 7 더해주었습니다.

그리고 ( ( ) ) 입력대로 쇠막대기 한 개를 원래 현재 가지고 있는 쇠막대기 2개에 더해주어 3개가 됩니다.

그리고 레이저를 쏘니 쇠막대기가 3니깐 +3이고 쇠막대기 한 개가 끝나니 +1 해주어 현재까지 쇠막대기 11개입니다.

그리고 ( ) ) ) 은 레이저를 쇠막대기가 2개인 상태로 쏴주니 +2 쇠막대기 두 개가 끝나니 +2를 해주면 현재까지 쇠막대기 15개입니다.

마지막으로 ( ( ) ) 은 쇠막대기 한 개를 추가해 주고 레이저로 자르고 끝내니 +1,+1 총 쇠막대기 17개입니다.

 

이러한 생각을 메모장에서 끄적여 보면서 수많은 시행착오 끝에 찾아냈습니다.

시행착오 중 ) 쇠막대기가 끝났을 때 스택에서 빼주기만 하고 쇠막대기가 추가되는 줄 까먹고 결과가 13개가 나올 때도 있었습니다.

 

이렇게 메모장에서 알고리즘을 생각을 정리하고 입력 예제를 넣어서 출력 예제처럼 나오는 걸 검증했으니 

코드를 짜보도록 하겠습니다. 

 

일단 쇠막대기( '('나 ')' 이런 문자 )를 담기 위한 스택을 생성시켜 줍니다.

그리고 문자열 입력을 a에 담아줍니다. 그리고 제 방식은 자른 걸 더해주는 방식이기 때문에 

자를 때마다 쇠막대기를 더해줄 num이라는 변수도 선언받습니다

그리고 이렇게 a문자열 길이만큼 for문을 돌려줍니다. 입력은 (이랑 )만 오니 이 두 가지의 경우의 수만 추적하면 됩니다.

만약 (이가 왔을 때 바로 다음이 )이면 ( ) 레이저입니다. 그렇기 때문에 스택에 있는 쇠막대기의 수만큼 num에 더해줍니다.

그리고 만약에 바로 )이가 오지 않는다면 레이저가 아니고 쇠막대기이니 스택에 쇠막대기 (를 넣어줍니다.

그리고 만약 (이가 아니고 )이면 쇠막대기가 끝난 것이니 쇠막대기를 num에 한번 더 추가해 주고 스택에서 쇠막대기를 빼줍니다.

이러고 출력하면 끝인 줄 알았지만

이러면 문제가 레이저로 사용된 )이가 다음 i번째에 들어와 스택에서 쇠막대기를 뺄 수도 있습니다. 왜냐하면 예외처리를 해주지 않았기 때문이죠 그래서 레이저 한번 오고 나서 )이 문자는 레이저에 사용된 녀석이니 무시하고 다음 i번째를 검사하기 위해서

자료형 불리언으로 laser이라는 변수를 선언해 줍니다.

그리고 여기서 레이저면 레이저를 true로 바꿔주고

전 i번째가 레이저였다면 레이저를 false로 바꿔주고 continue로 그 i번째 )를 검사 안 하고 넘어갑니다.

이것이 전체 코드입니다. 

 

이렇게 백준에 제출하였더니

정답이었습니다.