Kruskal (MST) Really Special Subtree

31 Mar 2019 Tags:

HackerRank, Kruskal MST, Prim's MST, Mininal Spanning Tree

HackerRank link

Kruskal (MST): Really Special Subtree

풀이 핵심

Kruskal 알고리즘에 대해 잘 이해하고 있다.
해당 문제는 그래프에서 subtree 중 최소 가중치를 원하고 있다.
Kruskal 알고리즘을 잘 알고 있는 경우 쉽게 풀린다.

※ MST(Minimal Spanning Tree : 최소 신장 트리) 알고리즘은 대표적으로 Kruskal MST와 Prim’s MST가 있다.

둘다 Greedy 알고리즘의 일종이지만,
Prim’s 알고리즘은 트리를 greedy하게 만들고(계속 이어 붙임),
Kruskal은 엣지를 greedy하게 Tree를 만든다(만들다가 이어 붙임).

Algorithm

입력을 우선순위 큐를 이용하여 정렬한다.
모든 노드에 대해 검색을 한다.
우선순위 큐에서 노드를 받는다. (최소의 가중치)
트리가 그래프가 되지 않도록 한다.
4-1. 최상위 부모 노드를 파악한다. (find)
4-2. 최상위 부모 노드가 같다면, 연결이 되므로 패스
4-3. 같지 않다면 연결한다. (union)

아래 코드는 해당 문제를 kruskal과 prim’s 모두 이용해 풀었는데..
항상 주의 할 것이 입력 조건에서 간선의 weight 조건이.. 0이 포함되어 있는지 꼭 확인 할것…
prim’s 알고리즘 구현하면서 처음에 ArrayList가아닌 배열로 구현하면서 무게 조건이 0인경우 패스라고 했다가 큰 낭패를 봤었음…..

Source Code

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

class Result {

    static public class Node implements Comparable<Node>
    {
        int start;
        int end;
        int weight;
        
        Node(int start, int end, int weight)
        {
            super();
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            // TODO Auto-generated method stub
            return  o.weight >= this.weight ? -1 : 1; 
        }
    }

    public static int prim(int gNodes, List<Integer> gFrom, List<Integer> gTo, List<Integer> gWeight) {
        int minWeight = 0;
    
        // map 만들기
        ArrayList<Node> map[] = new ArrayList[gNodes+1];
        
        for(int i = 0 ; i < map.length; i++)
        {
            map[i] = new ArrayList<>();
        }
        
        Iterator[] it = new Iterator[3];
        it[0] = gFrom.iterator();
        it[1] = gTo.iterator();
        it[2] = gWeight.iterator();
        
        while(it[0].hasNext())
        {
            int start = (int)it[0].next();
            int end = (int)it[1].next();
            int weight = (int)it[2].next();
            
            map[start].add(new Node(start,end,weight));
            map[end].add(new Node(end,start,weight));
        }
        
        PriorityQueue<Node> minWeigtQue = new PriorityQueue<>();
        Queue<Integer> haveToSearch = new LinkedList<>(); 
        boolean[] isMoved = new boolean[gNodes+1];
        
        haveToSearch.add(1);
                    
        while(haveToSearch.isEmpty() == false)
        {
            // 서치 큐에서 현재 서치를 해야 하는 시작점을 받아 온다.
            int start = haveToSearch.poll();
            ArrayList tempList = map[start];
            
            // 이동한 곳은 이동했다는 표시를 한다.
            isMoved[start] = true;
            
            // 이미 이동했던 곳을 제외하고 현재 노드에서의 이동 가능한 모든 경로를 찾는다.
            for(int i = 0 ; i < tempList.size() ; i++)
            {                
                Node tempNode = (Node)tempList.get(i);
                
                // 이동안한곳이라면..
                if(isMoved[tempNode.end] == false)
                {
                    // if(debugPrint) System.out.print("("+i+")");
                    // 만약 있다면, 우선순위 큐에 넣는다.
                    minWeigtQue.add(tempNode);
                }            
            }
            
            // 모두 다 넣었으면, 이중 가장 최단길을 우선순위 큐에서 뽑아 낸다.                
            while(minWeigtQue.isEmpty() == false)
            {
                Node temp = minWeigtQue.poll();
                int next = temp.end;
                
                // 중복을 방지하기 위해서, 이미 이동한 값은 무시한다.
                if(isMoved[next] == true) continue;
                
                minWeight += temp.weight;
                // if(debugPrint) System.out.println("->"+temp.end+"("+temp.weight+")");
                if(debugPrint) System.out.println(temp.weight);
                
                haveToSearch.add(next);
                break;
            }
        }

        return minWeight;
    }
    /*
     * Complete the 'kruskals' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts WEIGHTED_INTEGER_GRAPH g as parameter.
     */

