Power Coding 파워 코딩

Rust & Murderer

03 Jun 2019 Tags:
HackerRank, Graph Theory

Rust & Murderer

풀이 과정

일단 제일 간단하게 생각해 볼 수 있는 것은

2차원의 커다란 배열의 map을 만들고 입력이 들어 올때 표시를 해둔다.

그리고 아까 표시된 입력을 제외한 경로로 BFS를 한다.

그런데 여기서 문제가 있다. 노드의 수가 엄청나게 많다.

이렇게 map 데이터를 만드려면 2x10^5 x 2x10^5 = 4x10^10 java에서는 heap이 부족하다.

다른 방법을 생각해야 한다.

기존의 BFS등의 트리의 이동관련 알고리즘은 갈 수 있는 node 데이터를 중심으로 다음 가야 하는 데이터에 대한 중심으로 이동한다.

이 때문에 완전 반대로 생각해 보았다.

먼저 이렇게 할 수 있고, 빠르다고 생각한것은

The graph/map of the city is ensured to be a sparse graph.

이기 때문이다. (확실하게 Node의 수 보다 엣지의 수가 월등히 적다.)

먼저 전부 갈 수 있다고 생각하고,

가면 안되는 엣지만 체크 한다.

만약 이 엣지가 가면 안되는 곳을 제외하고, 갈 수 있는 곳과 이동수 차이가 1난다면,

이 엣지는 갈 수 있는 곳과 연결되어 있는 것이므로 이동된것이다.

일단 모든 노드가 시작 점을 제외하고 1이라고 생각하고,

이동하면 안되는 것들은 2로 고정해두고

이동하면 안되는 부분만 생각하면 된다.

에디토리얼과 좀 다르게 풀었는데, 결과적으로는 내 풀이가 훨씬 빠르다.

이유는 에디토리얼은 리스트 2개를 이용해서 계산하는데,

리스트 두개를 이용하면서 삭제와 추가가 너무 빈번해서 조금 더 느린 것 같다.

Editorial 풀이 에디토리얼과 좀 다른데, 에디토리얼 풀이를 분석하면

2개의 리스트를 이용하고, 전부 이동했다고 생각하고 이동 하면 안되는 것들을 제외 시키는 알고리즘이다.

  1. 이동한 노드의 리스트
  2. 이동해야 하는 노드의 리스트

알고리즘은 다음과 같다

  1. 일단 모두 이동했다고 생각하고, 이동한 리스트에 등록한다.
  2. 처음은 제외한다.
  3. 처음을 기준으로 이동 못 하는 경로가 이동 안했으면 리스트 1번에서 제거 하고, 리스트 2번에 등록한다.
  4. 리스트 1번에서 제거 안된 노드들은 이동했으니까 거리를 1씩 증가 시킨다.
  5. 리스트 1을 모두 제거 하고, 리스트 2의 데이터를 모두 등록한다.

풀이 핵심

  1. 일단 이동했다고 생각하고, 이 노드가 진짜 이동했는지 안했는지 판단한다.
  2. 이동 해서는 안되는 노드가 아니고, 다른 노드들과 비교하고 노드가 거리 값이 1차이면 이동가능

Algorithm

  1. 일단 처음 시작지를 중심으로 모두 이동했다고 생각한다.
  2. 자기 자신은 0으로 초기화
  3. 이동 해서는 안되는 노드들은 거리 정보를 1씩 증가시키고, 이 노드들을 체크 한다.
  4. 이동 해서는 안되는 노드가 아니고, 다른 노드들과 비교하고 노드가 거리 값이 1차이면 이동가능 하므로 볼 피요가 없다.
  5. 만약 4번이 아니라면, 거리를 1로 증가 시키고 앞으로 살펴봐야 한다고 큐에 등록
  6. 현재 살펴봐야할 노드를 모두 봤다면, 앞으로 살펴봐야 하는 노드의 데이터를 옮기고 반복한다.

Source Code

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

public class Solution {

