백준 3015번 오아시스 재결합 c++

첫 플래티넘 문제이다. 생각보다 간단한데? 하고풀었을때 예외케이스들이 계속 생겼다. 역쉬플래

 

이 문제는 서로눈을 볼 수 있는가. 즉 둘 사이에 둘보다 큰 사람이 있으면 안된다!
이말은 키가 1, 2, 3이면 1 과 3은 서로 못본다. 2는 3보다는 작지만 1보다는 크기 때문!

시간제한이 1초이고 n이 최대 500,000 이기에 O(n^2)면 시간초과다.

 

테스트 케이스를 보면서 이해해보자.

 

 

1)  2가 들어오고 4가 들어오면 일단 2-4 쌍이 생긴다.  (누적 1쌍) 2 4

2)  그 뒤에 1이 쌓이면 4-1 쌍이 추가로 생긴다. (누적 2쌍) 2 4 1

3)  그뒤에 2가 쌓이면 1-2, 4-2 두 쌍이 생긴다 (누적 4쌍) 2 4 1 2

여기까지만 봤을때 쌍이 생기는 조건을 보면 

새로운 데이터보다 큰 곳 까지 계속 쌍을 이룬다. 3) 을 보면새로운 2 는 2보다 큰 4가 등장할때까지 기존등장녀석들과 다 쌍을 이룬다. (2-1, 2-4) 다만 4 보다 더 이전것은 4에 막혀서더이상 볼 수 없다.

그렇다면

 

스택을 이용해보자.

새로운 데이터는 그냥 쌓으면 된다.

다만 새로운데이터가 쌓일때 그것보다 작은것들은 제거해주면 된다. 그리고 제거를 할 때 서로 바라보는 카운트를 세주면 된다. 새로운 데이터보다 큰것이 최상단에 있으면 그냥 쌓으면서 서로 바라보는 횟수만 추가해주면 된다.

 

일단 여기서 while문 조건을 보게되면 스택이 비어있지않고 현재값보다 스택최상단값이 작을때 s.pop()을 한다고 되어있다. 그리고 이때 s.top().Y를 토탈에 추가해준다(서ㅏ로 바라본 횟수 추가) 그런데 top.Y에는 기본적으로 1이 들어간다. 그니깐 바라본 횟수 1 증가인 셈이다. 

그리고 다 팝 하고나면 푸시를 해주는데 pair의 Y쪽에 푸시를 해준다(depth는 잠시 무시).

 

 

이제 또 중요한걸 고려해야한다. 바로 키가 같을때!!

4 2 2 2 이렇게 서게 되면 서로가 서로를 전부 볼 수 있다.

그러면 스택에 쌓을때 그냥 쌓는가?

그럼안된다. 

 

예시 

5 5 5 5 5 5 

 

a) 5부터 쌓자. 5를 넣고 그후에 5를 넣고 계속해서 5를 6번넣고 넣을때마다 카운트를세면 총 5가 된다. 실상은15이다.

b) 자 그럼 쌓을때 pop을 해야하는가? 그것또한 하니다.

5를 넣고 제거하고 넣고 제거하고 넣고,,,

 

여기서 동일높이의 것들이 등장해도 다른것들과 같게 ㅊ처리할 수 있게 할 수 있다.

 

바로 푸씨할때 pair로 한축에 1을 default로 두는것!

 

그럼 b) 방식으로 하되 pop할때마다 새로 넣는것에 pair한축에 이전것의 값을 더해주게 되는것. pop할때마다 카운트가 1이 증가하는게 아니라 pair의 한 축의 값이 증가하는것.

 

내가 아직 소양이 부족해서 초등학생도 이해하도록 글을 쓰지는 못했다..

 

 

pair로 x자리는 높이, Y자리는 pop을 했을때 증가되어야 하는 카운트 수 를 저장한다.

 

코드를 보면 일단 12번째에서 pair의 first에는 타입을 long long int로 두었다. 이는 문제조건을 보면 이렇게해야함을알 수 있다.

자 이제 second위치에서는 int 를 두었다. 얘의 역할이 무엇이냐? 바로 pop했을때 올려야 할 카운트 개수이다.

(2~3번줄을 통해 first ->X,  second -> Y)

 

일단 n에 대한 반복마다 depth를 0으로 초기화한다.

스택이 비어있으면 당연히 pop할게없고, 스택최상단이 현재 temp보다 크면 그것도 pop할 이유가 없다.(while문 조건에 대한 설명)

자 만약에 while문안으로 들어갔을때 스택의 최상단의(어차피 pop할거니까) Y값을 카운트에 증가시킨다.  28번줄을 보면 알 수 있듯이 기본적으로는 Y값에 1만 넣는다 (depth가 0이 default이기에)

 

자 그런데 20번째 줄을 보면 높이가 같은녀석이 들어올때를 다룬다. 이 때 depth를 사용한다. 높이가 같은애는 그냥쌓기에도 애매하고 그냥 pop하기도 애매하다. 그래서depth의 존재를 불러왔다. 동족포식을 몇번했는지를 depth에 저장한다. 정확히는 동족의 Y값을 자기꺼에 더하는것.

 

그게 20~22내용.

그리고 당연히 while이 끝나면 스택은 비어있거나 temp보다 큰녀석이 최상단에 남는다. 그러니 이때 push를 하려면 한번 카운트를 늘려줘야한다(25~27)   

 

여기서 pop할때의 카운트랑 push할때의 카운트는 별개다. Y쪽의 1+depth는 pop용이다.

 

 

5 4 3 2 5 6 라고 해보자.

5에 4를 올리면 카운트 1 증가한다.

5랑 4 모두 Y값으로 1씩 갖고있다.

여기에 3 올려놓으면 또 한번 1 증가한다 (누적 2)

2올려면 또 +1 (누적3)

5 4 3 2 전부 Y값으로 1을 갖는다.

이때 5를 다음으로 올리면 5는 전부 제거시킨다. (이유? 어차피 그 뒤에 5보다 크거나 작은것은 앞의것들과 못만남, 하지만 5와높이같은녀석은 만날수도 있음 그래서 depth설정)

 

pop되면서 5는 위에서부터 2, 3, 4를 차례로 제거하면서 그들의 Y값을 카운트에 증가시킨다. +1 +1 +1 (누적 6)

그뒤에 남아있는 5도 제거하는데 이때는 카운트 +1 해주고 동시에 Y값을 2로 증가시킨다.

 

왜?  만약 6이 추가로 들어온다고 해보자.

그런데 스택에는 그직전의 5가 전부 제거해서 5혼자남아있다. 그러면 6을넣을때 카운트가 1만 증가하는가?  아니다.

삭제된 첫번째의 5도 사실 6과 만날 수 있다.(4 3 2 는 뒤쪽 5에 가려져서 어차피 못만남)

Y값이 일종의 5의 유산인 셈.