    /*
     * For the weighted graph, <name>:
     *
     * 1. The number of nodes is <name>Nodes.
     * 2. The number of edges is <name>Edges.
     * 3. An edge exists between <name>From[i] and <name>To[i]. The weight of the edge is <name>Weight[i].
     *
     */
    static boolean debugPrint = false;
    
    public static void printParents(int[] parents)
    {
        if(debugPrint == false) return;
        
        for(int i = 0 ; i < parents.length; i++)
        {
            System.out.print(i+":"+parents[i]+"->");            
        }
        System.out.println();
    }
    
    // 부모 노드에 대해 탐색한다.
    public static int find(int[] parents, int a)
    {
        if(parents[a] == a) 
        {
            return a;
        }
        else
        {
            parents[a] =  find(parents, parents[a]);    // 검색할때마다 최상위 부모를 다시 설정. ( 검색 시 마다의 성능 향상을 위함)
            return parents[a];
        }
    }
    
    // 합친다.
    public static void union(int[] parents, int a, int b)
    {
        int rootA = find(parents, a);
        int rootB = find(parents, b);
        
        // 각각의 루트가 같은 경우 합칠 필요가 없음.
        if( rootA == rootB ) return;
        
        // 다르면 재 설정한다.
        parents[rootA] = rootB;
    }
    
    public static int kruskals(int gNodes, List<Integer> gFrom, List<Integer> gTo, List<Integer> gWeight) {
        int minWeight = 0;
        
        // 1. 데이터를 넣으면서 바로바로 가중치가 낮은 큐를 우선으로 하기 위해 우선순위 큐를 만든다.
        PriorityQueue<Node> que = new PriorityQueue<>();
        
        Iterator<Integer> it[] = new Iterator[3]; 
        it[0] = gFrom.iterator();
        it[1] = gTo.iterator();
        it[2] = gWeight.iterator();
        
        while(it[0].hasNext())
        {
            int start = it[0].next();
            int end = it[1].next();
            int weight = it[2].next();
            que.add(new Node(start, end , weight));
        }
        
        int nodes = que.size() + 1;
        
        // 부모 노드는 일단 연결하기 전이기 때문이니 자기 자신으로 지정.
        int[] parents = new int[nodes];
        for(int i = 0; i < parents.length; i++)
        {
            parents[i] = i;
        }
        
        // 모든 노드에 대해 검색 한다.        
        for(int i = 0 ; i < nodes - 1 ; i++)
        {
            printParents(parents);
            // 최소가 되는
            Node node = que.poll();
            int start = node.start;
            int end = node.end;
            
            // 서브 트리의 연결 시 연결이 되어 그래프 구조가 되면 안되기 때문에, 
            // 최상위 부모가 같은지 체크 한다.
            int rootStart = find(parents, start);
            int rootEnd = find(parents, end);
            
            if(debugPrint) System.out.print(start+"("+rootStart+")"+"->"+end+"("+rootEnd+")");
            
            // 그리고 부모가 같은 경우는 서로 연결되어 있는것이 아니므로, 다음으로 넘어간다. 
            if( rootStart == rootEnd ) 
            {
                System.out.println();
                continue;
            }
            
            if(debugPrint) System.out.println(":"+node.weight);
            
            // 부모가 서로 다른경우에는 서로 합친다. ( 부모를 같이 한다. ex) 3 -> 4로 이동하는 경우 3과 4 모두 최상위 노드가 
            minWeight += node.weight;
            union(parents, start, end);
        }        
        
        return minWeight;
    }


}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] gNodesEdges = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int gNodes = Integer.parseInt(gNodesEdges[0]);
        int gEdges = Integer.parseInt(gNodesEdges[1]);

        List<Integer> gFrom = new ArrayList<>();
        List<Integer> gTo = new ArrayList<>();
        List<Integer> gWeight = new ArrayList<>();

        for (int i = 0; i < gEdges; i++) {
            String[] gFromToWeight = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

            gFrom.add(Integer.parseInt(gFromToWeight[0]));
            gTo.add(Integer.parseInt(gFromToWeight[1]));
            gWeight.add(Integer.parseInt(gFromToWeight[2]));
        }

        //int res = Result.kruskals(gNodes, gFrom, gTo, gWeight);
        int res = Result.prim(gNodes, gFrom, gTo, gWeight);        

        // Write your code here.
        bufferedWriter.write(String.valueOf(res));
        // System.out.println(res);

        bufferedReader.close();
        bufferedWriter.close();
    }
}

