글 읽기 - 도저히 이해가 되질 않네요

leejaengjaeng 6년 전 0

학생마다 연결된 목록을 찾아들어가면서 List에 기록하고

싸이클이 생기면(List에 포함되어있는 값을 다시 넣으려고하면)

list에 있는 학생중, 싸이클에 포함되지 않는 학생은 -1로 처리하고 포함되면 1로 처리하는 방식으로 풀어서 80%까지 채점됐는데

시간초과가 떴습니다.

그래서 시간이 걸릴 만한 부분이 어디일까 보던중 79번줄에 selected.contains(iWant) 여기가 반복마다 확인하려면 오래 걸릴꺼같아서

54번줄 아래에 boolean isSelected[] = new boolean[stNum+1]; 를 두고 isSelected[iWant]로 상수시간에 확인 하도록 하였습니다.

근데 제출하니깐 1%에서 시간초과가 뜨네요? 속도는 훨씬 빨라졌을 텐데

어디서 루프가 도는 걸까요? 입력문제일까요?

-> 루프 인지 확인하려고 while(true) 속에서 학생수 이상으로 반복 돌면 "dasdasd" 문자열 출력하게 했는데

"틀렸습니다"가 아니라 여전히 1%에서 시간초과가 나네요 도대체 무슨 경우에 걸려서 80%까지 가던게

boolean 배열로 상수시간 접근하니깐 1%에서 멈추는 건지 이해가 안되네요

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int testCase = Integer.parseInt(sc.nextLine());
     
        for(int tc=0;tc<testCase;tc++)
        {
            int stNum = Integer.parseInt(sc.nextLine());
             
            int students[] = new int[stNum+1];
            //1:팀, 0: 디폴트, -1:팀이 못됨
            int teamFlag[] = new int[stNum+1];
     
            //학생 입력
            String inputStr[] = sc.nextLine().split(" ");
            for(int i=1;i<=stNum;i++)
                students[i] = Integer.parseInt(inputStr[i-1]);
 
            // 팀 찾기
            for(int i=1;i<=stNum;i++)
            {           
                List<Integer> selected = new ArrayList<Integer>();
                boolean canMakeTeam = false;
                 
                int selectedSize=0;
                selected.add(i);
                //싸이클을 찾거나, 내가 팀이 되고 싶은 대상이 이미 팀에 포함되어 있을때 까지 탐색
                while(true)
                {
                    int iAm = selected.get(selectedSize);
                    int iWant = students[iAm];
 
                     
                    //이미 팀이 있거나, 팀이 될수 없는 사람을 고른 경우
                    if(teamFlag[iWant]!=0)
                    {
                        for(int st=0; st<selected.size(); st++)
                        {
                            int currentStudent = selected.get(st);
                             
                            if(teamFlag[currentStudent]!=0) continue;
                            else teamFlag[currentStudent]=-1;   
                        }
                        break;
                    }
                     
                    //selectedList에 포함 된 경우
                    if(selected.contains(iWant))
                    {
                        //어디까지 싸이클 인지 확인
                        int cycleStart = selected.indexOf(iWant);
                        for(int st=0;st<selected.size();st++)
                        {
                            int currentStudent = selected.get(st);
 
                            if(st<cycleStart)
                                teamFlag[currentStudent]=-1;
                            else
                                teamFlag[currentStudent]=1;
                        }
                        break;
                    }
                     
                    //둘다 아니면 리스트에 삽입
                    selected.add(iWant);
                    selectedSize++;
                }
            }
             
            //팀이 없는 학생 확인
            int loser=0;
            for(int i=1;i<=stNum;i++)
                if(teamFlag[i]==-1) loser++;
             
            System.out.println(loser);
        }
    }
}

zlzmsrhak 6년 전 1

1. 확인된 점을 확인하는 부분에서, teamflag의 값은 -1도 가능하기 때문에 그부분을 확인해야 할 것 같습니다.

