Highest Value Palindrome

25 Oct 2018 Tags:

HackerRank, Strings

HackerRank link

풀이 핵심

앞자리가 클 수록 큰 숫자 이다.
입력 k 보다 변경해야 할 숫자가 더 크면 불가능하다. (-1 리턴)
k가 변경 해야 할 숫자가 작으면, 숫자를 9로 바꾸면서 가장 큰 수를 만들어 낼 수 있다.

Algorithm

변경해야 할 숫자와 변경해야 하는 index를 기록한다. 이때, 앞뒤가 같도록 숫자를 변경한다.
가능/불가능 여부를 체크한다.
숫자가 이미 9인경우에는 변경할 필요가 없음으로 패스.
변경이 불필요 하는 경우, 나머지 변경 가능한 수가 2번인 경우 변경 : 나머지 차감 -2
그렇지 않는 경우(변경해야 하는 index) 변경한다. : 나머지 차감 -1
길이가 홀수 인 경우, 가운데 index를 추가 변경이 가능한 경우 9로 변경해 준다.

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 highestValuePalindrome function below.
    static String highestValuePalindrome(String s, int n, int k) {
        
        // idx :0 1 2 3 4 
        // 홀수 : 1 2 3 4 5
        //길이 5 : length / 2 = 2 OK
        // 짝수 : 1 2 3 4
        // 길이 2 : length / 2 = 2
        int[] front;
        int[] back;
        boolean[] changed;
        int haveToChange = 0;
        int len = s.length() / 2;
        
        front = new int[len];
        back = new int[len];
        changed = new boolean[len];
        
        // len => 3 : 3 / 2 = 1        
        for(int i = 0 ; i < len ; i++)
        {
            front[i] = Integer.parseInt(s.substring(i, i+1));    //"smiles".substring(1, 5) returns "mile"
            back[i] = Integer.parseInt(s.substring(s.length() - i-1, s.length() - i));
            if(front[i] != back[i])
            {
                haveToChange++;
                if(front[i] > back[i])
                {
                    back[i] = front[i];
                }
                else
                {
                    front[i] = back[i];
                }
                changed[i] = true;
            }
        }      
        
        int rest = k - haveToChange;
        if(rest < 0) return "-1";    
        
        System.out.println(k+","+haveToChange+","+rest);
        int i = 0;
        while(rest > 0 && i < len)
        {   
            if(front[i] != 9)
            {
                if(changed[i] == false && rest >= 2)
                {
                    
                    front[i] = 9;
                    back[i] = 9;
                    rest -= 2;
                }
                else if(changed[i])
                {
                    front[i] = 9;
                    back[i] = 9;
                    rest --;
                }                
            }
            
            i++;
        }
        
        System.out.println(k+","+haveToChange+","+rest);
        
        
        StringBuilder str = new StringBuilder();
        
        //홀수 미드 처리 ( 남는거 있으면 9로)
        
        for( i = 0 ; i < len ; i++)
        {
            str.append(front[i]);
        }
        
        if(s.length() % 2 != 0)
        {
            if(rest > 0)
            {
                str.append("9");
            }
            else
            {
                str.append(s.substring(len, len+1));
            }
        }        
        
        for( i = 0 ; i < len ; i++)
        {
            str.append(back[len-1-i]);
        }        
        
        return str.toString();

    }

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

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

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

        String s = scanner.nextLine();

        String result = highestValuePalindrome(s, n, k);

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

        bufferedWriter.close();

        scanner.close();
    }
}

Lily's Homework

24 Oct 2018 Tags:

HackerRank, sorting

HackerRank link

Lily’s Homework

풀이 핵심

배열이 오름차순 또는 내림차순으로 정렬로 된 경우에 전후의 배열의 절대값의 합이 최소가 된다.
스왑해야 하는 수를 구하기 위해서는 직접 구하는 방법외에는 없다.
각 index가 스왑해야 하는지 판단하기 위해선 sorting을 해야 한다.
스왑해야 하는 위치를 알기 위해서는 HashMap이 필요하다. (key, value)

Algorithm

