글 읽기 - 메모리초과.. 코린이를 살..

seamans_code 2년 전 0

살려주세요 ㅡㅜ

메모리초과라고 나오는데요

arraylist를 써서 그런건지 어떤이유에서인지 모르겠습니다

살려주세요..

	import java.io.BufferedReader;
	import java.io.BufferedWriter;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.io.OutputStreamWriter;
	import java.util.ArrayList;
	import java.util.Collections;


	public class Main {
		public static void main(String[] args) throws IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
			
			String str = br.readLine();
			ArrayList<Character> arr = new ArrayList<>();
			
			for(int i = 0; i < str.length(); i++) {
				String tmp = str.toUpperCase();
				arr.add(tmp.charAt(i));
			}
			br.close();
			Collections.sort(arr);
		
			int num = 0;
			int index = 0;
			
			for(int i = 0; i < arr.size(); i++) {
				int tmp = num;
				num = Collections.frequency(arr, arr.get(i));
				if(tmp == num) {
					num = tmp;
				}else if(tmp > num) {
					num = tmp;
				}
				else index = i;
			}
			
			char maxFrequency = arr.get(index);
			ArrayList<Character> clone = (ArrayList<Character>)arr.clone();
			
			
			while(clone.contains(maxFrequency)) {
				clone.remove(new Character(maxFrequency));
			}
			int num2 = 0;
			for(int i = 0; i < clone.size(); i++) {
				int tmp = num2;
				num2 = Collections.frequency(clone, clone.get(i));
				if(tmp == num2) {
					num2 = tmp;
				}else if(tmp > num2) {
					num2 = tmp;
				}
			}
			
			if(num > num2) {
				bw.write(maxFrequency + "\n");
			}else bw.write("?");
			bw.flush();
			bw.close();
			
		}
		
}

nahwasa 2년 전 0

String tmp = str.toUpperCase(); 부분은 맨 위에 한번만 하면 될 것 같습니다.

String 자체가 final 이라 개별적으로 메모리를 차지하게 될텐데, str.length()가 최대 100만이므로 100만*100만*character사이즈 정도의 용량을 먹겠네요. 물론 GC가 중간에 돌긴 하겠지만 그래도 이걸로 메모리 초과는 확실히 날 것 같습니다.

또한 toUpperCase의 정확한 시간복잡도는 모르겠지만, 일반적으로 생각할 수 있는 O(N) 정도로 대문자로 바꾸는 알고리즘 형태라면 역시 저것만으로도 시간초과가 날 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리초과.. 코린이를 살..

seamans_code 2년 전 0

nahwasa 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말