2. 말씀하신대로 79번 줄이 남아있으면 N^2이 될 것 같고, boolean 배열을 써야 하는 것 같습니다. 다만 구현상에서 문제가 생겨 시간초과가 나는 것 같습니다.

leejaengjaeng 6년 전 0

감사합니다 ㅎㅎ
boolean 배열을 사용하는건 계속 1%에서 시간초과 나서 같은위치에 map을 사용해서 꾸역꾸역 풀었습니다
boolean 배열을 쓰면 뭐가 문제였을까요??
아래는 boolean배열을 사용한 코드입니다

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int testCase = Integer.parseInt(sc.nextLine());
     
        for(int tc=0;tc<testCase;tc++)
        {
            int stNum = Integer.parseInt(sc.nextLine());
             
            int students[] = new int[stNum+1];
            //1:팀, 0: 디폴트, -1:팀이 못됨
            int teamFlag[] = new int[stNum+1];
     
            //학생 입력
            String inputStr[] = sc.nextLine().split(" ");
            for(int i=1;i<=stNum;i++)
                students[i] = Integer.parseInt(inputStr[i-1]);
 
            // 팀 찾기
            for(int i=1;i<=stNum;i++)
            {
                //예외처리
                 
                //1. 확인 된 점이면 넘기기
                if(teamFlag[i]==1) continue;
                //2. 내가 하고 싶은 친구와 팀 못하면 넘기기
                if(teamFlag[students[i]]!=0)
                {
                    teamFlag[i]=-1;
                    continue;
                }
                //3. 혼자하고 싶으면 넘기기
                if(i == students[i])
                {
                    teamFlag[i]=1;
                    continue;
                }
 
                List<Integer> selected = new ArrayList<Integer>();
                boolean isSelected[] = new boolean[stNum+1];
                 
                int beforeSelect=i;
                selected.add(i);
                isSelected[i]=true;
                //싸이클을 찾거나, 내가 팀이 되고 싶은 대상이 이미 팀에 포함되어 있을때 까지 탐색
                while(true)
                {                   
                    int iWant = students[beforeSelect];
 
                    //이미 팀이 있거나, 팀이 될수 없는 사람을 고른 경우
                    if(teamFlag[iWant]!=0)
                    {
                        for(int st=0; st<selected.size(); st++)
                        {
                            int currentStudent = selected.get(st);
                             
                            if(teamFlag[currentStudent]!=0) continue;
                            else teamFlag[currentStudent]=-1;   
                        }
                        break;
                    }
                     
                    //selectedList에 포함 된 경우
                    else if(isSelected[iWant])
                    {
                        //어디까지 싸이클 인지 확인
                        int cycleStart = selected.indexOf(iWant);
                        for(int st=0;st<selected.size();st++)
                        {
                            int currentStudent = selected.get(st);
 
                            if(st<cycleStart)
                                teamFlag[currentStudent]=-1;
                            else
                                teamFlag[currentStudent]=1;
                        }
                        break;
                    }
                     
                    //둘다 아니면 리스트에 삽입
                    else
                    {
                        selected.add(iWant);
                        isSelected[iWant]=true;
                        beforeSelect=iWant;
                    }
                }
            }
             
            //팀이 없는 학생 확인
            int loser=0;
            for(int i=1;i<=stNum;i++)
                if(teamFlag[i]==-1) loser++;
             
            System.out.println(loser);
        }
    }
}

zlzmsrhak 6년 전 1

앞쪽에 큰 데이터가 있는것인지는 모르겠지만, isSelected 배열을 N번 선언하기 때문에 N^2 시간복잡도를 가지게 되어 시간초과가 나는 것 같습니다.

leejaengjaeng 6년 전 0

오 그러면 전역으로 선언하고 넣고 빼는 식으로 테스트 해보겠습니다~!

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

문제

문제

출처

ICPC

도저히 이해가 되질 않네요

leejaengjaeng 6년 전 0

zlzmsrhak 6년 전 1

leejaengjaeng 6년 전 0

zlzmsrhak 6년 전 1

leejaengjaeng 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말