글 읽기 - 자꾸 시간초과가 나요..

whddnr0218 6년 전 0

ㅠㅠ 살려주세요..

제가 생각했을 때는 시간 복잡도가 O(n)인 거 같은데 자꾸 시간초과가 나요..ㅜㅜ

import java.io.*;
import java.util.*;

class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(input.readLine());
        
        LinkedList<Integer> target = new LinkedList<Integer>();
        LinkedList<Integer> condition = new LinkedList<Integer>();
        
        StringTokenizer st1 = new StringTokenizer(input.readLine());
        StringTokenizer st2 = new StringTokenizer(input.readLine());
        for (int i = 0; i < n; i++){
            target.offerLast(Integer.parseInt(st1.nextToken()));
            condition.offerLast(Integer.parseInt(st2.nextToken()));
        }
        //////////////////////////////// 입력 끝
        while (condition.indexOf(target.peekFirst()) != 0){ // target과 condition의 첫 원소를 맞춥니다
            condition.offerLast(condition.pollFirst());
        }
        
        boolean isGoodPuzzle = true; // good puzzle 판단 불리언
        
        for (int i = 1; i < n; i++){
            if (target.get(i) != condition.get(i)){ // index 1부터 n - 1까지 같으면 good puzzle
                isGoodPuzzle = false;
                break;
            }
        }
        
        if (!isGoodPuzzle){ // 만약 아까 good puzzle이 아니라면,
        	isGoodPuzzle = true;
        	
        	int temp = condition.pollFirst(); 
            condition = reverseList(condition); // 첫 값을 제외한 값을 뒤집어줍니다
            condition.addFirst(temp);
            
            for (int i = 1; i < n; i++){
                if (target.get(i) != condition.get(i)){ // 다시 비교
                    isGoodPuzzle = false;
                    break;
                }
            }
        }
        
        System.out.println(isGoodPuzzle ? "good puzzle" : "bad puzzle"); // 출력
    }
    
    public static LinkedList<Integer> reverseList (LinkedList<Integer> arr){ // 뒤집는 메소드
        LinkedList<Integer> target = new LinkedList<Integer>();
        
        while(!arr.isEmpty()){
            target.offerLast(arr.pollLast());
        }
        
        return target;
    }
}

jh05013 6년 전 1

Linked List가 어떻게 작동하는지 알아 보세요. i번째 원소를 찾는 데 O(i)가 걸립니다.

whddnr0218 6년 전 0

LinkedList를 ArrayList로 변환하는 함수를 하나 만들어서 ArrayList로 get 메소드를 호출했습니다.

근데도 시간 초과는 없어지지가 않네요..ㅜㅜ

ArrayList<Integer> targetarr = convertList(target);
ArrayList<Integer> conditionarr = convertList(condition);

for (int i = 1; i < n; i++){
    if (targetarr.get(i) != conditionarr.get(i)){
        isGoodPuzzle = false;
        break;
    }
}

public static ArrayList<Integer> convertList(LinkedList<Integer> arr){
    ArrayList<Integer> target = new ArrayList<Integer>();
    
    target.add(arr.pollFirst());
    
    return target;
}

jh05013 6년 전 1

문제가 더 있습니다.

        while (condition.indexOf(target.peekFirst()) != 0){
            condition.offerLast(condition.pollFirst());
        }

whddnr0218 6년 전 0

도와주셔서 감사합니다..

서로 첫 원소를 peek해서 일치하지 않으면 밀도록 바꿔봤는데

아직도...

죄송합니다....

        while (condition.peekFirst() != target.peekFirst()){
            condition.offerLast(condition.pollFirst());
        }

jh05013 6년 전 1

그런데 예제는 돌아가나요?

https://ideone.com/1thZpP

whddnr0218 6년 전 0

convertList 메소드에 반복문을 빼먹었네요..

자꾸 실수하게 되는 거 같습니다..

근데 반복문 넣고 해봐도 자꾸 시간 초과가 나서

그냥 다른 방법으로 배열만 써서 풀었습니당..

지금까지 알려주셔서 감사합니다

import java.io.*;
import java.util.*;

class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(input.readLine());
        if (n < 4){
            System.out.println("good puzzle");
            return;
        }
        
        int[] target = new int[n];
        int[] condition = new int[n];
        StringTokenizer st1 = new StringTokenizer(input.readLine());
        StringTokenizer st2 = new StringTokenizer(input.readLine());
        for (int i = 0; i < n; i++){
            target[i] = Integer.parseInt(st1.nextToken());
            condition[i] = Integer.parseInt(st2.nextToken());
        }
        
        int conditionIndex = 0;
        
        for (int i = 0; i < n; i++){ // O(n)
            if (condition[i] == target[0]){
                conditionIndex = i;
                break;
            }
        }
        
        boolean isGoodPuzzle = true;
        
        int tempIndex = conditionIndex;
        for (int targetIndex = 0; targetIndex < n; targetIndex++){ // O(n)
            
            if (condition[tempIndex] != target[targetIndex]){
                isGoodPuzzle = false;
                break;
            }
            tempIndex++;
            if (tempIndex == n){
                tempIndex = 0;
            }
        }
        
        if (!isGoodPuzzle){
            isGoodPuzzle = true;
            tempIndex = conditionIndex;
            for (int targetIndex = 0; targetIndex < n; targetIndex++){ // O(n)
                
                if (condition[tempIndex] != target[targetIndex]){
                    isGoodPuzzle = false;
                    break;
                }
                tempIndex--;
                if (tempIndex == -1){
                    tempIndex = n - 1;
                }
            }
        }
        
        System.out.println(isGoodPuzzle ? "good puzzle" : "bad puzzle");
    }
}

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

문제

문제

출처

ICPC

자꾸 시간초과가 나요..

whddnr0218 6년 전 0

jh05013 6년 전 1

whddnr0218 6년 전 0

jh05013 6년 전 1

whddnr0218 6년 전 0

jh05013 6년 전 1

whddnr0218 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말