     static int[] rustMurderer(int n, int s, int[][] roads) {
        /*
         * Write your code here.
         */
        int []result = new int[n-1];
        List<Integer> mainRoad[] = new ArrayList[n+1];
        for(int i = 1 ; i <= n; i++) {
            mainRoad[i] = new ArrayList<>();
        }

        for(int i = 0; i < roads.length; i++) {
            int to = roads[i][0];
            int from = roads[i][1];
            
            mainRoad[to].add(from);
            mainRoad[from].add(to);            
        }
        
        for(int i = 1; i <= n; i++) {
            Collections.sort(mainRoad[i]);
        }
        
        
        int[] isMoved = new int[n+1];        
        for(int i = 0; i <= n; i++) {
            isMoved[i] = 1;
        }
        
        isMoved[s] = 0;
        Queue<Integer> haveToCheck = new LinkedList<>();                
        for(int e : mainRoad[s]) {
            isMoved[e]++;
            haveToCheck.add(e);
        }
        
        Queue<Integer> next = new LinkedList<>();        
        int curDis = 1;
        
        while(haveToCheck.isEmpty() == false ) {
            
            int cur = haveToCheck.poll();
            int dont = 0;
            int idx = 0;
            if(mainRoad[cur].size() >= idx + 1) {
                dont = mainRoad[cur].get(idx++);
            }
            boolean found = false;
            for(int i = 1; i <= n; i++) {
                if(i == dont) {
                    if(mainRoad[cur].size() >= idx + 1) {
                        dont = mainRoad[cur].get(idx++);
                    }
                } else {
                    if(isMoved[i] == curDis) {
                        found = true;
                        break;
                    }
                }
            }
            
            if(found == false) {
                isMoved[cur]++;
                next.add(cur);
            }
            
            if(haveToCheck.isEmpty()) {
                   haveToCheck.addAll(next);
                   next.clear();
                   curDis++;
            }
            
        }
        
        
        int count = 0;
        for(int i = 1 ; i <= n; i++) {
            if(i != s) {
                result [count++] = isMoved[i];
            }
        }
        
        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 t = Integer.parseInt(scanner.nextLine().trim());

        for (int tItr = 0; tItr < t; tItr++) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();

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

            for (int roadsRowItr = 0; roadsRowItr < m; roadsRowItr++) {    
                 roads[roadsRowItr][0] = scanner.nextInt();
                 roads[roadsRowItr][1] = scanner.nextInt();
            }

            int s = scanner.nextInt();

            int[] result = rustMurderer(n, s, roads);

            for (int resultItr = 0; resultItr < result.length; resultItr++) {
                bufferedWriter.write(String.valueOf(result[resultItr]));

                if (resultItr != result.length - 1) {
                    bufferedWriter.write(" ");
                }
            }

            bufferedWriter.newLine();
        }

        bufferedWriter.close();
    }
}

에디토리얼 포팅

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

public class Solution {

     static int[] rustMurderer(int n, int s, int[][] roads) {
        /*
         * Write your code here.
         */
        int []result = new int[n-1];
        List<Integer> mainRoad[] = new ArrayList[n+1];
        for(int i = 1 ; i <= n; i++) {
            mainRoad[i] = new ArrayList<>();
        }

        for(int i = 0; i < roads.length; i++) {
            int to = roads[i][0];
            int from = roads[i][1];
            
            mainRoad[to].add(from);
            mainRoad[from].add(to);            
        }
        
        PriorityQueue<Integer> moved = new PriorityQueue<>();
        PriorityQueue<Integer> left = new PriorityQueue<>();
        
        boolean[] isMoved = new boolean[n+1]; 
        int[] distance = new int[n+1];
        
        for(int i = 1; i <= n; i++) {
            moved.add(i);
        }
        
        moved.remove(s); 
        
        isMoved[s] = true;
        Queue<Integer> haveToCheck = new LinkedList<>();
        haveToCheck.add(s);
        
        while(!haveToCheck.isEmpty()) {
            
           int cur = haveToCheck.poll();
           for(int e : mainRoad[cur]) {
               if(!isMoved[e]) {
                  moved.remove(e);
                  left.add(e);                      
               }
           }
           
           while(!moved.isEmpty()) {
               int e = moved.poll();
               isMoved[e] = true;
               distance[e] = distance[cur] + 1;
               haveToCheck.add(e);               
           }
            
           moved.addAll(left);
           left.clear();
        }
        
        
        int count = 0;
        for(int i = 1 ; i <= n; i++) {
            if(i != s) {
                result [count++] = distance[i];
            }
        }
        
        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 t = Integer.parseInt(scanner.nextLine().trim());

        for (int tItr = 0; tItr < t; tItr++) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();

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

            for (int roadsRowItr = 0; roadsRowItr < m; roadsRowItr++) {    
                 roads[roadsRowItr][0] = scanner.nextInt();
                 roads[roadsRowItr][1] = scanner.nextInt();
            }

            int s = scanner.nextInt();

            int[] result = rustMurderer(n, s, roads);

            for (int resultItr = 0; resultItr < result.length; resultItr++) {
                bufferedWriter.write(String.valueOf(result[resultItr]));

                if (resultItr != result.length - 1) {
                    bufferedWriter.write(" ");
                }
            }

            bufferedWriter.newLine();
        }

