풀이방법
사용된 것:
이분 탐색
좌표압축
2022.06.08
간단한 코드로 풀리는 문제이지만,
좌표압축의 대표적인 예제이므로
좌표압축과 관련된 기본적인 내용까지 포함하여 자세하게 적었다.
단, 이분 탐색에 대한 설명은 적지 않았다.
이분 탐색에 대한 설명 및 좌표압축에 대한 매우 기본적인 이야기는 아래의 ICPC 강의 정리글에 있다.
관련된 신촌 ICPC 강의 정리글
초급 7회차 이분탐색 & 분할정복
이분탐색과 분할정복 모두 문제를 쪼개어 해결하는 방식임. 쪼갠다는 것은 무엇인가 문제의 크기가 크면 어렵다. 문제를 작은 부분 문제들로 나누어 풀면 쉬워진다. 문제를 쪼개고, 부분 문제들
blowupmomo.tistory.com
오답노트 #2370 : 시장 선거 포스터
풀이방법 및 문제점 2022.06.08 (1) 이분탐색을 쓰지 않고 그냥 좌표압축을 시도해보았다. 해시맵을 사용하였다. 역시 시간초과가 발생한다. 답의 값 자체는 맞게 도출되는 것 같다. 2022.06.08 (2) 이분
blowupmomo.tistory.com
좌표압축을 하지 않으면 길이가 1억인 자료구조를 사용해야 하는 문제이다. 이럴 경우 메모리 초과가 발생한다.
좌표압축을 하면 최악의 경우라도 길이가 20000인 자료구조로 문제를 풀 수 있다.
왜 그런지는 입력 제한과 범위를 살펴보면 알 수 있다.
포스터는 최대 10000개가 붙는다.
그리고 포스터마다 시작좌표와 끝좌표 2개의 좌표가 주어진다.
따라서 최대 20000가지의 서로 다른 좌표들이 입력될 수 있다. 포스터의 개수가 10000개 미만이거나 서로 겹치는 좌표가 있다면 주어지는 서로 다른 좌표들의 종류는 20000개보다 적다.
좌표압축을 하면, 최악의 경우라도 우리가 사용해야 하는 자료구조의 크기는 1억칸이 아니라 20000칸이 될 것이다.
따라서 좌표압축이 필수인 문제이다.
문제 해결과정은
- 좌표압축을 하는 단계
- 압축된 좌표를 바탕으로 포스터들을 붙이는 단계
- 포스터들이 다 붙은 모습을 보고 눈에 보이는 포스터가 몇 개인지 세는 단계
총 세 단계로 이루어진다.
1. 좌표압축을 하는 단계
백준 문제 페이지에 주어진 예제 1번의 경우, 좌표들을 압축하면 각각의 좌표들이 어떻게 바뀌는지 살펴보자.
입력된 좌표들 중 값이 가장 작은 것은 1이고 가장 큰 것은 10이다. 따라서 실제로 포스터들이 붙는 벽에서는 10byte의 공간이 사용된다.
좌표압축을 하지 않고 10byte짜리 벽에 그대로 포스터를 붙이면 결과는 다음과 같다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 4 | 4 | 2 | 2 | 5 | 5 | 5 | 5 |
하지만! 주어진 서로 다른 좌표는
1, 2, 3, 4, 6, 7, 8, 10 으로 총 8가지밖에 없다.
따라서 좌표압축을 하고 이를 바탕으로 8byte짜리 벽에 포스터를 붙여도 아무런 문제 없이 올바른 결과가 도출된다.
크기가 8인 1차원 배열을 선언하고 각 인덱스마다 1, 2, 3, 4, 6, 7, 8, 10 을 할당하면 다음과 같이 좌표가 압축된다.
| 압축된 값 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 실제 좌표 | 1 | 2 | 3 | 4 | 6 | 7 | 8 | 10 |
| 포스터 | 1 | 2 | 4 | 4 | 2 | 5 | 5 | 5 |
더 적은 메모리를 사용하면서도 문제 없이 포스터의 겹침 여부를 표시할 수 있다.
그럼 코드로는 어떻게 짜야 할까?
백준 문제 페이지의 예제 1을 계속 예로 들어 설명하겠다.
먼저 주어지는 모든 입력값들을 길이가 2*N인 1차원 정수 배열 arr에 순서대로 쫙 저장한다.
그리고 트리셋에도 쫙 넣는다.
arr에는 모든 입력값들이 입력 순서대로, 중복이 제거되지 않은 채 저장되고
트리셋에는 모든 입력값들이 오름차순으로 정렬되어 중복이 제거된 채 저장된다.
arr의 모습
{1, 4, 2, 6, 8, 10, 3, 4, 7, 10}
ts의 모습
{1, 2, 3, 4, 6, 7, 8, 10}
이제 arr의 각 값들을 좌표압축된 값으로 교체해준다.
| 압축 전 | 1 | 2 | 3 | 4 | 6 | 7 | 8 | 10 |
| 압축 후 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
이렇게 바꾸어주는 것이다.
1은 0으로,
2는 1로,
3은 2로,
4는 3으로,
6은 4로
...
10은 7로
싹 교체해주면 된다.
좌표압축을 하는 과정은 진짜 간단하고 쉽다. 하지만 글로 읽으면 이해가 잘 안 될 수 있다. 이왕이면 그냥 아래에 있는 코드를 읽는 게 편하다.
아무튼 설명해보자면 다음과 같다.
모든 arr[i]에 대하여,
트리셋 상에서 arr[i]의 값이 존재하는 위치를 구하고
그 위치값을 arr[i]에 저장해주어야 한다.
이때 트리셋 상에서 arr[i]의 값의 위치를 빠르게 구해야 하기 때문에 이분탐색이 쓰인다.
먼저, 이분탐색은 인덱스가 존재하는 선형 자료구조에서 작동하므로 트리셋에 들어있는 수들을 그대로 새로운 1차원 정수 배열 tsarr에 복사해 넣는다. (정렬과 중복값 제거를 위해 트리셋을 사용하였지만 트리셋은 트리의 구조로 자료를 저장하며 인덱스로 자료를 탐색할 수 없다)
그 다음,
모든 arr[i]에 대하여,
tsarr 상에서 arr[i]의 값이 저장된 곳의 인덱스를
이분탐색을 이용해 찾는다.
그 인덱스 값을 arr[i]에 저장해준다.
이러한 좌표압축을 하는 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
//이분탐색의 대상이 될 배열
static int[] tsarr;
//이분탐색법으로 배열 상에서 특정 값의 위치를 찾는 함수
static int find(int target) {
int start = 0;
int end = tsarr.length-1;
while(start<end) {
int mid = (start+end)/2;
if(tsarr[mid]==target) return mid;
else if(tsarr[mid]>target) end = mid-1;
else start = mid+1;
}
return end;
}
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//입력값 읽어오기
int n = Integer.parseInt(br.readLine());
int[] arr = new int[2*n];
TreeSet<Integer> ts = new TreeSet<Integer>();
for(int i=0; i<2*n; i+=2) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr[i] = Integer.parseInt(st.nextToken());
arr[i+1] = Integer.parseInt(st.nextToken());
ts.add(arr[i]);
ts.add(arr[i+1]);
}
//좌표압축 전의 좌표들을 출력
for(int i=0; i<2*n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
//좌표압축하기
tsarr = new int[ts.size()];
int idx = 0;
for(int i: ts) {tsarr[idx++] = i;}
for(int i=0; i<2*n; i++) {
arr[i] = find(arr[i]);
}
//좌표압축 후의 좌표들을 출력
for(int i=0; i<2*n; i++) {
System.out.print(arr[i] + " ");
}
}
}입력값: 백준 문제 페이지의 예제 1 입력값
5
1 4
2 6
8 10
3 4
7 10
출력값:
1 4 2 6 8 10 3 4 7 10
0 3 1 4 6 7 2 3 5 7
| 압축 전 | 1 | 2 | 3 | 4 | 6 | 7 | 8 | 10 |
| 압축 후 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
각각의 좌표값에 대하여 위 표와 같은 값이 할당되었음을 볼 수 있다.
2. 압축된 좌표를 바탕으로 포스터들을 붙이는 단계
이제 압축된 좌표를 바탕으로 포스터들을 붙이면 된다.
좌표를 압축하고 나니, 좌표들 중 가장 작은 것은 0, 가장 큰 것은 7이다.
따라서 길이가 8byte인 벽에다 포스터들을 모두 붙일 수 있다.
길이가 8인 1차원 정수 배열 wall을 선언한다.
모든 포스터에 대하여,
wall[포스터 시작지점]부터 wall[포스터 끝지점]까지를 각각의 고유한 번호로 채우는 작업을 반복하면 된다.
포스터의 시작지점과 끝지점은 arr에 좌표압축된 상태로 저장되어있으니, arr을 처음부터 읽어가며 붙이면 된다.
이 과정을 끝내면 길이가 8byte인 벽은 다음과 같은 상태가 된다.
여기까지 구현한 코드는 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
//이분탐색의 대상이 될 배열
static int[] tsarr;
//이분탐색법으로 배열 상에서 특정 값의 위치를 찾는 함수
static int find(int target) {
int start = 0;
int end = tsarr.length-1;
while(start<end) {
int mid = (start+end)/2;
if(tsarr[mid]==target) return mid;
else if(tsarr[mid]>target) end = mid-1;
else start = mid+1;
}
return end;
}
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//입력값 읽어오기
int n = Integer.parseInt(br.readLine());
int[] arr = new int[2*n];
TreeSet<Integer> ts = new TreeSet<Integer>();
for(int i=0; i<2*n; i+=2) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr[i] = Integer.parseInt(st.nextToken());
arr[i+1] = Integer.parseInt(st.nextToken());
ts.add(arr[i]);
ts.add(arr[i+1]);
}
//좌표압축하기
tsarr = new int[ts.size()];
int idx = 0;
for(int i: ts) {tsarr[idx++] = i;}
for(int i=0; i<2*n; i++) {
arr[i] = find(arr[i]);
}
//벽면에 포스터 붙이기
int[] wall = new int[ts.size()];
for(int i=0; i<2*n; i+=2) {
for(int j=arr[i]; j<=arr[i+1]; j++) {
wall[j] = i;
}
}
}
}
위 코드처럼 하면 wall에는 {0, 2, 6, 6, 2, 8, 8, 8}이 저장된다.
이해하기 쉽게 {0, 1, 3, 3, 1, 4, 4, 4}나 {1,2, 3, 3, 2, 4, 4, 4}와 같이 저장해도 된다... 근데 별 상관 없다.
포스터마다 unique한 값이 할당되기만 하면 된다.
나는 연산을 하나라도 줄이는 게 나을 것 같아서 그냥 저장 당시의 i값을 그대로 박아넣었다.
3. 눈에 보이는 포스터가 몇 개인지 세는 단계
이 단계는 매우 간단하다.
중복값이 자동으로 제거되는 자료구조를 아무거나 선언한다.
나는 해시셋을 사용했다.
여기다가 wall에 저장된 모든 값을 집어넣는다.
다 넣은 뒤의 해시셋의 크기가 바로 정답이다.
(해시셋 이름).size()
를 화면에 출력한다.
코드
Java(2022.06.08)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
//이분탐색의 대상이 될 배열
static int[] tsarr;
//이분탐색법으로 배열 상에서 특정 값의 위치를 찾는 함수
static int find(int target) {
int start = 0;
int end = tsarr.length-1;
while(start<end) {
int mid = (start+end)/2;
if(tsarr[mid]==target) return mid;
else if(tsarr[mid]>target) end = mid-1;
else start = mid+1;
}
return end;
}
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//입력값 읽어오기
int n = Integer.parseInt(br.readLine());
int[] arr = new int[2*n];
TreeSet<Integer> ts = new TreeSet<Integer>();
for(int i=0; i<2*n; i+=2) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr[i] = Integer.parseInt(st.nextToken());
arr[i+1] = Integer.parseInt(st.nextToken());
ts.add(arr[i]);
ts.add(arr[i+1]);
}
//좌표압축하기
tsarr = new int[ts.size()];
int idx = 0;
for(int i: ts) {tsarr[idx++] = i;}
for(int i=0; i<2*n; i++) {
arr[i] = find(arr[i]);
}
//벽면에 포스터 붙이기
int[] wall = new int[ts.size()];
for(int i=0; i<2*n; i+=2) {
for(int j=arr[i]; j<=arr[i+1]; j++) {
wall[j] = i;
}
}
//보이는 포스터 개수 세기
HashSet<Integer> cnt = new HashSet<Integer>();
for(int i: wall) cnt.add(i);
//정답 출력
System.out.print(cnt.size());
}
}'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
| #1059 : 좋은 구간 (0) | 2022.06.12 |
|---|---|
| #3187 : 양치기 꿍 (0) | 2022.06.09 |
| #17829 : 222-풀링 (0) | 2022.06.04 |
| #14626 : ISBN (0) | 2022.06.01 |
| #1260 : DFS와 BFS (0) | 2022.06.01 |