input을 받으면서 HashMap을 업데이트 한다.
퍼포먼스가 좋은 내부 sort 함수를 이용하여 입력 sort한다.
오름 차순에 대하여 swap 횟수를 구한다.
내림 차순에 대하여 swap 횟수를 구한다.
과정 3, 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 {
    static int[] sorted;
    static int[] inputArr;
    static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();    
	
    /*
	1. 스왑해야 하는 장소를 알기 위해 Hash map을 만든다.
	
	2. 오름차순으로 정렬한 배열로, 오름차순 순으로 스왑을 한다.
	
	3. 정렬된 배열을 이용하여, 내림차순으로 스왑을 한다.
	
	*/
    static int ascendingCnt(int[] input, HashMap<Integer, Integer> map)
    {
        int cnt = 0;
        
        for(int i = 0 ; i < input.length; i++)
        {
            // 정렬된 것과 input이 다르면.... 스왑!
            if(input[i] != sorted[i])
            {
                cnt++;
                int target = (int)map.get(sorted[i]);
                int temp = input[target];                
                input[target] = input[i];
                input[i] = temp;
                
                // 한개는 이미 fix 되었으니 앞으로 바뀔 것의 idx 값만 바꾸면 됨.
                map.put(input[target], target);                
            }
        }
        
        return cnt;
    }
    
    static int descendingCnt(int[] input, HashMap<Integer, Integer> map)
    {
        int cnt = 0;
        int n = input.length - 1;
        
        for(int i = 0 ; i < input.length; i++)
        {
            if(input[i] != sorted[n-i])
            {
                cnt++;
                
                int target = (int)map.get(sorted[n-i]);
                int temp = input[target];                
                input[target] = input[i];
                input[i] = temp;
                
                // 한개는 이미 fix 되었으니 앞으로 바뀔 것의 idx 값만 바꾸면 됨.
                map.put(input[target], target);             
            }
        }
        
        return cnt;
    }
    
    // Complete the lilysHomework function below.
    static int lilysHomework() {
                
        Arrays.sort(sorted);
                
        int ascending = ascendingCnt(Arrays.copyOf(inputArr, inputArr.length), new HashMap<Integer, Integer>(map));
        int descending = descendingCnt(Arrays.copyOf(inputArr, inputArr.length), new HashMap<Integer, Integer>(map));        
        
        System.out.println(ascending+","+descending);
        
        return ascending > descending ? descending : ascending;
        //return ascending;
    }

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

        sorted = new int[n];
        inputArr = new int[n];
        
        for(int i = 0 ; i < n; i++)
        {
            int val = scanner.nextInt(); 
            inputArr[i] = val;
            sorted[i] = val;
            map.put(val, i);
        }

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

        int result = lilysHomework();
        System.out.println(result);

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

        bufferedWriter.close();

        scanner.close();
    }
}

Fraudulent Activity Notifications

13 Oct 2018 Tags:

HackerRank, sorting, radix sorting

HackerRank link

Fraudulent Activity Notifications

풀이 핵심

median 값을 sorting 없이 구할 수 있는 방법은 없다.
median의 값을 구하기 위해 검색 해야 하는 날(d) 기준으로 매번 일반적인 sorting 한다면, 퍼포먼스에 큰 영향을 미친다.
0 <=expenditure[i] <= 200으로 radix sort을 이용한다면, median 값을 구하기 위해 매번 100회 정도의 검색만으로도 구할 수 있다.

Algorithm