        bufferedWriter.close();
    }
}

Minimum Penalty Path

01 Jun 2019 Tags:
HackerRank, Graph Theory

Minimum Penalty Path

풀이 과정

OR연산의 가장 큰 특징은 꼭 작은 수로만 or를 한다고 제일 작은 수라고 보장이 되지 않는 점이다.

4 or 2 = 6 이지만, 4 or 4 = 4이다.

아래와 같은 입력이 들어 온 경우

4 5 
1 2 1 
1 2 2 
2 3 10 
3 4 2 
3 4 1 
1 4 
답: 10

이 때문에 다익스트라 알고리즘을 이용하여 풀려고 하는 경우 풀 수가 없다.

그러면 일반 BFS나 DFS를 이용하여 그래프를 탐색하면서 다음 수가 최소 인지 알 수 있수 있을까?

굉장히 어려워 보인다. 왜냐하면 뒤에 추가적으로 나올 수가 무엇인지도 모르기 때문이다.

그럼 결론은 전부 다 검색해 봐야 한다.

그런데 여기서 문제가 있다. 제약 조건에서 N보다 M이 훨등히 많다.

즉, 노드의 수 보다 엣지의 수가 월등히 많다. 따라서, 효율적으로 서치를 해야 한다.

BFS나 DFS 모두 이용해도 답은 나올 것이다 왜냐하면 모든 엣지를 서치 하기만 하면 되기 때문이다.

문제는 이 문구 이다.

Loops and multiple edges are allowed.

모든 경우의 서치를 해야 하는데 다수의 엣지가 허용 되기 때문이 일반적인 서치를 통해서는 엄청나게 많은 수가 나올 것이다.

그런데 OR 연산의 경우 특이하게도 중복이 굉장히 많이 될 가능성이 있다.

ex) 6 or 2 = 6, 6 or 4 = 6, 6 or 6 = 6

즉, 앞에서 2, 4, 6 등이었고 다음이 또 6이었다면 앞에 2 -> 6, 4 -> 6, 6 -> 6 3가지 모두 할 필요없는 것이다.

그리고 node의 최댓값은 1~1023이다.

이를 이용하여 각 노드를 1024개의 배열로써 표시하면 최대한 빠르게 서치 가능하다.

boolean[][] isMoved = new boolean[n+1][1024];

다른 풀이

인상 적인 풀이로는

nbleier3 : 코드

풀이의 핵심 이동할 필요 없는 엣지를 지운다는 것이다.

만약 256보다 큰 엣지는 이동하지 않는다라고 하고, BFS를 이용하여 서치를 한다.

만약 도착을 못 했다면, 엣지의 크기가 256인 엣지는 무조건 이동 시 필요한 엣지이다.

or연산이고, 엣지의 크기가 최대 1023이므로 최대 10번만 루프를 돌리면 된다.

