Brave 문제 질문 (시간 초과, Java 구현)

  • mixnumg
    mixnumg

    안녕하세요 Brave 문제 관련해서 질문드립니다
    https://algospot.com/judge/problem/read/BRAVE

    (시간초과)

    문제에 대해 제가 이해하여 푼 방식은 아래와 같습니다

    1. Boom Class 구현
      1.1 Boom Class를 구현한 목적은 입력받는 boom들에 대한 연결고리 적용 (예를 들어, 1 2, 3 1 boom 을 입력받으면 1 -> 2 -> 3 의 연결고리 적용, 중복제거를 위해 Set 자료구조 사용)

    2. Boom array를 선언하여 입력 받는 boom 들에 대해 index가 작은 놈을 기준으로 연결고리 생성

    3. 입력을 다 받은 경우, size가 제일 큰 놈을 구하여 결과값 return

    ex) 1 2, 2 4, 3 2 를 입력받았을 경우
=====
Boom
=====
 1 -> 2
=====
 2 -> 4 3
=====
 3
=====
 4
=====

    코드를 구현 후 최악의 데이터 셋을 고려해봤을 때, 아래의 경우일꺼라고 가정, 입력 시 문제에서 요구하는 시간안에 구해지는 것 같았습니다.

    boom 데이터 구조
1 2 3 4  .... n
2 3 4 .... n-1
...
...
n-1 n
n

    질문은 다음과 같습니다
    1) 처음에 접근한 문제 풀이 방식이 잘못됐는지
    2) 자료구조를 잘못 사용하였는지
    3) 코드에서 더 빨라질 수 있는 조건이 있는지
    4) 기타 조언

    감사합니다.

    작성한 코드는 아래와 같습니다

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;


public class Main {
    private static BufferedReader in;
    private static int boomNumber = 0;
    private static int boomCount = 0;

    public static void main(String args[]) throws IOException {     
        in = new BufferedReader(new InputStreamReader(System.in));
        int loop = Integer.parseInt(in.readLine());

        for(int i = 0; i < loop; i++){
            String tmp[] = in.readLine().split(" ");
            boomNumber = Integer.parseInt(tmp[0]);
            boomCount = Integer.parseInt(tmp[1]);

            process();          
        }           
    }

    public static void process() throws IOException{

        Boom boom[] = new Boom[boomNumber+1];
        int startIndex = -1;

        for(int i = 0; i < boomCount; i++){
            String tmp[] = in.readLine().split(" ");
            int number1 = Integer.parseInt(tmp[0]);
            int number2 = Integer.parseInt(tmp[1]);

            if(boom[number1] == null){
                Boom boom1 = new Boom(number1);
                boom1.addboomList(boom1);
                boom[number1] = boom1;
            }

            if(boom[number2] == null){
                Boom boom2 = new Boom(number2);
                boom2.addboomList(boom2);
                boom[number2] = boom2;
            }

            if (number1 < number2){
                boom[number1].addboomList(boom[number2]);               
            }
            else{
                boom[number2].addboomList(boom[number1]);
            }
        }

        for(int index = 0; index < boom.length; index++){
            if(boom[index] == null)
                continue;

            if(boom[index].getboomList().size() == 1){
                startIndex = index;
                break;
            }               
        }

        if(startIndex == -1)
            startIndex = boom.length - 1;       

        int max = 1;
        for(int i = startIndex-1; i >= 0; i--){
            if(boom[i] == null)
                continue;

            Set<Boom> calcBoom = calcBoom(boom[i]);

            if(max < calcBoom.size()){
                max = calcBoom.size();              
            }
        }

        System.out.print(max);
    }

    public static Set<Boom> calcBoom(Boom boom){
        Set<Boom> resultBoom = new HashSet<Boom>();

        for(Boom subBoom : boom.getboomList()){
            resultBoom.addAll(subBoom.getboomList());
            subBoom.setBoomList(resultBoom);
        }

        boom.setBoomList(resultBoom);

        return resultBoom;
    }
}

class Boom{
    private Set<Boom> boomList;
    private int number;


    public Boom(int number){
        this.boomList = new HashSet<Boom>();
        this.number = number;
    }

    public int getNumber(){
        return number;
    }

    public void addboomList(Boom boom){
        this.boomList.add(boom);
    }

    public Set<Boom> getboomList(){
        return boomList;
    }

    public void setBoomList(Set<Boom> boomList){
        this.boomList = boomList;
    }
}

    7년 전
3개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    아이디어에 대해서는 맞는 것 같지만, 두개의 집합을 합칠 때 있어서 시간이 오래걸릴 것 같습니다. Set A에 set B를 추가하는 연산은 아마 O(|A|*log|B|) 의 시간 복잡도가 예상됩니다. 그리고 사용하신 자료구조에서는 상태를 저장하기 위해 불필요하게 많은 메모리를 사용하고 있는 것으로 보입니다. 다음 링크를 참고하시면 보다 효율적인 구현을 하실 수 있을 것으로 보이니 참고 바랍니다.
    https://en.wikipedia.org/wiki/Disjoint-set_data_structure


    7년 전 link
  • mixnumg
    mixnumg

    좋은 답변 감사합니다! ^^


    7년 전 link
  • mixnumg
    mixnumg

    덕분에 문제도 해결하고 개념도 하나 배워갑니다 감사합니다! ^^


    7년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.