본문 바로가기
PS/Posts

백준에서 자바로 풀려면 난이도가 매우 상승하는 문제들

by Nahwasa 2022. 4. 23.

발견할 때 마다 추가예정! 아는거 있는분은 알려주세요.

 

1. Transform the String (boj23716)

이유 - 메모리 초과

  로직 자체는 브론즈라 별거 없는데, 문제는 입력받은걸 character로 유지하면 메모리 초과가 된다 ㅋㅋㅋ 즉, BufferedReader나 Scanner로 String으로 입력받으면 메모리 초과 뜬다. 2byte인 character 대신 1byte인 byte로 입력받아야 한다. 즉, 직접 DataInputStream 같은 좀 더 low한 입력 클래스로 한땀한땀 byte로 입력을 받아줘야 한다.

 

 

2. 전설 (boj19585)

이유 - 좀 더 최적화된 로직을 요구함

  이건 풀이 로직에 따라 고수분이 하면 자바로 딱히 어렵다는 생각 안들고 뚫을 수도 있긴하다. 이 문제에 대해 일반적으로 생각하는 Trie 2개를 유지하며 푸는 방법에 대해 다른 언어론 통과가 가능한데, 자바로는 불가했다. 몇시간동안 머리 싸매고 여러 아이디어 넣어서 다 풀고 다른 언어 코드 보니 이미 이이이이전에 생각했던 로직으로 통과가 되더라 ㅠ

 

 

3. 전쟁 - 땅따먹기 (boj1270)

이유 - 메모리 초과

  7달전에 통과했는데, 아직도 자바 통과가 1명뿐인 문제이다. 문제가 자바는 unsigned int가 없다. 따라서 2^31을 받으려면 long으로 받아야 한다. 근데 이 문제의 경우 long으로 받으면 메모리 초과가 된다 ㅋㅋㅋㅋ. 내 경우엔 그래서 int 범위 넘는 부분을 음수로 빼고, tc도 전부 받지 않도록 버퍼를 제한하고, 수동으로 gc를 돌리는 등 이상한 짓들을 많이해서 통과시켰다.

 

 

4. 가넷이나 버는게 낫지 않아요? (boj10979)

이유 - 메모리 초과

  풀게된 계기가, 게시판 질문글에 자바로 입력만 받았는데 이미 메모리가 터졌다는 말을 보고 뚫어보려고 시도했다가 자바로 뚫는데 10시간 넘게 걸렸다.. 결론적으로 입력을 버퍼를 제한해서 받아야하고, gc도 수동으로 돌려줘야 하고, 로직도 최대한 최적화 시켜서 짜야 통과가 가능하다. 채점 현황을 보면 많은 자바러들의 통곡이 느껴진다. 내가 성공한게 다른 분들 시도까지 합쳐서 60번정도의 자바 제출 시도 끝에 처음 성공한거다 ㅋㅋㅋ(나만 해도 31번)

 

 

5. Tales of seafaring (boj8244)

이유 - 메모리 초과

  지금까지 중 메모리 초과 뚫기가 가장 힘들었다. 우선 온라인 쿼리로는 아예 불가하다. 5000x5000 배열 만들면 바로 터진다. 최대치 생각해서 short로 해도 터진다 ㅂㄷㅂㄷ.. 그래서 어쩔 수 없이 오프라인 쿼리로 진행해야 하는데, 그렇게 해도 위에서 말한 여러 방법들을 섞어야한다. 버퍼를 제한해서 받기, 일정 횟수마다 수동 gc 등..

  자바론 정신건강상 시도 안하는걸 추천한다.

 

 

6. 칠무해 (boj14729)

이유 - 좀 더 최적화된 로직을 요구함

  이 문제가 실버5인 이유는 단순히 전부 배열에 넣고 정렬 후 7개를 출력해주면 되기 때문이다. 하지만 자바로는 이게 안된다! 되긴한데, 할꺼면 Scanner나 BufferedReader(버퍼 개수 제한해도 안됨)가 아니라 직접 바이트 단위로 입력을 받아서 직접 처리해줘야 한다. 일반적으로 이건 힘드니깐.. 따라서 다음과 같이 해야 한다.
A. 7개 짜리 배열을 만든 후 입력받으면서 버블 정렬 하듯이 계속해서 정렬 시켜줌(수동)

B. 7개 짜리 배열에 입력받은 후 매번 정렬 돌려도 사실 시간이 길어서 된다.

C. PriorityQueue를 민힙이 아니라 맥스힙처럼 써서 top을 확인하면서 더 크다면 무시하고, 작으면 poll 후 push하는식으로 짜도 되긴 한다(힙 사이즈 7개로 유지).

아무튼 이렇게 되면 실버5 수준은 아니므로 난이도에 비해 자바로 하면 더 높은 티어 수준의 로직을 요구한다.

댓글