바킹독 0x05 문제7 / 백준 3015번 오아시스 재결합

근래에 사람들과 이래저래 대화를 나누며..

생각이 많아졌다.

세상이 좋아지고 바이브코딩이 핫한 요즘 it산업

하루에 사실 온전히 쏟는 시간은 아니긴 하지만

문제 하나 푸는데 한두 시간씩.. 사실 3시간도 걸리는 거 같기도 하고..

하지만.. 다음날 다 까먹는.. 씁쓸한 상황

코테용 알고리즘인데 나는 왜 이리 못하는가.....

뭔가 이도저도 못하는 느낌이 많이 든다.

 

취업의 문도 점점 두꺼워지는 요즈음 생각이 많다.

 

문제 풀기 싫어서 줄줄 써봤다.

 

다시.. 문제를 풀어봐야지

스택이라도 얼른 끝내봐야지..

---

 

사실 이 문제를 이해하는데 백만 년이 걸렸다.

 

요즘은 문제 이해하는 게 제일 어렵다는 생각이 든다.

일단 우리가 지금까지 그 스택의 패턴을 생각해 보면

2 다음 4면 애초에 2와 4는 되지만

2는 이제 그 뒤롤 못 보니까 없애고..

이렇게 넣을 거 넣고 뺄 거 빼면 되지 않을까?라는 생각이 들었다.

근데 문제는 이렇게 세는 게 맞나? 싶다.

 

또 의문인 건

이걸 pair로 써야 하는지 아닌지가 헷갈렸다..

또 하나....

범위가 곤란하다.

500,000개면.. 범위가.. 클 거 같기도 하다

결국 모든 숫자를 비교해야 할 수도 있으니까...

저번 문제처럼..

그러면 long long으로 가야겠.. 지? 싶었다.

 

 

오.. 지피티의 말로는 pair을 써야 하는 이유에 대해 알려주었다.

만약에 키가 같은 친구들이 오면 어떡할 거냐? 였다.

8 8 8 8 8 이면 8이 다섯 개여서 

8.1이랑 8.2 즉 일일이 다 비교해야 하는데 그것을 pair로 두 번째에 카운트해 주면

키가 같은 친구들을 한꺼번에 처리가 가능하게 된다. 

 

그래서 답도 long long 이여야 한다. 

 

가장 중요했고 헷갈렸던 건

마지막 줄이다.

 

이 식이 왜 필요할까?

그 식은 지피티가 이렇게 설명해 주었다.

 

스택에서 pop 할 땐, 스택에 있는 값보다 클 때이다.

top(). frist<= h 이기 때문에

반대로 top(). frist > h는 세지 못한다.

그런데 생각해 보면 first가 4이고 h에 2가 들어와도

이건 2 입장에서도 4 입장에서도 한 쌍이 될 수 있기 때문에

4가 먼저 들어와서 push 되어있을 테니

empty일리 없고

그래서 4 2는 한쌍인 것을 표현하기 위해 쓴 식이다.

 

그래서 ans++이고 그 뒤에 push를 하게 된다.

뭐 그뒤에 1이 나오면 또 empty검사해서 ++ 해주고
3이 나오면 2가 pop 되고, 기존에 있던 4가 있으니 empty가 아니어서 ans++ 하게 된다.

 

 

 

쉽지않은 문제를 끝냈다.

이제 스택 한문제 남았다. 얼른 끝내야겠다.

고생했다. 오늘 하루도 :)