KnightL on a Chessboard

24 Feb 2019 Tags:

HackerRank, Breadth First Search

HackerRank link

KnightL on a Chessboard

풀이 핵심

BFS 알고리즘에 대해 잘 이해하고 있다.
해당 문제에서 체크 말을 목적지까지 이동 시 소요되는 최단 거리를 원하고 있다.

Algorithm

함수 두개를 이용하여 구현한다.

BFS를 구현한 함수.
ab를 각각 1 ~ n-1 까지 증가 시키면서 BFS의 결과를 받는 함수.

Source Code

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

	static public class Point 
	{
		int x,y;
		Point()
		{
			x = 0;
			y = 0;
		}
		
		Point(int _x, int _y)
		{
			x = _x;
			y = _y;
		}
		
	}
	
	static void printSteps(int[][] steps)
	{
		System.out.println();
		for(int i = 0 ; i < steps.length ; i++)
		{
			for(int j = 0 ; j < steps.length ; j++)
			{
				System.out.print(steps[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	
    // Complete the knightlOnAChessboard function below.
	static int BreathFirstSearch(int n, int a, int b)
	{
		boolean debugPrint = false;
		
		Point p;
		
		Queue<Point> que = new LinkedList<Point>();
		int[][] steps = new int[n][n];
		
		
		int[][] dir = {
				{+a,+b}, {+a,-b}, {-a,+b}, {-a,-b},
				{+b,+a}, {+b,-a}, {-b,+a}, {-b,-a}
		};
		
		if((a == 1) && (b == 1)) return n - 1;
		
		if(a == (n - 1) && b == (n - 1)) return 1;
		
		que.add(new Point());
		steps[0][0] = 1;
		
		while(que.isEmpty() == false)
		{
			p = que.poll();
			
			if(debugPrint) System.out.print("(poll:"+p.x+","+p.y+") >> ");
			
			int curStep = steps[p.x][p.y] + 1;
			
			if(debugPrint) System.out.print("steps:" + curStep + " ");
			
			for(int i = 0 ; i < dir.length ; i++)
			{
				// new point
				int x = p.x + dir[i][0];
				int y = p.y + dir[i][1];
				
				// check limits
				if( x < 0 || y < 0) continue;
				if( x >= n || y >= n) continue;
				
				// check duplicated
				if(steps[x][y] == 0)
				{
					// check goal
					if( x == n - 1 && y == n - 1) 
					{
						steps[x][y] = curStep;
						if(debugPrint) printSteps(steps);
						return curStep - 1;						
					}
						
					steps[x][y] = curStep;
					que.add(new Point(x,y));
					
					if(debugPrint) System.out.print("("+x+","+y+") -> ");
					
				}			
			}
			
			if(debugPrint) System.out.println();
		}
		
		if(debugPrint) System.out.println("\n==================================");
		
		return -1;
	}
	
	
    static int[][] knightlOnAChessboard(int n) {
    	int[][] result = new int[n - 1][n - 1];
    	
    	
    	for(int a = 1 ; a < n ; a++)
    	{
    		for(int b = 1 ; b < n ; b++)
    		{
    			result[a-1][b-1] = BreathFirstSearch(n,a,b);
    		}
    	}
    	
    	return result;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        // BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        int[][] result = knightlOnAChessboard(n);

        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                // bufferedWriter.write(String.valueOf(result[i][j]));
            	System.out.print(String.valueOf(result[i][j]));

                if (j != result[i].length - 1) {
                    // bufferedWriter.write(" ");
                	System.out.print(" ");
                }
            }

            if (i != result.length - 1) {
                // bufferedWriter.write("\n");
            	System.out.print("\n");
            }
        }

        // bufferedWriter.newLine();

        // bufferedWriter.close();

        scanner.close();
    }
}

02 Jun 2019 Tags:

HackerRank link

Breadth First Search: Shortest Reach

풀이 핵심

BFS 알고리즘에 대해 잘 이해하고 있다.
단순 BFS 구현 문제

Algorithm

BFS를 구현한다.

Source Code

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the bfs function below.
	/*
	 * n: the integer number of nodes
	 * m: the integer number of edges
	 * edges: a 2D array of start and end nodes for edges
	 * s: the node to start traversals from
	 */
    static int[] bfs(int n, int m, int[][] edges, int s) {
    	boolean debugPrint = true;
    	// edge data    	
    	ArrayList<Integer>[] edge = new ArrayList[n+1];
    	for(int i = 0 ; i < edge.length ; i++)
    	{
    		edge[i] = new ArrayList<>();
    	}
    	
    	for(int i = 0; i < edges.length; i++)
    	{
    		edge[edges[i][0]].add(edges[i][1]);
    		edge[edges[i][1]].add(edges[i][0]);
    	}
    	
    	int[] moved = new int[n+1];
    	Queue<Integer> que = new LinkedList<Integer>();
    	
    	que.add(s);
    	moved[s] = 0;
    	
    	while(que.isEmpty() == false)
    	{
    		int cur = que.poll();
    		int curStep = moved[cur] + 1;
    		
    		if(debugPrint) System.out.print("("+cur+") ");
    		
    		for(int i = 0 ; i < edge[cur].size() ; i++)
    		{
    			int temp = edge[cur].get(i);
    			if(moved[temp] == 0)
    			{
    				que.add(temp);
    				moved[temp] = curStep;
    				if(debugPrint) System.out.print(" "+temp+" -> ");
    			}
    		}
    		
    		if(debugPrint) System.out.println();
    		
    	}
    	
    	int[] result = new int[n-1];
    	int idx = 0;
    	for(int i = 1 ; i < moved.length; i++)
    	{
    		if((i) != s )
    		{
    			result[idx] = moved[i] == 0 ? -1 : (moved[i]) * 6;
    			idx++;
    		}
    	}
    	
    	return result;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
//        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int qItr = 0; qItr < q; qItr++) {
            String[] nm = scanner.nextLine().split(" ");

            int n = Integer.parseInt(nm[0]);

            int m = Integer.parseInt(nm[1]);

            int[][] edges = new int[m][2];

            for (int i = 0; i < m; i++) {
                String[] edgesRowItems = scanner.nextLine().split(" ");
                scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

                for (int j = 0; j < 2; j++) {
                    int edgesItem = Integer.parseInt(edgesRowItems[j]);
                    edges[i][j] = edgesItem;
                }
            }

            int s = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] result = bfs(n, m, edges, s);

            for (int i = 0; i < result.length; i++) {
//                bufferedWriter.write(String.valueOf(result[i]));
            	System.out.print(String.valueOf(result[i]));

                if (i != result.length - 1) {
//                    bufferedWriter.write(" ");
                	System.out.print(" ");
                }
            }

//            bufferedWriter.newLine();
            System.out.println();
        }

//        bufferedWriter.close();

        scanner.close();
    }
}