알고리즘

  1. 이동 관련 데이터를 만든다.
  2. 일단 BFS로 한번 서치 해본다.
  3. 만약 도달하지 못 헀다면, 답이 없다고 리턴
  4. 512보다 큰 엣지에 대하여 이동하지 않고 탐색해 본다.
  5. 만약 도달하지 못 했다면, 512보다 큰 엣지는 512를 뺀 상태로 이동 관련 데이터를 갱신한다. (다음 번 서치에 이동 가능해야 하므로)
  6. 다음 512를 2를 나누고 다시 시도한다.
  7. 과정 4-7를 a가 0보다 큰 경우 계속 돌린다.
  8. 이제 남은 노드들을 or 연산 하여 답을 도출한다. (이 노드들은 무조건 이동)

풀이 핵심

  1. 모든 노드를 1024개의 배열로써 전 노드로부터 어떤 값이 왔는지 저장한다.

Algorithm

  1. 각 node의 입력 저장한다.
  2. 모든 노드를 1024크기의 배열로 확보한다.
  3. BFS 또는 DFS를 이용하여 서치 한다.

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 beautifulPath function below.
    static public class Node {
        int to;
        int weight;
        
        Node(int to, int weight) {            
            this.to = to;
            this.weight = weight;            
        }
    
    }
    
    static int beautifulPath(int n, int[][] edges, int A, int B) {
                
        List<Node> map[] = new ArrayList[n+1];
        for(int i = 0; i < map.length; i++) {
            map[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < edges.length; i++) {
            int from = edges[i][0];
            int to = edges[i][1];
            int weight = edges[i][2];
            
            map[from].add(new Node(to, weight));
            map[to].add(new Node(from, weight));
        }
        
        boolean[][] isMoved = new boolean[n+1][1024];
        
        isMoved[A][0] = true;
        
        Queue<Integer> haveToMove = new LinkedList<>();
        haveToMove.add(A);
        
        Queue<Integer> accumulatedOR = new LinkedList<>();
        accumulatedOR.add(0);
        
        while (!haveToMove.isEmpty())
        {
            int cur = haveToMove.poll();
            int or = accumulatedOR.poll();
            
            for(Node node : map[cur]) {
                int to = node.to;
                int weight = node.weight | or;
                
                if(!isMoved[to][weight]) {
                    isMoved[to][weight] = true;
                    haveToMove.add(to);
                    accumulatedOR.add(weight);                    
                }
            }
            
        }
        for (int i = 0; i < 1024; i++)
        {
            if (isMoved[B][i])
            {
                return i;
            }
        }
        
        return -1;
    }

    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")));

        String[] nm = scanner.nextLine().split(" ");

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

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

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

        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 < 3; j++) {
                int edgesItem = Integer.parseInt(edgesRowItems[j]);
                edges[i][j] = edgesItem;
            }
        }

        String[] AB = scanner.nextLine().split(" ");

        int A = Integer.parseInt(AB[0]);

        int B = Integer.parseInt(AB[1]);

        int result = beautifulPath(n, edges, A, B);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Journey to the Moon

14 May 2019 Tags:
HackerRank, Graph Theory

Journey to the Moon

풀이 과정

사실 1년전쯤 푼 문제인데, 언제푼지 기억이 안나서 14일 일자로 등록.

문제를 푸는데 두가지가 핵심이 될 것 같다.

  1. 우주 비행사를 나라별로 어떻게 분류 할 수 있는가?
  2. 분류를 하고 나서 어떻게 답을 구할 수 있는가?

나라 별로 분류 하고 나서 일단 답을 구하는 방법을 생각하면,

예제 입력1을 봤을 때,

Sample Input1

4 1
0 2

입력에 의해 [0,2], [1], [3]으로 나라가 나뉘고,

[0,1], [0,3], [2,1], [2,3], [1,3] 총 5가지가 된다.

즉, sum((전체 인원수 - 해당 나라 인원수)*(해당 나라 인원수))/2 = 나머지 페어 수 가된다.

곱을 하는 이유는 해당 나라 인원 수 만큼 경우의 수가 생기고,

나누기를 하는 이유는 중복을 제외한 것이다.

[0,2]의 경우 4 - 2 = 2 * 2 = 4 [1]의 경우 4 - 1 = 3
[3]의 경우 4 - 1 = 3

10/2 = 5 가 된다.

우주 비행사를 나라별로 어떻게 분류하는 것인가는