처음 d날짜를 기준으로 radix를 업데이트 한다.
radix를 이용하여 median을 구한다.
알림을 해야 하는지 판단한다.
radix를 업데이트 한다.

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 int[] radix = new int[201];
    
    static int getMedian(int d)
    {
        int median = 0;
        int cnt = 0;
        
        // odd  : 0 1 2, 3/2 + 1 = 2
        //        0 1 2 3 4, 5/2 + 1 = 3
        // even : 0 1  , 2/2 = 1 
        //        0 1 2 3, 4/2 = 2
        int mid = d % 2 == 0 ? d / 2 : d / 2 + 1;
        
        for(int i = 0; i < radix.length ; i++)
        {
            if(radix[i] > 0)
            {
                cnt += radix[i];
                if(cnt >= mid)
                {
                    median += i;
                    if(d % 2 == 0)
                    {
                        if( median != i) break;
                        
                        if(cnt > mid) 
                        {
                            median += i;
                            break;
                        }
                        
                    }
                    else
                    {
                        median += i;
                        break;                        
                    }
                }
            }                
        }
        
        return median;
    }
    // Complete the activityNotifications function below.
    static int activityNotifications(int[] expenditure, int d) {
        
        if( expenditure.length == d) return 0;
        
        int notice = 0;
        
        // set first radix for first d days.
        for(int i = 0 ; i < d; i++)
        {
            radix[expenditure[i]]++;
        }
        
        // set first radix for first d days.
        for(int i = d ; i < expenditure.length; i++)
        {
            int median = getMedian(d);            
            
            if(median <= expenditure[i]) notice++;
            
            System.out.println(median+","+expenditure[i]);
            
            radix[expenditure[i - d]]--;
            radix[expenditure[i]]++;
            
        }
        
        return notice;
    }

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

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

        int d = Integer.parseInt(nd[1]);

        int[] expenditure = new int[n];

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

        for (int i = 0; i < n; i++) {
            int expenditureItem = Integer.parseInt(expenditureItems[i]);
            expenditure[i] = expenditureItem;
        }

        int result = activityNotifications(expenditure, d);

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

        bufferedWriter.close();

        scanner.close();
    }
}

Larry's Array

28 Sep 2018 Tags:

HackerRank, Implementation

HackerRank link

Larry’s Array

풀이 핵심

임의의 3개의 수를 rotate 하더라도 변하지 않는 수열의 특성을 이용하여 풀수가 있다. inversion

ex) 가능한 경우와 가능하지 않는 경우를 보면

가능한경우
arr = {1, 2, 3} 이고 rotate를 했을때 나오는 모든 경우와 inversion을 구하면,
{1, 2, 3} => 0
{2, 3, 1} => 2
{3, 1, 2} => 2
가능하지 않는 경우
arr = {1, 3, 2} 이고 rotate를 했을때 나오는 모든 경우와 inversion을 구하면,
{1, 3, 2} => 1
{3, 2, 1} => 3
{2, 1, 3} => 1

한번 rotate하는 경우 inversion은 짝수개가 변한다.

좌측 rotate : 가장 작은 수가 맨 우측으로 이동 inversion 2증가
우측 rotate : 가장 큰수가 맨 좌측으로 이동 inversion 2증가

따라서, 가능한 경우는 inversion이 항상 짝수개
가능하지 않는 경우는 inversion이 항상 홀수개 이다.

Algorithm

inversion을 구한다.
inversion이 짝수인 경우 YES, 아닌경우 NO 리턴

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 larrysArray function below.
    static String larrysArray(int[] A) {
        int inversions = 0;
        for(int i = 0 ; i < A.length - 1; i++)
        {
            for(int j = i+1 ; j< A.length ; j++)
            {
                if(A[i] > A[j]) inversions++;
            }
        }
        
        if(inversions % 2 == 0) return "YES";
            
        return "NO";
    }

    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[] A = new int[n];

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

            for (int i = 0; i < n; i++) {
                int AItem = Integer.parseInt(AItems[i]);
                A[i] = AItem;
            }

            String result = larrysArray(A);

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

        bufferedWriter.close();

        scanner.close();
    }
}

Ema's Supercomputer

19 Sep 2018 Tags:

HackerRank, Implementation

HackerRank link

Ema’s Supercomputer

풀이 핵심

중복이 허용되지 않으므로, 직접 다 구해봐야한다.
결과값이 x 로 나오므로, 가장 큰 십자가 2개의 곱이 항상 최대값으로 보장되지 않는다.

알고리즘이 어렵지 않는 문제
유사 문제: Cross Word Puzzle

Algorithm

십자가를 놓을 위치를 구한다.
최소 십자가 부터 최대 십자가까지 각각 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.*;

public class Solution {

    static class Point
    {
        public int x;
        public int y;
        public int size;
    }
    
    static int[][] dir =
    {
            // i , j
            {+1,+0},    // up
            {-1,+0},    // down
            {+0,-1},    // left
            {+0,+1},    // right
    };
    
