[BOJ]12757번: 전설의 JBNU

 

www.acmicpc.net/problem/12757

---

오리버거님 풀이(blog.naver.com/PostView.nhn?blogId=uss425&logNo=222033992924&categoryNo=94&parentCategoryNo=63&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView)를 참고하여 해결하였습니다.

 

주요 기법은 두 가지 입니다.

1. STL map의 lower_bound를 사용

 

lower_bound는 set이나 map에서 특정 key보다 같거나 큰 key중에 가장 왼쪽에 있는 값을 가져옵니다.

 

upper_bound와의 차이는 

특정 key '이상'값을 대상으로 하면 lower_bound 입니다.

특정 key '초과'값을 대상으로 하면 upper_bound 입니다.

 

즉, 우연으로 set이나 map 내부에 있는 key 값과 검색하려는 key 값이 일치한다고 가정해보겠습니다.

이 경우, 

lower_bound는 일치한 key 값을 리턴합니다.

upper_bound는 일치한 key보다 큰 값 중에 가장 왼쪽에 있는 값을 리턴합니다.

 

2. 2개의 map 선언

원래 숫자의 key, value를 저장하고 있는 map 1개

원래 숫자의 음수 값으로 -key, value를 저장하고 있는 map 1개

 

이렇게 두 개를 사용하여 특정 key를 기준으로 양 옆에 있는 값을 모두 비교할 수 있도록 했습니다.

 

그래서 양 옆의 값을 비교하면서 문제의 조건대로 해결하면 됩니다.

---

코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ12757.cc