우주 비행사 별 나라 정보를 기억하는 배열, 나라별 수를 기억하는 배열이 두가지로 해결가능하다.

ArrayList vs 배열

사실 2번째 풀땐, 보기 좋으라고 ArrayList 형태로 풀어 보았다. 나라별로 보기에는 편하지만, ArrayList의 메모리 할당과정이 많이 걸려서 결과적으로는 ArrayList 버전이 더 느렸다.

ref input

100000 2
1 2
3 4
  ArrayList 배열
메모리 할당 0.011 0.002
알고리즘 수행 0.0 0.002
합계 0.013 0.004

풀이 핵심

  1. 배열 2개로 우주 비행사 별 나라 정보를 기록하고, 나라별 우주 비행사의 수를 기록한다.
  2. 답은 sum((전체 인원수 - 해당 나라 인원수)*(해당 나라 인원수))/2 = 나머지 페어 수 로 구할 수 있다.

Algorithm

  1. 나라별 우주 비행사 별 배열의 용량을 할당하고 초기화 한다. 처음에는 각 나라의 우주 비행사 수는 1, 그리고 서로 다른나라라고 가정한다.
  2. 입력이 들어왔을 때, 서로 다른 나라인 경우 해당 나라로 전부 바꿔준다. 바꿔야되는 나라를 전체 검색하여 바꾸고, 바꿀때마다 나라별 우주 비행사수를 갱신한다.

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.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;


public class Solution1 {

    static long journeyToMoon(int n, int[][] astronaut) {
    	boolean debugPrint = false;
    	long numPairs = 0;
    	long pre = System.currentTimeMillis();
    	int[] country = new int[n];
    	int[] count = new int[n];
  	
    	// assume all of astronauts are from different country.
    	for(int i = 0 ; i < n; i++)
    	{
    		country[i] = i;
    		count[i] = 1;
    	}
    	System.out.println((float)(System.currentTimeMillis() - pre)/1000.0);  
    	pre = System.currentTimeMillis();
    	for(int i = 0 ; i < astronaut.length ; i++)
    	{
    		int c0 = astronaut[i][0];
    		int c1 = astronaut[i][1];
    		
    		if(country[c0] != country[c1])
    		{
				int c = country[c0] < country[c1] ? country[c0] : country[c1];
				int change = country[c0] > country[c1] ? country[c0] : country[c1];
				for(int j = 0; j<n ; j++)
				{
					if(country[j] == change)
					{
						count[change]--;
						country[j] = c;
						count[c]++;
					}
				}        		
    		}
    	}
    	System.out.println((float)(System.currentTimeMillis() - pre)/1000.0);  
    	if(debugPrint)
    	{
    		for(int i = 0 ; i< n ; i++)
        	{
        		System.out.println(i+":"+country[i]);
        	}
        	
        	System.out.println("-------------");
        	for(int i = 0 ; i< n ; i++)
        	{
        		int countyrCode = i;
        		System.out.println(countyrCode+":"+count[i]);
        	}
        	System.out.println("-------------");
    	}
    	
    	numPairs = 0;

    	for(int i = 0 ; i< n; i++)
    	{
   			int cnt = n-count[country[i]];   			
    		numPairs += (cnt);
    		
    		if(debugPrint) System.out.println(i+":"+cnt);
    	}
    	
    	numPairs /= 2;
    	return numPairs;
    }

    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")));

        String[] np = scanner.nextLine().split(" ");

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

        int p = Integer.parseInt(np[1]);

        int[][] astronaut = new int[p][2];

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

            for (int j = 0; j < 2; j++) {
                int astronautItem = Integer.parseInt(astronautRowItems[j]);
                astronaut[i][j] = astronautItem;
            }
        }

        long pre = System.currentTimeMillis();
        long result = journeyToMoon(n, astronaut);

//        System.out.println(result);
        System.out.println(result+":"+(float)(System.currentTimeMillis() - pre)/1000.0);
        // bufferedWriter.write(String.valueOf(result));
        // bufferedWriter.newLine();

        // bufferedWriter.close();

        scanner.close();
    }
    
}

