Hash 함부로 쓰면 메모리 터진다

문제풀어보기

실버 3의 비교적 쉬운 문제처럼 보이는데요. 위 문제는 생각없이 풀면 머리에 ? 띄우기 딱 좋은 문제입니다. 특히 잘못된 풀이의 경우 논리적, 시간복잡도 측면에서도 틀린 것이 전혀 없기 때문에 헤매기 매우 쉽습니다. 풀이방향 잘못 잡으면 메모리 초과가 발생하기 때문에, 공간복잡도를 건드는 문제는 조심해서 접근해야합니다.

심지어 python, cpp에서는 문제 없이 통과되는 코드가 Java 특유의 객체지향성과 JVM/GC 특성이 환장의 시너지를 일으켜 통과가 안되는 경우가 꽤 있습니다. (억울) Java 쓴다고 이런 패널티를 받을 수는 없으니, 유의하도록합시다. (혹은 빠른 시일 내에 cpp나 python으로 갈아ㅌ..)

대기업 공채에서 이런 문제에 잘못 낚일 경우 6개월에서 1년동안 손가락 빨고 있어야합니다 ㅎㅅㅎ

문제를 간단히 요약하면 다음과 같습니다.

1. n개의 좌표가 입력으로 주어진다.
2. 직사각형의 길이 a,b가 주어진다.
3. n개의 좌표로 직사각형을 만들 때 길이가 일치하는 경우의 수 구하기

특이한건 전체 데이터의 개수가 약 10^5 개, 각 좌표값은 long 타입 써야할 정도로 숫자가 매우 흉악한데요. 전형적인 데이터 개수 & 크기로 내리찍는 문제입니다. 이 부분을 유의하면서 풀어봅시다. 불행 중 다행으로 전체 경우의 수는 2^31 안으로 나온다했으니, 정답 변수 만큼은 int로 선언할 수 있겠네요.

정말 간단하게 접근했을 때의 풀이입니다. 백트래킹이나 4중 반복문을 써서 가능한 모든 조합을 테스트 해보는 것입니다. 먼저 시간 복잡도를 계산해보겠습니다. 백트래킹으로 구현할 경우 조합의 개수 만큼 시간 복잡도가 나옵니다. nC4가 되므로 n=500,000을 넣어 계산해보겠습니다.
500000C4 = 2,60,385,417,812,487,500(~=10^17)이므로 택도 없는 풀이네요.

그렇다면 고려해볼만한 것은 해시입니다. 풀이는 다음과 같습니다.

답안 로직

1. x와 y좌표를 속성으로 갖고 x,y로 고유성을 판별할 수 있는 Position클래스를 정의합니다.
2. 주어진 모든 점을 해시셋에 넣습니다.
3. 가장 왼쪽 아래의 점(x y)을 잡았다 치고 주어진 모든 점을 순회합니다.
4. 해시셋에서 나머지 3개의 점 (x+a, y+b), (x,y+b), (x+a,y) 이 있는지 확인합니다.

전체 코드는 다음과 같습니다.

시간복잡도를 계산해볼까요?

1. 주어진 입력을 Position 객체로 만들어 해시셋에 저장합니다.(=O(n))
2. 전체 좌표에 대해 순회합니다. (=O(n))
3. 기준 좌표에 대해서 나머지 3개의 좌표가 존재하는 지 해시를 통해 확인합니다. (=O(3x1))
4. 전체 시간 복잡도는 다음과 같습니다. O(n+3*n) = O(n)

전체 시간복잡도는 O(n)으로 매우 무난하게 통과해야하는데요.

보시는 바와 같이, 메모리 초과가 발생합니다. 왜 메모리 초과가 발생할까요? 그리고 실전에서 이와 같은 풀이를 방지하려면 어떻게 해야할까요??

128MB 메모리 제한이 있을 때, Set<Position>가 최대 몇 개의 키를 가질 수 있는지 계산하기 위해서는 각 Position 객체가 차지하는 메모리 크기를 알아야 합니다. 이를 위해 Position 클래스의 메모리 크기를 분석해야 합니다.

Position 클래스는 두 개의 long 필드를 가지고 있습니다. long 타입은 64비트(8바이트)이므로, 두 개의 long 필드는 16바이트를 차지합니다. 그러나 Java 객체에는 추가적인 오버헤드가 존재합니다.

Java 객체의 메모리 오버헤드는 다음과 같이 계산됩니다:

1. 객체 헤더: 12바이트 (8바이트는 기본 객체 헤더, 4바이트는 정렬 패딩)
2. long 필드 두 개: 16바이트 (각각 8바이트)

따라서, Position 객체는 12바이트(헤더) + 16바이트(필드) = 28바이트가 됩니다. 그러나 Java 객체는 메모리 정렬 패딩에 따라 8바이트 단위로 정렬됩니다. 그러므로 28바이트는 32바이트로 정렬됩니다.

하지만 실제로 Map에 키로 사용될 때는 추가적인 메모리 오버헤드가 발생합니다. 일반적으로 HashSet을 예로 들면:

• HashSet.Entry 객체: 약 32바이트 (참조 변수와 정렬 패딩 포함)
• 기타 오버헤드 (해시 테이블 등): 해시 테이블 크기에 따라 다름

