백준[JAVA] 9345번 디지털 비디오 디스크(DVDs)

https://www.acmicpc.net/problem/9345

9345번: 디지털 비디오 디스크(DVDs)

요새 세그먼트 트리만 풀고있는데 좋은 문제를 발견하여 풀이를 공유합니다!

 

 

전형적인 세그먼트트리 문제입니다. 

i와 k가 주어진다면 A[i]~A[k] 범위에서 순서에 상관없이 범위내의 숫자가 존재하는지 물어보는 문제입니다!

혼자 처음에는 어떻게 풀어야하나 고민을 많이 했습니다.

머지소트트리 문제처럼 각 노드의 부모를 노드끼리 리스트로 만들어서 확인할려했지만 너무 배보다 배꼽이 큰거같아 

포기했습니다.

그러다가  a~b 범위내 숫자가 모두 존재할려면 최솟값이 a,최댓값이 b면 된다는 아이디어가 떠올라서

최소세그먼트트리와 최대세그먼트트리를 이용하여 문제를 풀었습니다.

예를 들어 2~5 범위에 2,3,4,5가 모두 존재할려면 2~5의 최솟값은 2 최대값은 5이면 됩니다. 만일 3이 아니라 7이면 최대값이 7이되므로 NO가 되기때문입니다.

package main;
 
 
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
 
import java.util.List;
class Main {
    static int size;
    static int first;
    static int[] mintree;
    static int[] maxtree;
    static int[] minarr;
    static int[] maxarr;
    static int logn;
    public static void main(String[] args) throws IOException {
        
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int test=Integer.parseInt(br.readLine());
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<test;i++) {
            StringTokenizer st=new StringTokenizer(br.readLine());
            size= Integer.parseInt(st.nextToken());
            int line=Integer.parseInt(st.nextToken());
            logn=0;
            for(int j=1;j<size;j*=2) {
                logn++;
                
            }
            
            minarr=new int[size+1];
            maxarr=new int[size+1];
            minarr[size]=Integer.MAX_VALUE;
            
            maxarr[size]=Integer.MIN_VALUE;
            mintree=new int[(int)Math.pow(2, logn+1)];
            maxtree=new int[mintree.length];
            Arrays.fill(mintree, size);
            Arrays.fill(maxtree, size);
            first=mintree.length/2;
            
            for(int j=0;j<size;j++) {
                minarr[j]=j;
                maxarr[j]=j;
                mintree[first+j]=j;
                maxtree[first+j]=j;
            }
            
            mininit(1);
            maxinit(1);
            for(int j=0;j<line;j++) {
                st=new StringTokenizer(br.readLine());
                int choice=Integer.parseInt(st.nextToken());
                
                if(choice==0) {
                    int temp1=Integer.parseInt(st.nextToken());
                    int answer1=minarr[temp1];
                    int temp2=Integer.parseInt(st.nextToken());
                    int answer2=minarr[temp2];
                    minarr[temp1]=answer2;
                    minarr[temp2]=answer1;
                    maxarr[temp1]=answer2;
                    maxarr[temp2]=answer1;
                    minupdate(first+temp1);
                    minupdate(first+temp2);
                    maxupdate(first+temp1);
                    maxupdate(first+temp2);
                }
                else {
                    int temp1=Integer.parseInt(st.nextToken());
                    int temp2=Integer.parseInt(st.nextToken());
                    int result1=minarr[minfind(first+temp1, first+temp2)];
                    int result2=maxarr[maxfind(first+temp1, first+temp2)];
                    if(result1==temp1&&result2==temp2) {
                        sb.append("YES").append("\n");
                    }else sb.append("NO").append("\n");
                }
                
                
                
            }
            
        
            
            
            
            
            
            
        }
        System.out.println(sb);
        
        
    }
    static int maxfind(int start, int end) {
        int result=maxtree[start];
        while(end>=start) {
            if(end==start) {
                if(maxarr[result]<maxarr[maxtree[start]]) {
                     result=maxtree[start];
                }
                return result;
            }
            if(start%2==1) {
                if(maxarr[result]<maxarr[maxtree[start]]) {
                result=maxtree[start];
                }
                start++;
            }
            if(end%2==0) {
                if(maxarr[result]<maxarr[maxtree[end]]) {
                result=maxtree[end];
                }
                end--;
            }
            start/=2;
            end/=2;
        }
        return result;
    }
    static int minfind(int start,int end) {
        int result=mintree[start];
        while(end>=start) {
            if(end==start) {
                if(minarr[result]>minarr[mintree[start]]) {
                    return result=mintree[start];
                }
            }
            if(start%2==1) {
                if(minarr[result]>minarr[mintree[start]]) {
                result=mintree[start];
                }
                start++;
            }
            if(end%2==0) {
                if(minarr[result]>minarr[mintree[end]]) {
                result=mintree[end];
                }
                end--;
            }
            start/=2;
            end/=2;
        }
        return result;
    }
    static void maxupdate(int index) {
        int temp=index/2;
        while(temp!=0) {
        if(maxarr[maxtree[temp*2]]>=maxarr[maxtree[temp*2+1]]) {
             maxtree[temp]=maxtree[temp*2];
        }else  maxtree[temp]=maxtree[temp*2+1];
        temp/=2;}
    }
    static void minupdate(int index) {
        int temp=index/2;
        while(temp!=0) {
            if(minarr[mintree[temp*2]]<=minarr[mintree[temp*2+1]]) {
                 mintree[temp]=mintree[temp*2];
            }else  mintree[temp]=mintree[temp*2+1];
 
            
            temp/=2;
        }
    }
    static int mininit(int index) {
        if(index>=first/2) {
            if(minarr[mintree[index*2]]<=minarr[mintree[index*2+1]]) {
                return mintree[index]=mintree[index*2];
            }else return mintree[index]=mintree[index*2+1];
            
        }
        if(minarr[mininit(index*2)]<=minarr[mininit(index*2+1)]) {
            
            return mintree[index]=mintree[index*2];
        }else return mintree[index]=mintree[index*2+1];
        
    }
    static int maxinit(int index) {
        if(index>=first/2) {
            if(maxarr[maxtree[index*2]]>=maxarr[maxtree[index*2+1]]) {
                return maxtree[index]=maxtree[index*2];
            }else return maxtree[index]=maxtree[index*2+1];
            
        }
        if(maxarr[maxinit(index*2)]>=maxarr[maxinit(index*2+1)]) {
            
            return maxtree[index]=maxtree[index*2];
        }else return maxtree[index]=maxtree[index*2+1];
        
    }
    
    
    }
 
 
 
 
 
 
 

 

 

최소세그먼트트리 최대세그먼트트리를 만들어 준후 0일때는 값을 바꿔주고 바뀐 인덱스끼리 범위에서 다시 트리를 업데이트 해줬습니다

1일때는 범위내에 최대값 최소값을 찾아주어 문제를 해결하였습니다.

더 좋은 풀이가 있으면 댓글달아주세요!!!!감사합니다