Recursive Digit Sum

03 Aug 2018 Tags:

HackerRank, Recursion

HackerRank link

Recursive Digit Sum

풀이 핵심

이름 그대로 재귀 함수를 이용하여 풀이
입력에 k 번 반복의 경우 k번 반복 할 필요 없이 k를 곱하면 간단하게 해결

Algorithm

문자열의 길이가 1이면 구할 필요가 없음. 바로 리턴.
각 문자열의 숫자를 합하고 k를 곱한다.
문자열의 길이가 1이 될때까지 각 문자열의 숫자를 합하여 super digit을 구한다. (재귀함수)

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 long super_digit(String n)
    {
        if(n.length() == 1)
            return Integer.parseInt(n);
        long sum = 0;
        System.out.print(n+"->");
        for(int i = 0 ; i < n.length() ; i++)
        {
            long temp = Long.parseLong(n.substring(i,i+1)); 
            sum += temp;
            // System.out.print("("+temp+")");
        }
        System.out.println(sum);
        return super_digit(Long.toString(sum));
    }
    
    // Complete the superDigit function below.
    static long superDigit(String n, int k) {
        if(n.length() == 1)
            return Integer.parseInt(n);
        long sum = 0;
        System.out.print(n+"->");
        for(int i = 0 ; i < n.length() ; i++)
        {
             sum += Long.parseLong(n.substring(i,i+1));
        }
        sum = sum * k;
        System.out.println(sum);
        
        return super_digit(Long.toString(sum));     

    }

    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[] nk = scanner.nextLine().split(" ");

        String n = nk[0];

        int k = Integer.parseInt(nk[1]);

        long result = superDigit(n, k);

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

        bufferedWriter.close();

        scanner.close();
    }
}

Cut the Tree

23 Jul 2018 Tags:

HackerRank, Search, Depth First Search

HackerRank link

Cut the Tree

풀이 핵심

node의 탐색 방법으로는 DFS를 이용.
node를 탐색하면서 노드의 값을 더하면서 값을 계산함.

이 문제 에서 Java의 경우 input reference 코드의 퍼포먼스가 매우 안좋게 되어 있어서, 풀이법이 맞아도 계속적으로 timeout error가 발생함.
유사한 문제 : Even Tree

퍼포먼스를 좋게 하기 위한 방법

입력을 받을 때 총합을 미리 계산한다. => node 탐색 시 계산에 용이
입력 시 아래 코드와 같이 scanner.nextInt(); 를 사용하는 방법이 훨씬 빠름.

String[] arrItems = scanner.nextLine().split(" ");  // 쓰지 말것

int[] input = new int[input_num];
for(int i = 0 ; i < input_num ; i++)
{
    input[i] = scanner.nextInt();
}

여러 단계를 거쳐서 오는 문제점도 있고,
자바에서 String을 다룰때 String Class는 퍼포먼스가 매우 좋지 않으니 조심.

Algorithm

input으로 부터 tree를 구성한다. (Array List를 이용)
dfs를 이용하여 노드를 탐색한다.
막다른 지점에서 다시 돌아오는 곳에서 부터 node의 길이를 count 한다.
만약 count 값이 짝수라면, 자르는 값 증가.
최종 입력이 무조건 짝수 이므로, 마지막 node까지 가게 되면 결과 값을 하나 더 하게 됨. 이때문에 마지막에 -1을 해줌.

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 Ascending implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
       return o1.compareTo(o2);
    }

}


public class Solution {

    static int MAXIMUN_INPUT    =    100000+1;
    
    static int minimun = Integer.MAX_VALUE;
    
    static boolean[] visit = new boolean[MAXIMUN_INPUT];
    static ArrayList<Integer> tree[] = new ArrayList[MAXIMUN_INPUT];
    
    static int[] data = new int[MAXIMUN_INPUT];
    
    static int totalSum = 0;