List

15 Jan 2019 Tags:

Data Structure, List, Java

List

List는 자료를 순서대로 저장하는 자료구조이다.

대표적으로는 배열을 이용하여 구현하는 ArrayList와 Pointer를 이용하여 구현하는 LinkedList가 있다.

ArrayList

ArrayList는 배열을 이용하여 구현한다. 배열을 이용하여 구현하기 때문에 하기의 장단점이 있다.

장점 : 각 원소들을 접근하는데 매우 빠르다.
단점 : 삭제, 추가 시 많은 부하가 걸린다.

ex)

삭제 : 크기가 1000개의 ArrayList에서 0번째 메모리 삭제 시 999번의 데이터 이동이 필요.
삽입 : 크키가 1000개의 ArrayList에서 0번째에 추가 시 기존 1000개의 데이터 이동이 필요.
추가 : 원래 할당 된 사이즈 보다 더 큰 사이즈가 필요한 경우, 새로 메모리 할당 및 복사하는 과장이 필요.

LinkedList

LinkedList는 Pointer를 이용하여 구현한다. Pointer를 이용하여 구현하기 때문에 하기의 장단점이 있다.
장점 : 삭제, 추가 시 부하가 매우 적다. (새로 메모리 할당 후 Link). 메모리
단점 : 각 원소들을 접근하는데 매우 느리다.

