1-M

내 풀이(http://boj.kr/1eaa089707114eecab1fb750e1a384a8) - 틀림

공유 소스 보기

---

1-M

1-M, 백준 3986 좋은 단어 문제를 풀어 보도록 할게요.

일단 제가 예시를 보면서 설명을 해볼게요. 일단 선끼리 교차하지 않아야 되고 짝지을 수 있는 같은 단어가 좋은 단어죠.

예를 들어서 AABB가 이렇게 나왔어요.

이거는 좋은 단어일까요? 좋은 단어죠.

그런데 ABAB 이건 좋은 단어일까요? 좋은 단어가 아닙니다. 선끼리 교차하니까요.

자, 그럼 어떻게 해야 될까?

항상 문제를 볼 때, 이런 식으로 이제 어떤 문자열이 왔을 때 생각이 안 난다. '아, 선생님 저는 도저히 풀 생각이 나지 않습니다' 라고 하면은 어떻게 하면 되냐?

주어진 문자열을 뒤집어 보거나, 문자열 하나를 더 붙여 보거나, 아니면 문자열을 90도로 회전해 보거나. 해봐야합니다.

자, 이거를 여러분 기억해 주세요.

지금 문제에서 ABAB 이렇게 되어있는 거잖아요.

이걸 보고 얘가 좋은 단어인지 좋은 단어가 아닌지를 구별을 하는 문제죠. 근데 이렇게 얼핏 봐서는 어떻게 풀어야 될지 모르겠다라는 거예요.

여러분 기억하세요. 문제를 봤을 때, 그리고 예시를 봤을 때 좀 뭔가 이해가 안 된다. 그러면 도식화를 시킬 생각, 그림으로 그릴 생각을 하셔야 돼요.

그때 이제 어떻게 하면 되냐?

주어진 문자열을 뒤집어 보거나, 그러니까 문자열을 90도 회전해 보거나 뒤집어봐요. 또는 한 번 이렇게 붙여봐요. 이런 식으로 시도를 한번 해보세요.

저는 이게 좀 맘에 드는데 좋은 단어를 예시로 한번 들어볼게요.

ABBA일 때는 얘가 이렇게 아래부터 쌓아지는 거잖아요. 그런데 생각해보면, BB는 폭발을 하는게 아닌가? 그럼 이제 위에 있던 A가 뚝 떨어지면서 AA가 만나서 폭발을 하면 되지 않나? 라는 아이디어를 가지고 푸시게 되는 거예요.

다시 정리하자면, 문제를 보시고 이해가 안 되면 일단 예시를 당연히 이해를 하셔야 되고, 그 다음에 이런 식으로 그림을 그려가면서 그대로 한번 해보고 하나를 더 붙여보고, 90도로 회전해보고, 반대로 뒤집어보고 이런 거를 하면서 어떻게 풀지 아이디어를 잡아가셔야 되는 거예요.

자 그러면 지금 보시는 것처럼,

'어 이거 폭발이 아닌가?' 라고 들어갈 수가 있는 거죠.

이런 식으로 폭발을 해서 A가 뚝 떨어져서 사라지는 로직이 필요하다라는 거죠.

생각해보면 이런거예요.

어떤 자료구조인진 아직 모르겠지만, A가 들어와요.

그 다음에 B가 들어오고, B가 또 들어와요. 그 때 폭발해야 되는 겁니다.

그러니까 가장 윗 부분에 있는 것과 들어오는 문자가 같을 때 폭발, pop()을 시켜버리는 거죠.

그런 다음에 A가 또 들어오면

또 폭발이 일어나겠네요.

그럼 이 자료구조가 뭔지는 모르겠지만, 가장 뒤에 있는 어떤 요소와 비교를 해서 폭발을 하겠네요. 그렇게 해가지고 결국에는 이 자료구조의 size가 0이면, 좋은 단어겠네요. 그러니까 폭발이 일어나서 다 소거가 돼버린 상황인거죠.

반대로 ABAB 들어와서 폭발이 안 일어나면, size가 있을 거고 그럼 좋은 단어가 아니겠죠.

자, 그럼 여기서 제가 어떻게 했어요? 지금 보시면 가장 뒤에 부분만 참조를 한 것을 볼 수가 있죠.

자 가장 뒤에 부분만 참조할 수 있는거 뭐에요? 스택이죠.

스택은 뭐에요? 접시 쌓기를 생각하라고 했죠.

접시는 위에서부터 쌓이고, 위에만 참조가 가능하다. 즉 가장 뒤에 거만 참조가 가능하다는 겁니다.

잠깐 짚고 넘어갈게요.

Queue는 뭐에요? 가장 앞에 있는 녀석만 참조가 가능하다.

그래서 가장 앞에 거는 Queue, 가장 뒤에 거는 스택입니다. 그래서 이 문제는 스택을 사용하는 문제인 거고요.

자 그럼 이제 이걸 어떻게 해야 되냐?

말 그대로 그냥 이 도식화를 그대로 코드로 옮기기만 하시면 돼요.

---

자 코드입니다.

문자열을 받아서 스택을 정의를 합니다.

자 문자열을 받을 때마다 매번 스택을 정의를 하셔야 돼요. 왜냐면 매번 빈 스택이 필요하니까요.

일단 이 부분 볼까요?

지금 이런 식으로 stack의 top()과 들어오는 문자를 비교를 해야 되는데, 한 가지 팁을 드리자면

stack.top() 이나 queue.front()처럼 이렇게 참조를 할 때, 항상 size()를 함께 체크하셔야 돼요.

이런 식으로 값이 먼저 있는지 체크를 하고, 참조를 하셔야 합니다.

그렇게 해야 reference 에러가 나지 않습니다. 그러니까 값이 없는데 이걸 참조하려고 하면 참조 에러가 발생하게 된다라는 거죠.

자 그렇게 해서 만약에 top()이 같으면 스택에 pop()을 하고, 그게 아니라면 그냥 push를 하는 거죠.

그리고 모든 문자를 다 끝낸 다음에 stack의 size가 0이면, ret++;을 해서 좋은 단어의 개수를 세는 겁니다.

자 마지막 팁 나갑니다. 여러분 이거 꼭 기억하세요.

문제에서 만약에 짝짓기다, 폭발이다 라는 단어가 있으면 스택을 한번 생각하세요.

'어? 짝짓기, 폭발? 스택을 사용해야 되지 않을까?' 라고 생각하는 게 중요합니다.