    static ArrayList<Point> findAllPoint(char[][] map)
    {
        ArrayList<Point> pt = new ArrayList<>();
        for(int i = 0; i < map.length; i++)
        {
            for(int j = 0; j < map[i].length; j++)
            {
                // find good cell
                if(map[i][j] == 'G')
                {
                    // check good plus
                    /*
                    if( 
                        (map[i-1][j] == 'G') && (map[i+1][j] == 'G') && 
                        (map[i][j-1] == 'G') && (map[i][j+1] == 'G')
                    )
                    {
                    */
                        Point p = new Point();
                        p.x = j;
                        p.y = i;
                        p.size = getPlusSize(map, p.y, p.x);
                        
                        // System.out.println("found"+j+","+i);
                        
                        pt.add(p);
                    //}
                }
            }
        }
        
        return pt;
    }
    
    static int getPlusSize(char[][] map,int _y, int _x)
    {        
        
        int minSize = Integer.MAX_VALUE;
        for(int i = 0 ; i < dir.length ; i++)
        {
            int size = 0;
            int x = _x + dir[i][1];
            int y = _y + dir[i][0];
            
            while( (y >= 0 && y < map.length) && (x >= 0 && x < map[y].length) && map[y][x] == 'G')
            {
                size++;
                x += dir[i][1]; 
                y += dir[i][0];
            }            
            
            if(minSize > size) minSize = size;
        }
        
        minSize = minSize * 4 + 1;
        
        return minSize;
    }
    
    static char[][] setCell(char[][] map, int _y, int _x, int size, char goodOrBad)
    {
        map[_y][_x] = goodOrBad;
        // System.out.println("setCell"+_y+","+_x+"/"+size);
        for(int i = 0 ; i < dir.length ; i++)
        {
            int y = _y;
            int x = _x;
            for(int l = 0 ; l < size ; l++)
            {
                y += dir[i][0];
                x += dir[i][1];
                        
                map[y][x] = goodOrBad;
            }
        }
        
        for(int i = 0 ; i < map.length ; i++)
        {
            for(int j = 0; j < map[i].length ; j++)
            {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
        
        
        return map;
    }
    
    
    
    
    // Complete the twoPluses function below.
    static int twoPluses(String[] grid) {
        
        int max = 0;
        
        // convert String to char for convenient
        char [][] map = new char[grid.length][];
        for(int i = 0 ; i < grid.length ; i++)
        {
            map[i] = grid[i].toCharArray();
        }        

        ArrayList<Point> pt = findAllPoint(map);
        
        for(int i = 0 ; i < pt.size(); i++)
        {
            int[] totalSize = new int[2];
            // totalSize[0] = getPlusSize(map, pt.get(j).y, pt.get(j).x);
            totalSize[0] = pt.get(i).size;
            System.out.println("1."+pt.get(i).y +"," +pt.get(i).x +":" + totalSize[0]);
                        
            for(int size = 1 ; size <= pt.get(i).size ; size += 4)
            {
                // set 'B'
                int oneSideSize = (size - 1)/4;
                map = setCell(map, pt.get(i).y, pt.get(i).x, oneSideSize, 'B');

                ArrayList<Point> pt2 = findAllPoint(map);

                for(int j = 0 ; j < pt2.size() ; j++)
                {
                    totalSize[1] = getPlusSize(map, pt2.get(j).y, pt.get(j).x);

                    int temp = size * totalSize[1];

                    if(max < temp) max = temp;

                    System.out.println("2."+pt2.get(j).y +"," +pt2.get(j).x +":" + totalSize[1]);
                    System.out.println(max);
                }

                // revert
                System.out.println("revert");
                map = setCell(map, pt.get(i).y, pt.get(i).x, oneSideSize, 'G');
            }
            
        }
        
        return max;

    }

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

        String[] grid = new String[n];

        for (int i = 0; i < n; i++) {
            String gridItem = scanner.nextLine();
            grid[i] = gridItem;
        }

        int result = twoPluses(grid);

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

        bufferedWriter.close();

        scanner.close();
    }
}

Older Newer

Power Coding 파워 코딩

Highest Value Palindrome

HackerRank link

풀이 핵심

Algorithm

Source Code

Lily's Homework

HackerRank link

풀이 핵심

Algorithm

Source Code

Fraudulent Activity Notifications

HackerRank link

풀이 핵심

Algorithm

Source Code

Larry's Array

HackerRank link

풀이 핵심

Algorithm

Source Code

Ema's Supercomputer

HackerRank link

풀이 핵심

Algorithm

Source Code