ex) 1000번 중 999 번째의 데이터를 찾기 위해서는 0번째부터 순차적으로 1번째 데이터 Node로 가고 다음 링크를 타서 2번쨰 데이터 Node가고 …

ArrayList vs LinkedList

ArrayList와 LinkedList 성능표

	ArrayList	LinkedList
indexing	O(1)	O(n)
Insert/delete at beginning	O(n)	O(1)
Insert/delete at end	O(1)	O(1)
Insert/delete in middle	O(n)	search time + Θ(1)

Iterator

자바에서는 List의 순회에 사용할 수 있는 Iterator 클래스를 제공함.
아래 코드처럼 사용

Iterator it;

it = myList.iterator();

while(it.hasNext())
{
    System.out.println(it.next());
}

몇가지 퍼포먼스 테스트

ArrayList에서 메모리 Overflow시 얼마나 많은 부하가 있는지, 그리고 Iterator 사용의 이점에 대해 몇 가지 테스트 해보았다.

테스트 대상 자료형
ArrayList
ArrayList (미리 사이즈 할당)
LinkedList

테스트 내역
List의 추가/삽입 (마지막, 처음)
서치 테스트 (메소드를 이용, Iterator를 이용)

테스트 결과

이론적으로 보았던, 삽입/추가 시 ArrayList는 매우 성능이 떨어졌다.
하지만, 데이터 순회에서는 강점을 보였다.

(단위 ms)  
1. 메모리 추가 테스트  
▶ 마지막 추가 : 데이터 10000000개
- not allocated list add time: 1983  
- allocated list add time: 526  
- linked list add time: 4581  

▶ 처음에 추가 : 데이터 100000개  
- not allocated list add time: 1002  
- allocated list add time: 1050  
- linked list add time: 6  

2. 서치 테스트
- ArrayList iterator time: 8  
- ArrayList direct search time: 5  
- linkedList iterator search time: 76   
- linkedList 직접 서치하는 경우.. 20분째 결과가 안나옴

결론

메모리 할당
ArrayList에서 미리 메모리 할당이 가능하다면 할당한다.
데이터 순회
Iterator의 경우 한번 거쳐가기 때문에, ArrayList의 경우 직접하는게 빠르다.
하지만, LinkedList의 경우 Iterator를 사용하는 것이 매우 빠른 속도를 보인다.

테스트 코드

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class test {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int size = 10000000;
		//int size = 100000;
		//int size = 100;
		
		List<Integer> notAllocatedList = new ArrayList<>();
		List<Integer> allocatedList = new ArrayList<>(size);	// 메모리 사이즈를 미리 할당한다.
		List<Integer> linkedList = new LinkedList<>();
				
		long start;
		
		start = System.currentTimeMillis();
		for(int i = 0 ; i < size ; i++)
		{
			notAllocatedList.add(i);
		}
		System.out.println("not allocated list add time: "+(System.currentTimeMillis() - start));
		
		start = System.currentTimeMillis();
		for(int i = 0 ; i < size ; i++)
		{
			allocatedList.add(i);
		}
		System.out.println("allocated list add time: "+(System.currentTimeMillis() - start));
		
		start = System.currentTimeMillis(); 
		for(int i = 0 ; i < size ; i++)
		{
			linkedList.add(i);
		}
		System.out.println("linked list add time: "+(System.currentTimeMillis() - start));
		
		notAllocatedList.clear();
		allocatedList.clear();
		linkedList.clear();
		
		allocatedList = new ArrayList<>(size);	// 메모리 사이즈를 미리 할당한다.
		
		start = System.currentTimeMillis();
		for(int i = 0 ; i < size ; i++)
		{
			notAllocatedList.add(0, i);
		}
		System.out.println("not allocated list add time: "+(System.currentTimeMillis() - start));
		
		start = System.currentTimeMillis();
		for(int i = 0 ; i < size ; i++)
		{
			allocatedList.add(0, i);
		}
		System.out.println("allocated list add time: "+(System.currentTimeMillis() - start));
		
		start = System.currentTimeMillis(); 
		for(int i = 0 ; i < size ; i++)
		{
			linkedList.add(0, i);
		}
		System.out.println("linked list add time: "+(System.currentTimeMillis() - start));
		

		Iterator it;	
		
		it = allocatedList.iterator();
		
		start = System.currentTimeMillis();
		while(it.hasNext())
		{
			it.next();
		}
		System.out.println("ArrayList iterator time: "+(System.currentTimeMillis() - start));
		
		start = System.currentTimeMillis();
		for(int i = 0 ; i < size ; i++)
		{
			allocatedList.get(i);
		}
		System.out.println("ArrayList direct search time: "+(System.currentTimeMillis() - start));
		
		it = linkedList.iterator();		
		start = System.currentTimeMillis();
		while(it.hasNext())
		{			
			it.next();
		}
		System.out.println("linkedList iterator search time: "+(System.currentTimeMillis() - start));
		
		start = System.currentTimeMillis();
		for(int i = 0 ; i < size ; i++)
		{
			linkedList.get(i);
		}
		System.out.println("linkedList direct search time: "+(System.currentTimeMillis() - start));
	}

}

