백준 1270 자바 - 전쟁 - 땅따먹기 (BOJ 1270 JAVA)

문제 : https://www.acmicpc.net/problem/1270

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01200/BOJ_1270.java

 

  실3지만, 자바로는 메모리초과 때문에 개인적으로 골드 상위정도는 될 듯 하다. 일단 자바로 성공한게 현재로썬 혼자뿐이다. 문제 자체는 그냥 카운팅만 잘 하면 되는 쉬운 문제이므로 해설은 이 문제를 자바로 도전할 사람들을 위해 메모리를 감소시킨 방식과 일부 이해하기 힘들 수 있는 코드 부분에 대해 적어본다.

 

1.  일단 입력 최대치가 2^31-1이 아니고 int형 범위를 1 넘어간 2^31 이라는 점에서 악의성이 다분하다. 그냥 대충 해싱으로 t개 전부 카운트 하려 했더니 메모리 초과로 터졌다.

 

2. 여기서 중요한 점은 입력은 2^31까지 들어오지만, 어쨌든 입력되는 갯수가 최대 10만개라는 점이다. 그래서 메모리를 최적화 하기 위해서 좌표압축하듯이 2^31까지의 숫자를 10만 이하의 숫자로 압축했다(그럼 10만개 짜리 int형 배열로 카운팅 가능) 새로운 번호가 뜰 때 마다 새로운 번호를 붙여주고 (idx) 실제 번호와 idx만 해싱했다.

 

3. 그리고 입력, 출력도 최적화 하고, 매번 System.gc() 를 통해 강제로 Garbage Collector를 돌려줬다.

 

4. long으로 받고 2^31일 경우는 별도로 처리해서 해시맵에 사용될 메모리도 아꼈다. (HashMap<Long, Integer> 보다 HashMap<Integer, Integer>가 용량이 조금이라도 적게 들어갈테니)

 

여기까지 하고 또 메모리 초과라면 StringBuilder를 쓰지 않고 좀 느리더라도 BufferedWriter로 바로바로 flush 시켜줄까 했는데 다행히 성공했다.