ArrayList 버전

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 Solution2 {

    // Complete the journeyToMoon function below.
    static long journeyToMoon(int n, int[][] astronaut) {
    	long numPairs = 0;
    	long pre = System.currentTimeMillis();
    	List<Integer> astronautList[] = new ArrayList[n];		// 나라 가지고 있는 우주 비행사 정보
    	int[] country = new int[n];								// 우주비행사의 나라 정보
    	for(int i = 0; i< n; i++) {
    		astronautList[i] = new ArrayList<Integer>();
    		astronautList[i].add(i);
    		country[i] = i;
    	}
    	System.out.println((float)(System.currentTimeMillis() - pre)/1000.0);
    	pre = System.currentTimeMillis();
    	for(int i = 0; i < astronaut.length; i++) {
    		int a1 = astronaut[i][0];
    		int a2 = astronaut[i][1];
    		
    		// 서로 다른 나라면
    		if(country[a1] != country[a2]) { 
    			// 해당 나라의 모든 우주 비행사들을 a1쪽으로 나라를 바꾼다.
    			int haveToDelete = country[a2];
    			for(int temp : astronautList[country[a2]]) {
    				astronautList[country[a1]].add(temp);
    				country[temp] = country[a1];
    			}
    			astronautList[haveToDelete].clear();
    		}
    	}
    	System.out.println((float)(System.currentTimeMillis() - pre)/1000.0);
    	for(int i = 0; i < astronautList.length; i++) {
    		int size = astronautList[i].size();
    		if(size != 0) {
    			int cnt = (n-size)*size;  
    			numPairs += (cnt); 
    		}	
    	}

    	return numPairs/2;
    }

    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")));

        String[] np = scanner.nextLine().split(" ");

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

        int p = Integer.parseInt(np[1]);

        int[][] astronaut = new int[p][2];

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

            for (int j = 0; j < 2; j++) {
//                int astronautItem = Integer.parseInt(astronautRowItems[j]);
            	int astronautItem = scanner.nextInt();
                astronaut[i][j] = astronautItem;
            }
        }
        
        long pre = System.currentTimeMillis();
        
        long result = journeyToMoon(n, astronaut);
        System.out.println(result+":"+(float)(System.currentTimeMillis() - pre)/1000.0);
//        bufferedWriter.write(String.valueOf(result));
//        bufferedWriter.newLine();

//        bufferedWriter.close();

        scanner.close();
    }
    
}

Sansa and XOR

13 May 2019 Tags:
HackerRank, Bit Manipulation

Sansa and XOR

풀이 과정

예제에 나온데로 순차적으로 계산하면 답이 될 수 있다.

하지만, 제약조건을 봤을때, 2 <= n <= 10^5 이다. 게다가 한번만 계산하는게 아니라

예제를 보면

입력 배열이 arr = [3,4,5] 이면,  

3^4^5^(3^4)^(4^5)^(4^5)^(3^4^5)

순으로 계산한다.

굉장히 많은 연산량이 필요하게 된다.

다른 방법을 생각해 보자.

Xor은 해당 비트가 같으면 0 아니면 1이다.

그리고, 몇번 xor 연산을 해보면 이러한 특징을 발견 할 수 있다.

  1. 자기자신을 xor 하면 0이다. 왜냐면 똑같으니까.
  2. xor은 분배법칙, 교환법칙 모두가 통한다. 즉 3^4^5^(3^4^5) = 3^4^5^3^4^5
  3. 배열의 사이즈가 짝수인경우 각 배열의 원소가 짝수번 xor 연산을 하게 되어 무조건 0이다.
  4. 배열의 사이즈가 홀수인경우 원소의 짝수번째 index는 짝수번 나오게되어 0이다. (시작이 1부터라고 한 경우)

이 특징을 이용하면 O(n)으로 풀 수 있다.

풀이 핵심

  1. 배열의 사이즈가 짝수면 무조건 답은 0이다.
  2. 배열의 사이즈가 홀수인경우 짝수번째는 0이다.

