[백준 5430번 / JAVA] AC

문제 링크

https://www.acmicpc.net/problem/5430

5430번: AC

 

 

 

풀이

첫 번째로 제출했을 때 시간이 초과했고 들여다봤더니, 한가지 실수를 범했는데, 이게 엄청 큰 시간을 차지했다.

n의 범위가 100,000까지인데 전부다 String의 메서드를 반복적으로 호출했다.

String arr = br.readLine();
List<Integer> list = new ArrayList<>();
for(int j=0; j<n; j++) {
    list.add(Integer.parseInt(arr.substring(1, arr.length()-1).split(",")[j]));
}

for(String psplit : p.split("")) {
    if(psplit.equals("D")) Dnum++;
    if(Dnum > n) return true;			
}


for(String psplit : p.split("")) {
    if(psplit.equals("R")) {
        R++;
        continue;
    }
    else {
        if(R%2==0) {
            list.remove(0);
        }
        else list.remove(list.size()-1);
    }			
}

위의 두 코드를 보면, 입력 받을 때 List로 집어 넣는 과정에서 전부 substring과 split을 진행하였고

아래의 코드는, 전부 split하여 equals를 사용하여 비교했다.

 

String은 불변 객체로, String 연산 시 내부적으로 새로운 String객체가 생성되어, 추가적인 메모리 할당과 객체 복사를 필요로 한다. 당연히 느리다. 항상 기억하자...

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

class Main{
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
		
		int T = Integer.parseInt(br.readLine());	
		
		StringBuffer sb = new StringBuffer();
		
		for(int i=0; i<T; i++) {
			String p = br.readLine();			
			int n = Integer.parseInt(br.readLine());
			String arr = br.readLine();
			StringTokenizer st = new StringTokenizer(arr.substring(1, arr.length()-1), ",");			
			List<Integer> list = new ArrayList<>();
			
			while(st.hasMoreElements()) {
				list.add(Integer.parseInt(st.nextToken()));
			}
			
			if(errorCheck(p, n)) {
				sb.append("error\n");
				continue;
			}
			
			else {
				funcAC(p, n, list, 0);
				sb.append("[");
				for(int l=0; l<list.size(); l++) {
					sb.append(list.get(l));
					if(l < list.size()-1) {
						sb.append(",");
					}					
				}
				sb.append("]\n");
			}
			
		}
		
		System.out.println(sb);
		
	}
	
	private static boolean errorCheck(String p, int n) {
		p = p.replace("RR", "");
		int Dnum = 0;
		char[] parr = p.toCharArray();
		for(char pchar : parr) {
			if(pchar == 'D') Dnum++;
			if(Dnum > n) return true;			
		}
		return false;
	}
	
	private static void funcAC(String p, int n, List<Integer> list, int R) {
		char[] parr = p.toCharArray();
		for(char pchar : parr) {
			if(pchar == 'R') {
				R++;
				continue;
			}
			else {
				if(R%2==0) {
					list.remove(0);
				}
				else list.remove(list.size()-1);
			}			
		}
		if(R%2==1) {
			for(int i=0; i<list.size()/2; i++) {
				int tmp = list.get(i);
				list.set(i, list.get(list.size()-1-i));
				list.set(list.size()-1-i, tmp);
			}
		}
	}
	
}