Maximum Palindromes

29 Oct 2018 Tags:

HackerRank, Strings

HackerRank link

Maximum Palindromes

풀이 핵심

페르마의 소정리을 이용한 Factorial의 나눗셈 modulo 연산
분할정복을 이용한 빠른 거듭제곱 계산
퍼포먼스를 위한 초기 계산

Solution의 답은 중복이 포함된 경우의 수를 구하는 문제이므로 쉽게 구할 수 있다.

(짝수개의 문자 수/2)! x (중간에 올 수 있는 수)
/ (중복된 문자 ‘a’의 수)! / (중복된 문자 ‘b’의 수)! / … / (중복된 문자 ‘z’의 수)!

하지만 입력 조건에서 문자열의 최대 길이는 100000이고, 이 때문에 factorial을 구하는 경우 매우 큰 값이 나올 수 있기 때문에, 답을 구할 때 10^9+7 값의 나머지를 리턴하라고 하고 있다.

곱셈에서의 나머지 연산은 다음 식과 같이 아무때나 연산을 해도 성립하지만, 문제는 나눗셈에서는 성립하지 않는 것이다.

(a x b) % p = (a % p) x (b % p)
(a/b) % p != (a%p) / (b%p)

ex)
(4! % 11) / (3! % 11) = 2 / 6 = 0.33
(4! / 3!) % 11 = 4

페르마의 소정리 이용
이 문제를 해결하기 위해 페르마의 소정리를 이용한다.

페르마의 소정리에서 a^(p-1) = 1 (mod p) 이므로, a x a^(p-2) = 1 (mod p) 이다.
즉, a의 역원은 a^(p-2) 임을 이용한다.
ex) (4! % p) / (3! % p) = (4! % p) x ((3!)^(p-2) % p)

분할 소거법 이용
그런데 여기서 p-2의 거듭제곱을 구하는데, p가 매우 크므로 분할정복을 이용하여 빠르게 계산을 한다. Exponentiation by squaring

미리 계산
마지막으로, 입력의 l과 r로 입력 문자열에서 ‘a’ ~ ‘z’가 각각 몇개가 있는지 알아야 답을 구할 수 있다. 테스트 케이스에서 l과 r이 입력으로 들어올 때마다 문자열을 확인하여 구할수 있지만, 입력 최대 문자열의 길이가 10^5 이고, 최대 test case의 수도 10^5 이기 때문에, 이 방법은 속도면에서 매우 비효율 적이다.

이를 해결하기 위해 입력을 받을 때, 각 문자열 길이 별로 a~z까지의 수를 계산을 해두면 빠르게 계산이 가능하다. (메모리가 많이 사용 되는 단점이 있지만, 속도는 훨씬 빠르다.)

최악의 경우 대략적으로 연산량을 계산하면 (l = 1, r = 10^5, q = 10^5),

미리 계산 안 하는 경우: 10^10번 연산
미리 계산하는 경우 : 10^5 x 24번 연산

자바의 경우 : reference code 최적화
자바의 경우 String을 계속적으로 다루는 경우 메모리 사용에 의해 퍼포먼스가 매우 낮다. 이 때문에, reference 코드에서 하기의 코드를 수정한다.

