글 읽기 - 시간 초과 문제 도움 부탁드립니다.

kisrin4319 7년 전 0

로직은 맞다고 생각되는데 시간초과가 나네요

ArrayList 말고 다른 방법을 이용해야 할까요?

힌트를 주신다면 감사하겠습니다!

import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		sc.nextLine();
		for (int cycle = 0; cycle < n; cycle++) {
			String s = sc.nextLine();
			int cursor = 0;
			ArrayList s2 = new ArrayList();
			String result = "";
			for (int i = 0; i < s.length(); i++) {
				if (s.charAt(i) == '<') {
					if (cursor != 0) {
						cursor--;
					}
				} else if (s.charAt(i) == '>') {
					if (cursor != s2.size()) {
						cursor++;
					}
				} else if (s.charAt(i) == '-') {
					if (cursor != 0) {
						cursor--;
						s2.remove(cursor);
					}
				} else {
					s2.add(cursor, s.charAt(i));
					cursor++;
				}

			}
			for (int i = 0; i < s2.size(); i++) {
				result += s2.get(i);
			}
			System.out.println(result);
		}
		sc.close();
	}
} // main class close

kesakiyo 7년 전 0

ArrayList는 임의의 위치에 삽입, 삭제할 때 시간복잡도가 O(n)입니다.

따라서 이 문제를 풀기에는 적합하지 않아요.

시간복잡도를 모르신다면 한번 공부한 뒤 다시 생각을 해보는것도 좋을 것 같습니다.

정답부터 말하자면 ArrayList대신 LinkedList를 사용하면 제 시간내에 들어오는 코드를 짤 수 있습니다.

kisrin4319 7년 전 0

감사합니다!

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

문제

문제

출처

ICPC

시간 초과 문제 도움 부탁드립니다.

kisrin4319 7년 전 0

kesakiyo 7년 전 0

kisrin4319 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말