Algorithm

  1. 배열의 사이즈를 체크하면 짝수면 0을 리턴한다.
  2. 그게 아니라면, 배열의 짝수번째 index를 모두 xor 연산을 한다.

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 sansaXor function below.
    static int sansaXor(int[] arr) {
        
        if(arr.length % 2 == 0) return 0;
        
        int result = 0;
        
        for(int i = 0 ; i < arr.length; i+=2) {           
            result = result ^ arr[i];            
        }
        
        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 t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] arr = new int[n];

            String[] arrItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i < n; i++) {
                int arrItem = Integer.parseInt(arrItems[i]);
                arr[i] = arrItem;
            }

            int result = sansaXor(arr);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Xor and Sum

12 May 2019 Tags:
HackerRank, Dynamic Programming

Xor and Sum

풀이 과정

XOR을 많이 안쓰다 보니 조금 생소하다. 문제 자체는 굉장히 심플하다. 주어진 수식을 계산 하면 되는 문제 이다.

XOR 연산은 두 값의 각 자릿수를 비교해,값이 0으로 같으면 0, 값이 1로 같으면 0, 다르면 1을 계산한다.

자세히 보면, 같으면 해당 자릿수는 빼기 다르면 더하기가 된다.

b의 경우 left shift를 계속적으로 하는데 shift는 1번 할때마다 2배가 된다.

String으로 들어 오는 두 값을 생각해보자. a, b 둘다 1 <= a,b <= 2^(10^5) 그런데, a는 증가 하지 않고 b는 2배씩 증가 한다.

shift 하다 보면 언젠가는 a랑 겹치지 않는 부분이 있다.

이후는 계속 두 수를 더하면된다.

즉, 겹치는 부분은 b에서 1 bit가 a의 1 bit 만날 때 이루어지고, 해당 수 만큼 빼주면 된다.

solution = b의 총합 + a * 314160 - (겹치는 부분)

b의 총합은 등비수열의 합이므로, sum a*r^(n-1) = a * ((r^n)-1) / (r-1) : ( r > 1)

문제는 겹치는 부분인데 첫번째로 계산 방법은 2중 for문이다.

for 0 -> a.length  
    for 0 -> b.length  
	   if ( a(i) == b(j) ) count++;

이런식으로 그런데 input이 2^(10^5) 이므로 2중 for문 사용시 어마어마한 계산량이…

그렇다면 한번에 가능할 방법이 있지 않을까?

뒤쪽부터 계산 하면 가능 하다.

풀이 핵심

  1. Xor 계산에서 같은 자릿수의 bit가 같으면 “빼기” 다르면 “더하기”가 된다.
  2. solution = sum(b) + a * 314160 - (겹치는 부분) 으로 계산이 된다.
  3. 겹치는 부분을 한번에 계산하기 위해서 최상위 비트부터 계산한다.
  4. 제곱을 계산하기 위해서 분할 정복법을 이용하여 빠르게 계산한다.

Algorithm

  1. 겹치는 부분을 계산한다. 그 겹치는 부분의 2배를 추후 빼줄 것이다. 2배인 이유는 a도 빠지고 b도 빼야되기 때문.
  2. b의 합을 구한다. 등비수열의 합을 구한다. a(r^n-1)/(r-1) (r > 1)
  3. a의 합을 구한다. a * (314159 + 1) 0부터 134159번이므로
  4. 결과를 구한다. solution = b의 총합 + a * 314160 - (겹치는 부분)

Source Code

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

public class Solution {

    /*
     * Complete the xorAndSum function below.
     */
	static final long modulo = 1000000000 + 7;
	static final long until = 314159 + 1;

