codeTree - Grid Compression [Hard]

https://www.codetree.ai/missions/8/problems/count-number-of-points-2?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

처음보는 개념의 문제라서, 작성해보고자 한다. 비슷한 유형의 코테 문제도 많이 봤던 것 같아 자세하게 이해하고 넘어가보자!!!

 

Pair 클래스는 해당 x,y 지점을 담을 것이고, Tuple 클래스는 직사각형의 왼쪽 아래와 오른쪽 위 지점을 담을 것이다.

 

init 부분

신기했던 것은 nums라고 만들어진 TreeSet에 해당 좌표 x,y 지점을 넣어준다. 그리고 queries에는 직사각형 좌표의 지점 정보를 넣는다. 이후 TreeSet에 들어간 points 정보들에 대해 mapper라는 HashSet의 값을 추가해줄 것이다. HashSet의 key는 정렬되어있는 좌표들 값이고, value는 순서를 넣는 cnt 값이다.

 

points의 정보들을 이제 압축하는데, 이를 통해 prefixSum인 부분합 배열을 완성한다.

 

 

처음 봤을 때 굉장히 어려운 문제 같았다. 이해하기 위해 비슷한 문제의 유형을 풀어보았고, 문제에 대한 접근과 제한사항을 고려해서 적용할 수 있을 때 사용한다면 유용한 방안이 될 것 같다.