   static int dfs(int start)
    {
        System.out.print(start + " ");
        
        int sum = 0;
        visit[start] = true;
        sum += data[start - 1];
        
        for(int i = 0 ; i < tree[start].size() ; i++)
        {
            int next = tree[start].get(i);
            if(visit[next] == false)
            {
                sum += dfs(next);
            }
        }
        
        System.out.println("("+sum + ")");
        
        int rest = totalSum - sum;
        int dif = sum > rest ? sum - rest : rest - sum;
        
        if(minimun > dif) minimun = dif;
        
        // System.out.print("("+dif + ")");
        
        return sum;
    }
    
    
    // Complete the solve function below.
    static int solve() { 
        dfs(1);        
        return minimun;
    }

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

        // data = new int[n];

        for (int i = 0; i < n; i++) {
            int dataItem = scanner.nextInt();
            data[i] = dataItem;
            totalSum += dataItem;
            // System.out.print(data[i]+" ");
            tree[i] = new ArrayList<Integer>();        
        }
        
        tree[n] = new ArrayList<Integer>();        
        
        // System.out.println();
        
        int[][] edges = new int[n-1][2];

        for (int i = 0; i < n-1; i++) {           

            for (int j = 0; j < 2; j++) {
                int edgesItem =scanner.nextInt();
                edges[i][j] = edgesItem;
                
            }            
            int p0 = edges[i][0];
            int p1 = edges[i][1];
            tree[p0].add(p1);
            tree[p1].add(p0);
        }

        int result = solve();

        // System.out.println(result);
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Project Euler

20 Jul 2018 Tags:

HackerRank, Project Euler

HackerRank link

Project Euler #89: Roman numerals

풀이 핵심

주어진 사양에 맞게 코딩
문자열→숫자, 숫자→문자열 변환

Algorithm

로마 숫자를 숫자로 변환한다.
변환된 숫자를 로마 숫자로 변환한다.

Source Code

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

public class Solution {

    static int RomanNumStr2Num(String str)
    {
        int[] number         = new int[]     {  1,  5, 10, 50,100,500,1000};
        char[] romanStr     = new char[]    {'I','V','X','L','C','D','M'};
        
        int pre = 0;
        int num = 0;
        
        int reVal = 0;
        
        for(int i = 0 ; i < str.length(); i++)
        {
            char ch = str.charAt(i);
            for(int j = romanStr.length - 1 ; j >= 0 ; j--)
            {
                if(ch == romanStr[j])
                {
                    num = number[j];
                    reVal += num;
                    if(pre < num)
                    {
                        reVal -= 2 * pre; 
                    }
                    pre = num;
                    break;
                }
            }
        }
        
        return reVal;
        
    }
    
