코딩하는 고릴라

🦍 문제 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 🐈 문제 풀이 1. 무엇을 구해야 할까? 주어진 숫자들의 빈도를 계산한 후, 빈도수가 높은 숫자들부터 순서대로 출력한다. 빈도수가 같다면 먼저 나왔던 숫자들을 우선적으로 출력한다. 2. 어떻게 구해야 할까? 1) 빈도수를 구해야 한다. - 보통 빈도수를 구하는 방법으로는 배열을 사용하는 방법을 떠올릴 수 있지만 입력되는 수의 최댓값이 10억이기에 HashMap 자료구조를 이용하였다. - key 값으로는 입력받은 숫자를, value로는 빈도수를 저장하였다. - HashMap에 저장된 값을 빈도수(..

🐒 문제 7626번: 직사각형 첫째 줄에 양의 정수 N이 주어진다. (1 ≤ N ≤ 200,000) 다음 N개 줄에는 공백으로 나누어진 네 값 "x1, x2, y1, y2"가 주어진다. 이 값은 직사각형 [x1,x2] × [y1,y2]를 나타낸다. 모든 좌표는 0보다 크거나 www.acmicpc.net 🐈 풀이 1. y좌표 압축 2. x축 정렬 후 x축 방향으로 순차적으로 스위핑 3. 스위핑하며 직사각형의 세로선 활성화 및 비활성화를 통해 좌표상의 직사각형 넓이를 구한다. 1. 주어지는 x, y 좌표의 최대값이 매우 커 이를 바로 활용해 트리를 만들 수 없다. 따라서 좌표 압축을 필요로 한다. 2. 스위핑 기법을 통해 문제풀이를 진행하되, 과연 어떤 값을 어떻게 저장하고 꺼내와야 하는지의 아이디어가 중요..

🐒 문제 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 🐈 문제풀이 핵심 A번 ~ B번 인덱스를 확인했을 때 해당 구간에 A번부터 B번까지의 값이 모두 존재하는지 확인하는 것을 어떤 식으로 구현할지가 관건이다. 이를 위해 해당 구간의 최솟값, 최댓값을 구하여 확인하는 방법을 이용했다. A번 ~ B번 인덱스 구간의 값을 확인했을 때, 최소값이 A이고 최댓값이 B라면 그 둘 사이의 값은 모두 A와 B 사이에 있음을 보장받는다. 따라서 해당 구간의 최솟값, 최댓값만 구..