글 읽기 - 시간초과가 나오는데 방법이 있을까요?

impact0823 7년 전 0

시간초과가 나오는데 방법이 있을까요? 도와주세요

정답은 나오긴 하는데... 시간 복잡도가 .....큰가봐요

어떤방법으로 해야 할까요?

인터넷을 뒤져봐도 이와 관련된 질문 답이 없네요

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

class Main{
    public static void main (String args[]) {
    Scanner sc = new Scanner(System.in);
    int commandCount  = Integer.parseInt(sc.nextLine());
    String[] arrCommand = new String [commandCount];
    for (int i=0; i<commandCount; i++) {
    arrCommand[i]=sc.nextLine();
    }
    String result=operataion(arrCommand, commandCount);
    System.out.println(result);
    }
    private static String operataion(String[] arrCommand, int commandCount) {
    String result= "";
    Map<Integer, String> map = new HashMap<Integer, String>();
    
    for (int i = 0; i<commandCount; i++) {
    String[] sptCommand = arrCommand[i].split(" ");
    switch(sptCommand[0]) {
    case "type":{
    result=result.concat(sptCommand[1]);
    int second = Integer.parseInt(sptCommand[2]);
    map.put(second, result);
    break;
    }
    case "undo": {
    while(true) {
    int now= Integer.parseInt(sptCommand[2]) 
    - Integer.parseInt(sptCommand[1])-1;
    
    if (now<1) {
    result="";
    map.put(Integer.parseInt(sptCommand[2]), result);
    break;
    }
    else if (map.containsKey(now)) {
    result=map.get(now);
    map.put(Integer.parseInt(sptCommand[2]), result);
    break;
    }
    else {
    --now;
    }
    }
    break;
    }
    }
    }
    Set keys=map.keySet();
    int maxKey=0;
    for (Iterator key=keys.iterator();key.hasNext();) {
    int realKey=(int)key.next();
    if (maxKey<realKey) {
    maxKey = realKey; 
    }
    }
    
    return map.get(maxKey);
    }
    
}​

dlaud5379 4년 전 0

이 문제는 O(n)으로 풀리는 문제입니다. undo가 적당히 많이 있는 테스트 케이스를 만들어서 최종적으로 무슨 명령어가 실행되고(실행 취소가 실행 취소되는 경우 포함해서), 무슨 명령어가 실행 취소되는지 훑어보다 보면 아이디어가 나올 수도 있어요!

아래쪽에 예시 테스트 케이스를 첨부해 두었습니다. 답은 abcdf입니다.

16
type a 1
type b 2
type c 3
type d 4
undo 2 5
undo 1 6
undo 4 7
undo 2 8
type e 9
undo 3 10
type f 11
undo 1 12
undo 3 13
type g 14
undo 6 15
undo 4 16

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

문제

문제

출처

ICPC

시간초과가 나오는데 방법이 있을까요?

impact0823 7년 전 0

dlaud5379 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말