    static String Num2RomanStr(int num)
    {
        int[] number         = new int[]     {  1,   4,  5,   9, 10,  40, 50,  90,100, 400,500, 900, 1000};
        String[] romanStr     = new String[]    {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"};
        
        StringBuffer roman = new StringBuffer();
        
        while(num > 0 )
        {
            for(int j = romanStr.length - 1 ; j >= 0 ; j--)
            {
                int sub = num - number[j];
                
                if(sub < 0 ) {continue;}
                
                roman.append(romanStr[j]); 
                num -= number[j];
                break;
            }
        }
        
        
        return roman.toString();        
    }
    
    static String RomanNumerals(String str)
    {
        int num = RomanNumStr2Num(str);
        
        return Num2RomanStr(num);
    }    
    
    private static final Scanner scanner = new Scanner(System.in);
    
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        
        // Unit test for RomanNumStr2Num 
        // System.out.println(RomanNumStr2Num("CCXX"));
        
        // Unit test for Num2RomanStr 
        // System.out.println(Num2RomanStr(999));

        
        
        int nTimes = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
                
        for(int i = 0 ; i < nTimes ; i++)
        {
            String str = scanner.nextLine();
            
            String answer = RomanNumerals(str);
            
            System.out.println(answer);            
        }
        
        
        
    }
}

The Maximum Subarray

16 Jul 2018 Tags:

HackerRank, Dynamic Programming

HackerRank link

The Maximum Subarray

풀이 핵심

두가지를 풀어야 됨.
[max subsequence]

단순히 양수를 더하면 최댓값을 알 수 있음.

[max subArray]

동적 프로그래밍으로 풀이
아래의 표와 같이 최대 subArray의 sum은 sum의 최대값 - sum의 최소값(단, 최대값 이전 index) 이다.

index	0	1	2	3	4	5	6
arr	-2	2	-1	2	3	4	-5
sum	-2	0	-1	1	4	8	-3

답은 10

Algorithm

현재까지의 sum 값을 구한다.
최소 값과 최대값을 업데이트 하며, subArrMax를 업데이트한다.
양수를 더하며 subsequence의 최대값을 구한다.
과정 1~4를 반복한다.

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 maxSubarray function below.
    static long[] maxSubarray(long[] arr) {
    	long[] sum = new long[arr.length];
    	
    	long subArrMax = arr[0];
    	long sumMin = arr[0];
    	long subSeqMax = Long.MIN_VALUE;
    	
    	for(int i = 0 ; i < arr.length ; i++)
    	{
    		if(i == 0)
    		{
    			sum[i] = arr[0];
    		}
    		else
    		{
    			sum[i] += sum[i-1] + arr[i];
    			if(sum[i-1] < sumMin) sumMin = sum[i-1];
    			
    			long subMax = sum[i] - sumMin;
    			subMax = sum[i] < subMax ? subMax : sum[i];
    			
    			if(subArrMax < subMax) subArrMax = subMax;
    		}
    		
    		if(arr[i] > 0)
			{
				if(subSeqMax > 0)
				{
					subSeqMax += arr[i];
				}
				else
				{
					subSeqMax = arr[i];
				}
			}
			else
			{
				if(subSeqMax < 0 )
				{
					if(subSeqMax < arr[i])
					{
    					subSeqMax = arr[i];
					}
				}    				
			}
    	}
    	
    	long[] result = new long[2];
    	result[0] = subArrMax;	// 2, -1, 2, 3, 4
    	result[1] = subSeqMax;	// 2,  2, 3, 4
    	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])?");

            long[] arr = new long[n];

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

            for (int i = 0; i < n; i++) {
                long arrItem = Long.parseLong(arrItems[i]);
                arr[i] = arrItem;
            }

            long[] result = maxSubarray(arr);

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

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

            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Alice and Bob's Silly Game

15 Jul 2018 Tags:

HackerRank, Game Theory

HackerRank link

Alice and Bob’s Silly Game

풀이 핵심

Alice와 Bob이 서로 반복하기 때문에 계속 반복할 필요 없이 소수의 총수를 구하면 간단하게 구할 수 있다.

Algorithm

소수를 구하면서 전체 소수의 갯수를 센다.
소수의 수가 짝수이면 Bob, 아니면 Alice를 리턴한다.

Source Code

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

public class Solution {

    /*
     * Complete the sillyGame function below.
     */
    static String sillyGame(int n) {
        /*
         * Write your code here.
         */
		boolean[] primeNum = new boolean[n+1];
		int count = 0;
		
		primeNum[0] = true;
		primeNum[1] = true;
		
		for(int i = 2; i <= n ; i++)
		{
			if(primeNum[i] == false)
			{
				count++;
				for(int j = 2 ; j*i < primeNum.length; j++)
				{
					primeNum[i*j] = true;
				}
			}
		}
		
		if(count % 2 == 0)	return "Bob";
		
		return "Alice";
	}

    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 g = Integer.parseInt(scanner.nextLine().trim());

        for (int gItr = 0; gItr < g; gItr++) {
            int n = Integer.parseInt(scanner.nextLine().trim());

            String result = sillyGame(n);

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

        bufferedWriter.close();
    }
}

Older Newer

Power Coding 파워 코딩

Recursive Digit Sum

HackerRank link

풀이 핵심

Algorithm

Source Code

Cut the Tree

HackerRank link

풀이 핵심

퍼포먼스를 좋게 하기 위한 방법

Algorithm

Source Code

Project Euler

HackerRank link

풀이 핵심

Algorithm

Source Code

The Maximum Subarray

HackerRank link

풀이 핵심

Algorithm

Source Code

Alice and Bob's Silly Game

HackerRank link

풀이 핵심

Algorithm

Source Code