	/*
	 * XOR 연산은 두 값의 각 자릿수를 비교해,값이 0으로 같으면 0, 값이 1로 같으면 0, 다르면 1을 계산한다.
	 * 즉, 같으면 해당 자릿수는 빼기 다르면  더하기가 된다.
	 * 
	 * b의 경우 left shift를 계속적으로 하는데 shift는 1번 할때마다 2배가 된다.
	 * 
	 * String으로 들어 오는 두 값을 생각해보자. a, b 둘다  1 <= a,b <= 2^(10^5)
	 *  그런데, a는 증가 하지 않고 b는 2배씩 증가 한다.
	 *  
	 * b를 shift 하다 보면 언젠가는 a랑 겹치지 않는 부분이 있다. 이런 경우 계속 두 수를 더하면된다.
	 * 그런데 겹치는 부분이 있다. 그런경우 그 수를 빼면된다.
	 *  
	 * 즉, 겹치는 부분은 b에서 한 bit가 a의 bit와 만날 때 이루어지고, 해당 수 만큼 빼주면 된다.
	 *  
	 * solution = b의 총합 + a * 314159 - (겹치는 부분)
	 *  
	 * b의 총합은 등비수열의 합이므로, sum a*r^(n-1) = a * ((r^n)-1) / (r-1) : ( r > 1)
	 * 
	 * 문제는 겹치는 부분인데
	 * 첫번째로 계산 방법은 2중 for문이다. 
	 *  for 0 -> a.length
	 *   for 0 -> b.length
	 *     if ( a(i) == b(j) ) count++;
	 *  
	 * 이런식으로 그런데 input이 2^(10^5) 이므로 2중 for문 사용시 어마어마한 계산량이...
	 *  
	 * 그렇다면 한번에 가능할 방법이 있지 않을까?
	 *  
	 * 뒤쪽부터 계산 하면 가능 하다.
	 */
	static int powerWithMod(long a, long pow) {

		/*
		if(pow%2 == 1) {
			result = ((powerWithMod(a, pow/2) * powerWithMod(a, pow/2)) % modulo * a)  % modulo;
		} else {
			result = (powerWithMod(a, pow/2) * powerWithMod(a, pow/2)) % modulo;
		}
		*/
		
		long result = 1;
		long x = a;
				
		while(pow > 0) {
			
			if( (pow & 1) > 0) {
				result = (result * x) % modulo;
			}
			
			pow = pow >> 1;
			
			x = (x * x) % modulo;
		}
		
		return (int)result;
	}
	static long pluse(long a, long b) {
		return (a+b) % modulo;
	}
	
	static long sub(long a, long b) {
		return (a + (modulo - b))%modulo;
	}
	
	static long mul(long a, long b) {
		return (a*b) % modulo;
	}
	
	static long covertInt(String s) {
		long result = 0;
		for(int i = 0; i < s.length(); i++) {    		
    		if(s.charAt(i) == '1'){
    			result = pluse(result, powerWithMod(2, s.length() - (i+1)));
    		}
    	}
		
		return result;
	}
	

    static long xorAndSum(String a, String b) {
        /*
         * Write your code here.
         */

    	// b의 시작 지점    	
    	
    	int j = 0;
    	
    	//   1 0 1 1	: 4
    	// 1 0 1 1 1	: 5

    	int gap = 0;
    	
    	if(a.length() < b.length()) {
    		j = b.length() - a.length();
    	} else {
    		gap = a.length() - b.length();
    	}
    	
    	long powSum = 0;
    	long restSum = 0;
    	
		for(int i = 0; i < a.length() && j < b.length(); i++) {    		
    		if(a.charAt(i) == '1'){
    			powSum = pluse(powSum, powerWithMod(2, a.length() - (i+1)));			
    		}
    		
    		if(b.charAt(j) == '1') {
				// 자릿수가 같으면 증가
				if((j + gap) == i) {     					
					restSum = pluse(powSum, restSum);					
					j++;
				}
			} else {
				j++;
			}
    	}
		
		// 나머지 처리
		for( ; j < b.length() ; j++) {
			if(b.charAt(j) == '1') { 
				restSum = pluse(powSum, restSum);
			}
		}
    	
    	
    	restSum = mul(restSum, 2);
    	
    	long bSum = mul(covertInt(b), powerWithMod(2,until) - 1);
    	long aSum = mul(covertInt(a),until);
    	
    	return sub(pluse(bSum, aSum), restSum);    	
    }

    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")));

        String a = scanner.nextLine();

        String b = scanner.nextLine();

        long result = xorAndSum(a, b);
        System.out.println(result);

//        bufferedWriter.write(String.valueOf(result));
//        bufferedWriter.newLine();

//        bufferedWriter.close();
    }
}