보수적으로 계산해보면, 하나의 Position 객체가 HashSet의 키로 사용될 때 약 64바이트의 메모리를 차지한다고 가정할 수 있습니다.

이제 전체 메모리 사용량을 계산해 보겠습니다:

• 주어진 메모리 제한: 128MB = 128 1024 1024 바이트 = 134,217,728 바이트

각 Position 객체가 약 64바이트를 차지하므로, Map이 가질 수 있는 최대 키의 개수는:

바이트바이트객체개

따라서, 128MB 메모리 제한이 있을 때 Set<Position>은 최대 약 2,097,152개의 키를 가질 수 있습니다.

문제에서 풀이는 처음 해시셋에 키를 저장할 때 최대 50만개의 키, 3개의 점으로 판단할 때 최대 200만(4x50만)개의 키를 사용합니다.

즉 최대 250만개의 키를 사용할 가능성이 있기 때문에 128MB의 메모리 제한이 있을 때 메모리 초과가 발생합니다.

그렇다면 해시를 사용하지 않으면 어떻게 해야할까요? 바로 이진탐색을 사용하는 것입니다. 속성이 2가지라 이진 탐색 사용이 어려울 것 같지만, java의 comparable 인터페이스를 구현하여 정렬을 하면 비교적 쉽게 구현할 수 있습니다.

풀이는 해시와 비슷합니다.

1. 전체 좌표에 대해서 순회한다.
2. 해당 좌표를 좌하단 좌표로 기준을 잡고 판단한다.
3. 나머지 3개의 좌표((x+a, y+b), (x,y+b), (x+a,y))를 이진탐색을 활용해 있는지 없는지만 빠르게 판단한다.

보시는 바와 같이 기본적인 논리구조는 같은데, 실제 값을 찾을 때 해시를 사용할 것이냐, 이진탐색을 사용할 것이냐의 차이로 갈리게 됩니다.

시간복잡도는 전체 좌표에 대해서 순회하는 시간 O(n), 이진탐색을 이용해서 나머지 3개의 좌표가 있는지 없는지 판단하는 시간 O(logN) 총 O(3nlogN)이므로 해시보다는 느려도, 매우 넉넉하게 시간 제한 안에 들어올 수 있습니다.

실제 코드를 통해 확인해보겠습니다.

이진탐색에서 활용할 데이터 셋은 정렬이 필수기 때문에 정렬을 해주는 모습입니다.

for (int i = 0; i < n; i++) {
	tokens = new StringTokenizer(buffer.readLine());

	positions[i] = new Position(
		Long.valueOf(tokens.nextToken()), 
		Long.valueOf(tokens.nextToken())
		);
	}

Arrays.sort(positions);
Copy

전체 좌표를 순회하며 좌하단으로 고정했을 때 나머지 3개의 좌표가 있을 때만 세는 코드입니다.

long result = Arrays.stream(positions)
                .filter(p->isValid(positions, p, a,b))
                .count();
Copy

private static boolean isValid(Position[] positions, Position position, int a, int b){
	return binarySearch(positions, position.x+a, position.y+b)&&
			binarySearch(positions, position.x, position.y+b)&&
			binarySearch(positions, position.x+a, position.y);

}
Copy

객체의 comparable 인터페이스를 구현하여 두 종류 이상의 변수가 있어도 쉽게 이진탐색을 수행하는 코드입니다.

private static boolean binarySearch(Position[] positions, long targetX, long targetY) {
	int l = 0;
	int h = positions.length;


	while(h>l){
		int mid = (l+h)/2;

		Position midPosition = positions[mid];

		if(midPosition.x==targetX&&midPosition.y==targetY){
			return true;
		}else if(midPosition.compareTo(new Position(targetX, targetY))<0){
			l=mid+1;
		}else{
			h=mid;
		}
	}

	return false;

}

Copy

class Position implements Comparable<Position>{
    long x, y;


    public Position(long x, long y){
        this.x = x;
        this.y = y;
    }
	//equals와 compareTo를 오버라이딩한 메서드는 중략... 

    @Override
    public int compareTo(Position o){
        if(this.x==o.x){
            return Long.compare(this.y, o.y);
        }
        return Long.compare(this.x, o.x);
    }
}
Copy

파이썬 해시 활용 제출코드
자바 이진탐색 활용 제출코드

def is_rectangle_present(x, y, A, B, point_set): 
	return ((x + A, y) in point_set 
				and (x, y + B) in point_set 
				and (x + A, y + B) in point_set)

def count_rectangles(points, A, B):
    point_set = set(points)
    count = 0

    for (x, y) in points:
        if is_rectangle_present(x, y, A, B, point_set):
            count += 1

    return count

import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
A = int(data[1])
B = int(data[2])

points = []
for i in range(N):
    x = int(data[3 + 2 * i])
    y = int(data[4 + 2 * i])
    points.append((x, y))

result = count_rectangles(points, A, B)


print(result)

Copy

해쉬를 사용하는 동일한 풀이를 python으로 작성하고 제출해봤습니다.

자바는 오늘도 연전연패..