//변경 전
String[] lr = scanner.nextLine().split(" ");
int l = Integer.Parse(lr[0]);
int r = Integer.Parse(lr[1]);

// 변경 후
int l = scanner.nextInt();
int r = scanner.nextInt();

Algorithm

초기화 부분 : initialize

modulo 계산이 포함된 Factorial을 구한다.
modulo 계산이 포함된 Inverse Factorial을 구한다.
a~z까지의 갯수를 문자열 0 ~ 입력 길이 만큼 저장한다.

계산 부분 : answerQuery

미리 연산된 데이터를 이용하여 ‘a’~’z’까지의 수를 구한다.
‘a’~’z’까지의 수를 이용하여 답을 구한다.

Source Code

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    static final int size = 100001;
    static long mod = (long)Math.pow(10,9)+7;
    static long[] factorial = new long[size];
    static long[] inverseFac = new long[size];
    static int a2z[][];
    
    static long powerWithMod(long a, long n)
    {
        long ret = 1;
        while(n > 0)
        {
            if(n % 2 == 1)    // 홀수 인경우 한번 먼저 곱
            {
                ret *= a;
                ret %= mod;
                
            }
            a *= a;
            a %= mod;
            n /= 2;
        }
        
        return ret;
    }
    
    
    // Complete the initialize function below.
    static void initialize(String s) {
        // This function is called once before all queries.
        // initialize factorial
        factorial[0] = 1;
        factorial[1] = 1;
        for(int i = 2 ; i < factorial.length ; i++)
        {
            factorial[i] = factorial[i-1] * i % mod;
        }
        
        // inverse factorial for modulation.
        // a^(P-1)
        // a x X = 1 (mod P-1)
        // X = a^(P-2)
        
        inverseFac[size-1] = powerWithMod(factorial[size-1], mod - 2);
        for (int i = size - 2; i >= 0; i--) 
        {
            inverseFac[i] = (inverseFac[i + 1] * (i + 1)) % mod;     
        }
        
        a2z = new int[s.length()+1]['z'-'a'+1];                
        
        for(int i = 0 ; i < s.length() ; i++)
        {
            System.arraycopy(a2z[i], 0, a2z[i + 1], 0, 'z' - 'a' + 1);
            a2z[i+1][s.charAt(i)-'a']++;
        }
    }

    // Complete the answerQuery function below.
    static int answerQuery(int l, int r) {
        // Return the answer for this query modulo 1000000007.
        int mid = 0;
        int total = 0;
        long inverse = 1;
        long result =1;
        int[] aTozCnt = new int['z'-'a' + 1];
        
        for(int i = 0 ; i < aTozCnt.length ; i++)
        {
            aTozCnt[i] = a2z[r][i] - a2z[l-1][i];
        }        
        
        for(int cnt : aTozCnt)
        {
            if(cnt % 2 == 0)    // 짝수
            {
                total += cnt/2;
                inverse = (inverse * inverseFac[cnt/2])%mod;
                
            }
            else // 홀수
            {
                if(cnt == 1)    // 한개
                {
                    mid++;
                }
                else
                {
                    total += (cnt - 1)/2;
                    mid++;
                }
                inverse = (inverse * inverseFac[(cnt-1)/2])%mod;
            }
        }
        if(mid == 0) mid =1;
        
        result = (factorial[total] * inverse) % mod;
        result = (result * mid) % mod;
   
        return (int)result;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        String s = scanner.nextLine();

        initialize(s);
        int q = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int qItr = 0; qItr < q; qItr++) {
            // String[] lr = scanner.nextLine().split(" ");

            int l = scanner.nextInt();

            int r = scanner.nextInt();

            int result = answerQuery(l, r);

            System.out.println(result);
        }

        scanner.close();
    }
}

Older Newer

Power Coding 파워 코딩

Kruskal (MST) Really Special Subtree

HackerRank link

풀이 핵심

Algorithm

Source Code

KnightL on a Chessboard

HackerRank link

풀이 핵심

Algorithm

Source Code

HackerRank link

풀이 핵심

Algorithm

Source Code

List

List

ArrayList

LinkedList

ArrayList vs LinkedList

Iterator

몇가지 퍼포먼스 테스트

테스트 결과

결론

테스트 코드

Maximum Palindromes

HackerRank link

풀이 핵심

Algorithm

Source Code