Hackerrank Day 29 Bitwise AND

알고리즘 연습 사이트

www.hackerrank.com

Day 29:Bitwise AND

 Java D-Day 마지막 주제는 비트 연산에 대한 것이다.

* 참고사이트
 Truth_table : https://en.wikipedia.org/wiki/Truth_table
 Java Operator : https://docs.oracle.com/javase/tutorial/java/nutsandbolts/opsummary.html

* & Bitwise AND (∧)
둘 다 1이어야지 1, 둘 중 하나라도 0이라면 0이다.

* | Bitwise inclusive OR (∨)
둘 중 하나만 1이어도 1이다.

* ^ Bitwise Exclusive OR or XOR
두 개가 동일하다면 0, 두개가 다르다면 1이다.

* ~ NOT 
1이면 0으로, 0이면 1로 뒤집는 반대 연산자이다.

비트 연산자 마지막 문제는 두개의 숫자가 입력값으로 주어진다. $(N,K)$ 
집합 $S$ 의 요소들은 1~N까지이다. 
집합의 요소들끼리 & 연산을 했을 때 가장 큰 수가 나오는 것을 찾는 것이다. 다만 K보다는 작아야 한다.

K보다 작은 max 값을 찾는 부분만 주의하면 된다.

public class Solution {
    
    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            String[] nk = scanner.nextLine().split(" ");

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

            int k = Integer.parseInt(nk[1]);
            int max =0; 
            for(int i = 1 ; i <=n ; i++){
                for(int j=i+1 ; j <= n ; j++){
                    if((i&j)< k && (i&j)>max) {
                        max = i&j;
                    }
                }
            }
            System.out.println(max);
        }

        scanner.close();
    }
}

여기까지 D-Day 30 Java 튜토리얼을 완료하였다. :) 
다음은 Java 를 시작할 예정이다.

Hackerrank Day 28 RegEx, Patterns, and Intro to Databases

알고리즘 연습 사이트

www.hackerrank.com

Day 28:RegEx, Patterns, and Intro to Databases

 정규표현식(Regular expression)은 사용하려고 할 때마다 잊어버리고 다시 찾아보게 된다. 
 따라서 복습이 필요할 때마다 이 글을 참조하기 위해 기본 개념을 정리해 둔다.

* 참고 사이트

Pattern 클래스:  https://docs.oracle.com/javase/8/docs/api/java/util/regex/Pattern.html
Matcher 클래스: https://docs.oracle.com/javase/8/docs/api/java/util/regex/Matcher.html
정규표현식 튜토리얼:  https://docs.oracle.com/javase/tutorial/essential/regex/
정규표현식 연습사이트: 여러가지 연습할 수 있는 사이트들이 많지만 regex101.com가 가장 편리한것 같다. 내가 만든 정규식에 대해 동작원리 설명이 나와있어 학습하기 편하다.
https://regex101.com/
https://rubular.com/r/UAgzl9NxQv

* Character Classes
 일반적으로 생각하는 자바의 클래스와 같은 의미가 아니라, 한개 혹은 한 개 이상의 문자들의 집합을 의미한다. 
 Character Class라는 것은 문자 그 자체이거나 문자의 범위를 표현하는 문법이 될 수 있다. 
 예를 들면 정규표현식 a는  a 문자 하나에 매칭될 것이다.
 \d라는 것은 정규표현식 문법인데 미리 정의된 캐릭터 클래스라는 것이다. 의미는 a digit(숫자) 을 뜻한다. 
\d와 동일한 표현으로 [0-9] 역시, 0부터 9까지의 숫자중에 한 개만 일치하면 된다는 조건이다.

 점(.) 은 정규표현식 문법 중 [ ] (bracketed character class) 안에서는 일반 점(.) 문자를 의미하지만,
[ ] 밖에서는 개행문자(\n)를 제외한 아무 문자한 개를 뜻하는 Character Class이다. 
 고로 [ ] 밖에서도 일반 문자처럼 사용하고 싶다면 \(back slash, 역슬래시) 를 앞에 붙여서 escape 해야 한다.


* Quantifier(수량사)
캐릭터 클래스 뒤에 붙어서 그 캐릭터클래스가 몇 번을 반복하는지 조건을 설정 하는 문법이다.

X? : X가 1개 이거나 0개의 횟수
X+ : X가 1개 이거나 그 이상의 횟수 
X* : X가 0개 이거나 그 이상의 횟수 
X{n} : X가 정확히 n번의 횟수
X{n, } : X가 최소 n번의 횟수
X{n,m} : X가 최소 n번에서 m번 사이의 횟수 (m횟수 포함)

^ , $
 캐릭터 클래스 앞에 ^ 이 문자가 오게 되면 그 캐릭터 클래스가 첫번째 문자여야 한다는 의미이다. 
 그러나 [ ] 안에 ^ 문자가 존재한다면 not 이 된다. 
 예를 들면 ^[a].+ 혹은 ^a.+은 a로 시작하는 2개 혹은 그 이상의 문자를 찾아내지만, ^[^a].+은 a로 시작하지 않는 2개 혹은 그 이상의 문자를 찾아낸다.
 $는 바로 앞의 캐릭터 클래스로 끝나야 함을 나타낸다.

 이번 문제는 이름과 이메일 주소를 공백으로 연결하여 입력값이 주어진다. 이메일 주소는 반드시 @gmail.com 이여야 하며 이름은 20자를 넘을 수 없다. 
전체 이메일 주소 길이는 50자를 넘을 수 없다.
위 조건에 맞는 이메일 주소를 가진 이름을 오름차순으로 정렬해야 한다.  

public class Solution {
    
    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int N = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
        String regexEmailId = "[a-z]{1,40}@gmail\\.com";
        String regexFirstName = "[a-z]{1,20}";
        Pattern pEmailId = Pattern.compile(regexEmailId);
        Pattern pfirstName = Pattern.compile(regexFirstName);
        List<String> resultList = new ArrayList<String>();

        for (int NItr = 0; NItr < N; NItr++) {
            String[] firstNameEmailID = scanner.nextLine().split(" ");

            String firstName = firstNameEmailID[0];

            String emailID = firstNameEmailID[1];

            Matcher firstNameM = pfirstName.matcher(firstName);
            Matcher emailM = pEmailId.matcher(emailID);

            if(!emailM.find()){
                continue;
            }
            if(firstNameM.find()){
                resultList.add(firstName);
            }
            
        }
        Collections.sort(resultList);
        for(String temp : resultList)
            System.out.println(temp);

        scanner.close();
    }
}

Hackerrank Day 27 Testing

알고리즘 연습 사이트

www.hackerrank.com

Day 27:Testing

 단위 테스트의 목적은 개발 코드 단위(예: 함수) 가 예상대로 작동하는지 확인하는 것이다.
함수에 대해 테스트 함수 코드를 작성할 때 예상하는 모든 결과가 다뤄지기를 원할 것이다.

1. 함수가 예기치 않는 결과값을 낼 것으로 생각되는 인수를 인자로 받아본다.
2. 경계값을 인자로 넣어서 테스트한다.
3. 특정 실행 패턴에서 예외를 던질 경우에 대해서도 테스트 해야한다. 

오늘 문제는 테스트 코드를 작성해보는 것인데,
아래는 배열에서 최소값을 갖는 배열의 인덱스를 가져오는 함수이다.

 public static int minimum_index(int[] seq) {
        if (seq.length == 0) {
            throw new IllegalArgumentException("Cannot get the minimum value index from an empty sequence");
        }
        int min_idx = 0;
        for (int i = 1; i < seq.length; ++i) {
            if (seq[i] < seq[min_idx]) {
                min_idx = i;
            }
        }
        return min_idx;
    }class TestDataEmptyArray {
    public static int[] get_array() {
        return new int[]{};
    }
}

아래는 오늘 문제의 구현 코드인데 다양한 조건의 배열을 만들어서 리턴한다. 빈 배열, 유니크한 데이터 배열, 최소값을 최소 2개 이상 갖는 배열을 리턴해 본다. 
특이 케이스 상황을 임의로 만들어보는 것이다.

static class TestDataEmptyArray {
    public static int[] get_array() {
        return new int[]{};
    }
}

static class TestDataUniqueValues {
    public static int[] get_array() {
        return new int[]{1,2,3,4,5};
    }

    public static int get_expected_result() {
        return minimum_index(get_array());
    }
}

static class TestDataExactlyTwoDifferentMinimums {
    public static int[] get_array() {
         return new int[]{1,2,3,4,3,2,1};
    }

    public static int get_expected_result() {
        return minimum_index(get_array());
    }
}

실제로 테스트 할 때 위에서 생성한 배열들을 대상으로 테스트를 진행하고 특이 케이스에서 예외 처리 코드를 작성 해주면 된다. 
아래 코드는 hackerrank에 있는 코드를 가져왔다.
  

public static void TestWithEmptyArray() {
        try {
            int[] seq = TestDataEmptyArray.get_array();
            int result = minimum_index(seq);
        } catch (IllegalArgumentException e) {
            return;
        }
        throw new AssertionError("Exception wasn't thrown as expected");
    }

    public static void TestWithUniqueValues() {
        int[] seq = TestDataUniqueValues.get_array();
        if (seq.length < 2) {
            throw new AssertionError("less than 2 elements in the array");
        }

        Integer[] tmp = new Integer[seq.length];
        for (int i = 0; i < seq.length; ++i) {
            tmp[i] = Integer.valueOf(seq[i]);
        }
        if (!((new LinkedHashSet<Integer>(Arrays.asList(tmp))).size() == seq.length)) {
            throw new AssertionError("not all values are unique");
        }

        int expected_result = TestDataUniqueValues.get_expected_result();
        int result = minimum_index(seq);
        if (result != expected_result) {
            throw new AssertionError("result is different than the expected result");
        }
    }

    public static void TestWithExactlyTwoDifferentMinimums() {
        int[] seq = TestDataExactlyTwoDifferentMinimums.get_array();
        if (seq.length < 2) {
            throw new AssertionError("less than 2 elements in the array");
        }

        int[] tmp = seq.clone();
        Arrays.sort(tmp);
        if (!(tmp[0] == tmp[1] && (tmp.length == 2 || tmp[1] < tmp[2]))) {
            throw new AssertionError("there are not exactly two minimums in the array");
        }

        int expected_result = TestDataExactlyTwoDifferentMinimums.get_expected_result();
        int result = minimum_index(seq);
        if (result != expected_result) {
            throw new AssertionError("result is different than the expected result");
        }
    }

Hackerrank Day 26 Nested Logic

알고리즘 연습 사이트

www.hackerrank.com

Day 26:Nested Logic

 D-Day 문제도 거의 막바지다.


 오늘은 도서관 대출 벌금 계산하기이다.
 간단하게 설명하면 반납예정년보다 반납년이 늦으면 요금이 $10000$이다. 제때 반납했으면 물론 요금은 0이며, 달이 늦으면 $500 * (반납월-반납예정월)$ 을 계산한다.
마찬가지로 동일한 년월에서 일자만 늦는 경우에는
$15 * (반납일 - 반납예정일)$ 이다.

 가독성이 정말 떨어지지만 문제 통과는 하였다.
 코드를 작성 할 때마다 느끼는 것이지만 이 고정적인 사고 습관에서 벗어나기란 참 어렵다.


*처음작성코드

public class Solution {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        
        String returnDate = sc.nextLine();
        String dueDate = sc.nextLine();

        String [] returnDateArr = returnDate.split(" ");
        String [] dueDateArr = dueDate.split(" ");
        int[] iReturnDateArr =new int[3];
        int[] iDueDateArr = new int [3];

        for(int i = 0 ; i < returnDateArr.length;i++){
            iReturnDateArr[i] = Integer.parseInt(returnDateArr[i]);
        }
        for(int i = 0 ; i < dueDateArr.length;i++){
            iDueDateArr[i] = Integer.parseInt(dueDateArr[i]);
        }

        int fine = 0; 
        //0 : day , 1: month , 2 : year
        if(iReturnDateArr[2] <= iDueDateArr[2]){ //년비교
            if(iReturnDateArr[2] == iDueDateArr[2]){
                if(iReturnDateArr[1] <= iDueDateArr[1]){
                    if(iReturnDateArr[0] <= iDueDateArr[0]){
                        fine=0;
                    }else{
                        fine= 15 * (iReturnDateArr[0] - iDueDateArr[0]);
                    }
                }else{ //반납월이 늦으면
                    fine = 500 * (iReturnDateArr[1] - iDueDateArr[1]);
                }
            }else{
                fine = 0;
            }
        }else{ //반납 년도가 더 클 경우
            fine = 10000;
        }
        System.out.println(fine);

    }
}

 위 코드에서 stdin으로 입력을 받는 부분은 논외로 쳐도, 가장 큰 문제점은 쓸때 없는 if문 구절이 많이 중복되었다.
fine=0을 처리하는 조건들을 반대로 걸어 코드를 더 축약할 수 있다.


*개선버전

public class Solution {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        
        int rDay = sc.nextInt();
        int rMonth = sc.nextInt();
        int rYear = sc.nextInt();

        int eDay = sc.nextInt();
        int eMonth = sc.nextInt();
        int eYear = sc.nextInt();

        int fine=0;

        if(rYear < eYear){
            fine = 0;
        }else{
            if(rYear > eYear){
                fine = 10000;
            }else if(rMonth > eMonth){
                fine = 500 * (rMonth-eMonth);
            }else if(rDay > eDay){
                fine = 15 * (rDay - eDay);
            }
        }

        System.out.println(fine);
    }
}

Date 객체를 사용할 필요까지도 없고 문제 자체가 년, 월, 일만 비교하는 것이기 때문에 단순 숫자만으로 계산해도 무리가 없다.

Hackerrank Day 25 Running Time and Complexity

알고리즘 연습 사이트

www.hackerrank.com

Day 25:Running Time and Complexity

알고리즘의 복잡성이나 성능을 따져볼 때 asymptotic notation(점근 표기법)을 사용하여 나타낸다.
아무리 성능이 느린 알고리즘도 CPU가 좋다면 느린 CPU에서 성능이 좋은 알고리즘보다 빠를 수 있다.
 때문에 이러한 기계의 성능과는 독립적으로 알고리즘 그 자체에 대한 성능을 알아보기 위해 점근 표기법을 사용한다.

$f(n)$은 내가 만든 알고리즘을 나타내고 $g(n)$는 어떤 점근적으로 도달되는 함수를 나타낸다.
점근적으로 도달될 때 특징이 있는데, 내가 만든 알고리즘이 성능의 최소치보다는 항상 위이거나, 최대치보다는 항상 아래일 수 있다. 
그러한 특징을 세타나 빅오 등으로 표기하는 것이다.


1. $\Theta$ notation
세타 표기법, $f(n) = \Theta(g(n))$
즉 $f(n)$이 $g(n)$사이에 있기 때문에 $f(n) = g(n)$이라고 봐도 된다.
$ c1·g(n) ≤ f(n) ≤ c2·g(n) $ 


2. Big-Ο notation
빅 오 표기법, $f(n) = O(g(n))$
$f(n) ≤ g(n)$


3. $\Omega$ notation

빅 오메가 표기법, $f(n) = \Omega(g(n))$
$f(n) ≥ g(n)$

 오늘 문제는 소수를 찾는 알고리즘을 만들어보는 것이다. 
어떠한 $n$이 소수인지 아닌지 판별하는 방법은 찾고자하는 수를 $2$ 부터 $\sqrt n$까지 $1$씩 증가시키면서 나누면서 나누어 떨어진다면 소수가 아니고 나누어 떨어지지 않는다면 소수이다.  
 이 원리 혹은 증명은 여기서 다루지 않는다. 일단 이 공식만 알면 코드 작성은 쉽다. 
 아래 코드의 소스 알고리즘은 $O(\sqrt n)$ 의 복잡도를 가진다. 
 $g(n)$이 $\sqrt n$인데 최대 $\sqrt n$ 수까지 나누어봐야 소수인지 아닌지 알아낼 수 있기 때문이다. $\sqrt n$ 보다는 복잡도가 높아질 수 없으므로 빅 오 표기법으로 나타낼수 있다. 

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        //Read input from STDIN. 
        int count = sc.nextInt();
        int [] arr = new int[count];

        for(int i = 0 ; i < count;i++){
            arr[i] = sc.nextInt();
        }

        for(int k= 0 ; k < count ; k++){
          
            if(isPrime(arr[k])){
                System.out.println("Prime");
            }else{
                System.out.println("Not prime");
            }
        }
    }

    public static boolean isPrime(int n){
        if(n == 1){
            return false;
        }
        if(n == 2){
            return true;
        }
        for (int i = 2; i<=Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Hackerrank Day 24 More Linked Lists

알고리즘 연습 사이트

www.hackerrank.com

Day 24:More Linked Lists

 Linked List 관련 3번째 문제이다. 
자료구조 관련 문제는 역시 어렵지만 풀고나면 재밌다. 

 이 문제의 포인트는 노드들의 첫 시작 주소인 head 참조값을 잘 갖고 있다가 반환해야 한다는 것이다.

 
 다음 노드의 참조 값을 변수로 가지고 있는 노드들 리스트의 head 노드의 참조값이 메소드 인자로 주어지고, 이 노드 리스트의 data 변수에 있는 값 중 중복된 값을 제거하라는 문제이다. 
 다만 항상 data가 오름차순으로 정렬된 노드 리스트가 주어진다.

class Node{
 int data;
 Node next;
 Node(int d){
        data=d;
        next=null;
    }
 
}

public static Node removeDuplicates(Node head) {
    if(head == null) //head가 null일 때 처리
        return null;
    Node s = head; // s 변수에 head 참조 값을 저장한다.
    while(s.next != null){//while안에서 s변수를 이용하여 노드리스트들을 조작한다.
        if(s.data == s.next.data)//현재 노드의 data값과 다음노드의 데이터값이 일치하면
            s.next = s.next.next; //현재 노드 next 변수에 노드 하나를 건너뛴 다음의 주소값을 저장한다.
        else // 중복되지 않으면 
            s = s.next; //다음 노드 참조값을 s에 대입한다.
    } 
    return head;
}

 return을 할 때는 s 참조 변수가 아닌 head 변수를 반드시 리턴해야한다. 
 잘 생각해보면 s는 while문이 돌면서 값이 계속 변경되고 있어서 head값은 이미 잃어버린 상태이다. 
결국 모든 노드리스트들의 첫 시작 지점 주소 값인 head 를 리턴하면 될 것이다.

Hackerrank Day 23 BST Level-Order Traversal

알고리즘 연습 사이트

www.hackerrank.com

Day 23:BST Level-Order Traversal

트리를 접근하는 순서에는 여러가지가 있다.


 1. InOrder Traversal
 일반적인 순서대로 트리의 노드를 접근한다. 
left-root-right 순서이다.

 2. PostOrder Traversal
 Post라는 말에서 유추할 수 있듯이 root 노드를 마지막에 두는 순서를 말한다. left-right-root 순서이다.

 3. PreOrder Traversal(DFS)
 PreOrder는 root노드를 가장 먼저 접근한다. 
root-left-right.  Depth-first-search라고도 한다.

 4. Level-Order Traversal(BFS)
 트리의 레벨 순서대로 검색한다. breath-first-search라고도 한다.

예시를 보면 위 4가지 방법을 어떤 순서로 진행되는지 이해하기 쉽다. 
아래 링크에서 이미지를 가져왔다.

https://www.hackerrank.com/challenges/30-binary-trees/tutorial

hackerrank-Binary Tree

• InOrder: 1 2 3 4 5 6 7
• PostOrder: 1 3 2 5 7 6 4
• PreOrder: 4 2 1 3 6 5 7
• Level-Order: 4 2 6 1 3 5 7

이번 문제는 Binary search tree에서 Level-Order Traversal 방식대로 데이터를 꺼내와서 출력해야 한다.
이 문제를 해결하기 위해 Queue를 이용하면 매우 쉽게 문제가 해결된다. 
Day 18:Queues and Stacks 글 참조


 대표적인 Queue를 구현하는 클래스인 LinkedList 객체를 생성하고, 이 list에 2진탐색트리인 root 노드를 add한다.
 poll 메소드를 사용하였는데 poll은 리스트에 저장된 요소를 가져오면서 그 요소를 list 내에서 삭제해 준다. 
그리고 tmpNode에 현재 꺼내온 노드의 참조 주소를 저장하여 현재 노드의 left, right 자식이 존재하는지 체크하고 존재한다면 list에 add한다.  
add 할 때 주의점은 왼쪽에서 오른쪽 순으로 출력될 수 있도록 왼쪽부터 넣어야한다. 
 list가 비어있지 않는 동안은 계속 while문이 돌면서 data 값을 출력하게 된다.
 while문의 마지막에서 peek 메소드를 써 봤는데, 그다음 list에 요소가 존재할 때에만 data 간에 띄어쓰기를 넣어서 표출하기 위해서이다. 
 peek은 poll과 다르게 요소를 삭제 하지 않으므로 자식이 있다면 다음 반복을 탈 수 있게 된다.

static void levelOrder(Node root){
      LinkedList<Node> list = new LinkedList<Node>();

      list.add(root);
      while(!list.isEmpty()){
          Node tmpNode = list.poll();
          System.out.print(tmpNode.data);
          
          if(tmpNode.left != null){
              list.add(tmpNode.left);
          }
          if(tmpNode.right != null){
              list.add(tmpNode.right);
          }
          if(list.peek() != null)
            System.out.print(" ");
      }
}

Hackerrank Day 22 Binary Search Trees

알고리즘 연습 사이트

www.hackerrank.com

Day 22:Binary Search Trees

2진 트리(Binary Trees)

 2진 트리의 가장 깊은 노드까지의 거리 (height)를 계산하는 메소드를 구현한다. 
즉 root 노드로부터 가장 먼 자식 노드까지의 거리를 구하는 것이다. 
 2진 트리는 right, left 노드 2개를 갖거나 둘 중의 하나의 자식만 갖거나 아예 자식이 존재하지 않는다.(leaf)

 오늘 문제의 키 포인트는 인자로 들어오는 root노드의 자식 노드를 검사할 때, right, left 자식 노드가 각각 존재하는지 한번에 체크를 해야한다.

 각 사이드의 자식 노드가 존재한다면 해당 높이변수에 1을 더하고 그의 하위자식노드를 인자로 넘겨주어 재귀호출을 한다. 
 주의깊게 살펴봐야 할 부분은 return 부분인데 이곳에서 max height 을 처리한다.

 자식노드가 몇 개가 달려있건간에 자식노드가 존재하지 않을 때까지 재귀호출 되어 결국 마지막 leaf노드에 도달하였을 때 right과 left중 큰 쪽의 height 을 리턴한다. (깊이가 깊은 것이 2개가 있다고 해도 어쨌든 둘중의 하나를 리턴한다.) 그러면 재귀호출이 된 지점으로 반환되면서 결국 가장 최초의 getHeight 메소드 호출의 리턴에서 가장 큰 height값을 구할 수 있다.

 2진 트리가 어떻게 구성되고 특징이 무엇인지 이해하여야 풀 수 있었던 문제였다.

public static int getHeight(Node root){
        int heightLeft = 0;
        int heightRight = 0;
        
        if(root.left !=null){
            heightLeft = 1 + getHeight(root.left);
        }
        if(root.right !=null){
            heightRight = 1 + getHeight(root.right);
        }
        return heightLeft > heightRight ? heightLeft : heightRight; 
}

Hackerrank Day 21 Generics

알고리즘 연습 사이트

www.hackerrank.com

Day 21:Generics

Generics 참고 URL - oracle API 
Generic Types
Generic Methods
Type Inference



배열의 요소들을 출력하는 printArray 메소드를 제네릭을 이용하여 구현한다.
Printer 클래스의 인스턴스를 만들 때 데이터 타입을 지정해야한다. Class Printer가 제네릭으로 선언되어 있기 때문이다.
class안에 T로 되어있는 부분들은 인스턴스 생성시 지정했던 데이터 타입으로 전부 변환된다.


아래 코드를 보면 이해하기가 쉽다.

class Printer <T> { //class 선언 시 제네릭으로 데이터형을 선언한다.

    /**
    *    Method Name: printArray
    *    Print each element of the generic array on a new line. Do not return anything.
    *    @param A generic array
    **/
    
    // Write your code here

    void printArray(T[] array){ //다양한 형태의 데이터 타입 배열을 인자로 받아들일 수 있다.
        for(T temp : array){
            System.out.println(temp);
        }
    }
}

public class Generics {
    
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Integer[] intArray = new Integer[n];
        for (int i = 0; i < n; i++) {
            intArray[i] = scanner.nextInt();
        }

        n = scanner.nextInt();
        String[] stringArray = new String[n];
        for (int i = 0; i < n; i++) {
            stringArray[i] = scanner.next();
        }
        
        Printer<Integer> intPrinter = new Printer<Integer>(); //T가 Integer가 됨
        Printer<String> stringPrinter = new Printer<String>(); //T가 String이 됨

        intPrinter.printArray( intArray  );
        stringPrinter.printArray( stringArray );
        if(Printer.class.getDeclaredMethods().length > 1){
            System.out.println("The Printer class should only have 1 method named printArray.");
        }
    } 
}

Hackerrank Day 20 Sorting

알고리즘 연습 사이트

www.hackerrank.com

Day 20:Sorting

 20일차는 Bubble sort에 대해 간략히 배웠다. 

 정렬되는 모습이 마치 거품처럼 위로 이동하는 것 처럼 보이기 때문에 Bubble이라는 말이 붙었다. 
 버블 정렬은 실제 현실세상에서 써먹기에는 그리 효율이 좋지 않기 때문에 학습 용도로만 배운다.

 버블정렬은 간단히 말하면 정렬을 할 때 인접한 두개의 값을 서로 비교하여 큰 값이 작은 값보다 앞에 있다면 두 값의 위치를 서로 바꾸는 것이다.


키 포인트는 최초 1회 비교에서 가장 큰 값은 마지막에 위치하게 된다.


 배열의 시작 지점부터 바로 인접한 변수를 계속 비교하여, swap하거나 그대로 두면서 배열의 끝까지 계속 비교해야 한다.
 그리고 2 싸이클에서 다시 배열의 처음으로 되돌아와서 다시 순서대로 비교한다. 

 규칙을 찾아내보면 배열의 길이에서 1을 뺀 만큼 도는 바깥 반복문 1개와, 그 내부에 인접한 두개의 변수를 비교하면서 배열의 위치를 계속 이동시키는 반복문이 필요하다. 


버블소트 기본 동작을 이해하고 나서 코드를 보면 이해가 쉽다.

오늘 문제는 버블소트를 구현하고 몇 번 swap이 일어났는지와 첫번째와 마지막 요소를 출력하는 것이다.

첫번째 버전은 마지막으로 스왑이 일어난 지점을 endPosition에 저장하고 endPosition만큼만 반복을 한다. 

이렇게 되면 어차피 마지막 값이 최대값이 들어있는 부분은 검사를 안하게 되는 이점이 있다.
그리고 endPosition이 0이 되면 while 반복문을 탈출하게 된다. 


(1) 첫번째 버블소트

public static void bubbleSort(int[] x) {
    printArray("Initial", x);

    int endPosition = x.length - 1;
    int swapPosition;

    while( endPosition > 0 ) {
        swapPosition = 0;

        for(int i = 0; i < endPosition; i++) {

            if( x[i] > x[i + 1] ){
                // Swap elements 'i' and 'i + 1':
                int tmp = x[i];
                x[i] = x[i + 1];
                x[i + 1] = tmp;

                swapPosition = i;
            } // end if

        } // end for

        endPosition = swapPosition;
    } // end while
} // end bubbleSort

(2) 두번째 버블소트

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for(int a_i=0; a_i < n; a_i++){
            a[a_i] = in.nextInt();
        }
        
        int numSwaps = 0; //Swap이 일어난 total 횟수
        int firstElement = 0; //첫번째 배열 데이터 저장
        int lastElement =0; //마지막 배열 데이터 저장
        int tmp = 0; 
        for(int i =0 ; i < a.length ; i++){ 
            for(int j = 0 ; j < a.length -1 ; j++){
                if(a[j] > a[j+1]){
                   tmp = a[j+1];
                   a[j+1] = a[j];
                   a[j] = tmp;
                   numSwaps++; 
                }
            }
        }
        System.out.println("Array is sorted in "+numSwaps+" swaps.");
        System.out.println("First Element: "+a[0]);
        System.out.println("Last Element: "+a[a.length-1]);
    }
}

두번째는 모든 루프에서 배열 전체를 다 검사하는 단순한 버블소트이다.

Hackerrank Day 19 Interfaces

알고리즘 연습 사이트

www.hackerrank.com

Day 19:Interfaces

 인터페이스는 추상클래스와 비슷하지만 좀 더 규칙을 강화한 문법이다. 
 인터페이스는 new를 이용하여 객체를 생성할 수 없다. 
 왜냐하면 인터페이스에는 몸체가 없는 메소드들 밖에 없기 때문이다.

인터페이스를 implement 하는 클래스들은 인터페이스의 메소드들을 무조건 구현해야 한다. 
 인터페이스를 implements해놓고 구현을 하지 않으면 컴파일 에러가 뜬다.

 인터페이스의 장점은 간단하게 말하면 이미 인터페이스를 구현한 클래스들이나 앞으로 구현될 클래스들의 기능이 예측이 가능하다는 것이다. 
 클래스를 직접 뜯어보지 않아도 기능을 예측 할 수 있다는 것은 실제 개발에서 매우 유용한 장점이다. 

 아래 문제는 어떤 자연수의 약수들의 합을 구현한 코드다.
AdvancedArithmetic 인터페이스를 구현한 것이 Calculator 클래스가 되고, Calculator 클래스에서는 반드시 divisorSum 메소드의 몸체를 구현해야만 한다. 

interface AdvancedArithmetic{
   int divisorSum(int n);
}
class Calculator implements AdvancedArithmetic {
    public int divisorSum(int n) {
        //약수들의 합 구하기
        int sum = 0;
        int i = 1 ;
        while(n >= i){
            if(n % i == 0){ //나누어 떨어지면
                sum += i ;
            }
            i++;     
        }
        return sum;
    }
}

i가 1부터 n이 될때까지 n을 나누면서 나머지가 0이면 나누어 떨어지므로 sum에 i의 값을 누적하고 sum을 리턴한다.

Hackerrank Day 18 Queues and Stacks

알고리즘 연습 사이트

www.hackerrank.com

Day 18:Queues and Stacks

 자료구조의 가장 기본이 되는 Queue와 Stack이다. 

*참고
Stack: https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
Queue: https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html

* Stack 
Last In First Out (LIFO).
가장 나중에 넣은 것이 처음에 나오는 형태. 
밑이 막혀 있는 그릇에 데이터를 차곡차곡 쌓고 꺼낼때는 가장 위부터 꺼낸다.

Stack 클래스에는 주요 메소드 3가지가 있다
-Push : Stack의 가장 맨위에 데이터를 추가한다.
-Peek : 가장 맨위의 데이터를 리턴하지만 데이터를 지우지 않는다.
-Pop : 가장 맨위의 데이터를 리턴하고 그 데이터를 지운다.

* Queue
First In First Out (FIFO)
처음에 넣은 것이 처음에 나오는 형태.
- Enqueue : 큐의 가장 마지막의 그 다음에 데이터를 넣는다.
- Dequeue : 큐의 가장 앞부분(head)의 데이터를 리턴하고 그 값을 큐에서 삭제한다. 그러고 나면 두 번째에 있던 데이터가 head가 된다. 




오늘 문제는 앞으로 읽으나 거꾸로 읽으나 동일한 단어나 문장이 되는 문자열을 찾아내는 것이다. 그러한 문장 혹은 구를 palindrome이라고 한다.

문자열을 char형으로 쪼개어 Stack과 Queue에 각각 넣고 Stack에서는 pop을 하여 리턴되는 문자와, Queue의 remove메소드를 호출하여 리턴되는 결과를 서로 비교하여 문자열의 절반까지 비교를 하여 값이 완벽히 동일하다면 palindrome, 다르다면 palindrome이 아닌 것이다.

여기서 중요한 것은 스택과 큐의 성질을 이해하고 클래스의 메소드의 사용법을 이해하면 된다.

위에 링크해 둔 API 문서에 상세히 나와 있다.

public class Solution {
    // Write your code here.
    Stack stack = new Stack();
    Queue queue = new LinkedList();

    void pushCharacter(char ch){
        stack.push(ch);
    }
    void enqueueCharacter(char ch){
        queue.add(ch);
    }
    char popCharacter(){
        return stack.pop();
    }
    char dequeueCharacter(){
        return queue.remove();
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String input = scan.nextLine();
        scan.close();

        // Convert input String to an array of characters:
        char[] s = input.toCharArray();

        // Create a Solution object:
        Solution p = new Solution();

        // Enqueue/Push all chars to their respective data structures:
        for (char c : s) {
            p.pushCharacter(c);
            p.enqueueCharacter(c);
        }

        // Pop/Dequeue the chars at the head of both data structures and compare them:
        boolean isPalindrome = true;
        for (int i = 0; i < s.length/2; i++) {
            if (p.popCharacter() != p.dequeueCharacter()) {
                isPalindrome = false;                
                break;
            }
        }

        //Finally, print whether string s is palindrome or not.
        System.out.println( "The word, " + input + ", is " 
                           + ( (!isPalindrome) ? "not a palindrome." : "a palindrome." ) );
    }
}

Hackerrank Day 17 More Exceptions

알고리즘 연습 사이트

www.hackerrank.com

Day 17:More Exceptions

 전날에 이어서 예외 처리 문제를 풀어보자. 
어떤 메소드에 예외를 던지겠다는 표시를 한 후, 메소드 안에서 throw 키워드를 이용하여 고의로 발생시킬 수 있다. 
그러면 메소드를 호출한 곳으로 예외는 전달된다. 
예외는 이런 식으로 계속 상위로 퍼져 나가는데 결국 최상위에서 예외는 반드시 잡아내어서(try~catch) 처리되어야 한다. 

아래 코드는 Calculator 클래스 안에 거듭제곱(n^p)을 구하는 power 메소드에서 중 N or P가 음수일 때 예외를 던지는 코드이다. 

class Calculator{
    int power(int n, int p) throws Exception{
        int result = 1;
        if(n<0 || p<0){
            throw new Exception("n and p should be non-negative");
        }else{
            for(int i = 0 ; i < p ; i ++){
                result *= n;
            }
        }
        return result;
    }
}

class Solution{

    public static void main(String[] args) {
    
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
        
            int n = in.nextInt();
            int p = in.nextInt();
            Calculator myCalculator = new Calculator();
            try {
                int ans = myCalculator.power(n, p);
                System.out.println(ans);
            }
            catch (Exception e) {
                System.out.println(e.getMessage());
            }
        }
        in.close();
    }
}

power 메소드를 호출한 상위부분으로 예외가 던져지고, 그 부분이 try 문으로 감싸지면서 예외를 catch한다.

Hackerrank Day 16 Exceptions - String to Integer

알고리즘 연습 사이트

www.hackerrank.com

Day 16:Exceptions - String to Integer

 코드를 작성하다 보면 예기치 못한 버그나 에러가 발생 할 수 있고 프로그램 동작이 멈출 수 있다.
 그런 상황에서 자바와 같은 언어는 예외처리 기능을 제공한다.

* try catch finally
 오류가 발생 할 수 있는 부분들을 try로 감싸고 catch로 에러를 잡는다.
 finally 안에는 try로 감싼 지점을 벗어나서도 반드시 실행되야 하는 코드들을 작성한다. 
finally로 감싸진 부분은 에러가 발생하더라도 무조건 실행되야 하는 코드를 작성한다.

* try with resources (1.7)
 java.lang.AutoCloseable 이나 java.lang.Closeable 클래스들을 구현하는 클래스들의 exception 처리 시 자원을 자동으로 close 해주는 유용한 문법이다. 
AuthCloseable과 Closeable 클래스를 구현하는 대표적인 클래스들은 Scanner, BufferedReader 등과 같은 IO 클래스들이다.

try(Scanner scan = new Scanner();){
      // 잠재적으로 예외가 발생할 가능성이 있는 코드를 작성 
} //괄호를 벗어나면 자원을 자동 해제

Closeable이나 AutoCloseable만 구현하는 클래스이기만 하면 예외 처리나 try 구문을 벗어날 때 자동으로 close() 가 호출된다.

오늘 문제는 String을 Integer로 변환하면서 숫자는 출력하고 문자열을 변환하려고 할 때는 try catch 구문을 이용해 에러 메시지를 출력하도록 한다.

public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String S = in.next();
        try{
            int n = Integer.parseInt(S);
            System.out.println(n);

        }catch(Exception e){
            System.out.println("Bad String");
        }
    }
}

Hackerrank Day 15 Linked List

알고리즘 연습 사이트

www.hackerrank.com

Day 15:Linked List

List reference: https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html

Linked List 연결된 리스트, 리스트의 요소 한개가 다음 요소(노드)와 연결되어 있다는 의미이다. 
자세한 내용은 위의 java API docs 참조 문헌에 있다.
링크드 리스트에서 노드들은 다음번 차례의 노드의 참조 주소를 가지고 있어서 아래의 그림과 같이 연결이 되는 형태이다. 
마지막 tail 노드는 다음 요소가 없기 때문에 null를 가르키는 특징을 가진다.

LinkedList

정의된 Node 클래스를 이용하여 LinkedList의 insert 메소드를 구현해보는 것이 Day 15의 문제이다.

KeyPoint는 첫번째 Head Node의 객체의 참조 주소를 절대로 잃어버려서는 안된다는 점이다.

새로 생기는 노드로 참조를 이동해서 연결해야 한다(?)는 강박관념에 사로잡혀 굉장히 어렵게 문제를 풀었다.
지금 구현하고자 하는 insert 메소드는 최초의 노드를 계속 return 해주어야 하는게 핵심이다. 
왜냐하면 첫번째 노드를 잃어버리게 되면, LinkedList 객체의 참조 주소 자체를 잃어버리는 것과 같다.
시작 노드자체가 Null인 경우/중간 노드/꼬리 노드의 특징을 이용하여 if 분기 처리를 한다.  
중간 노드인 경우 next 값이 존재 하므로 next가 null인 경우까지 반복하면서 꼬리를 찾다가 꼬리노드의 next에 새로운 노드를 만들어 값을 넣으면 된다.



노드 클래스는 아래와 같이 next 라는 다음 노드의 주소를 저장하는 참조변수와, data를 저장하는 int형 변수로 이루어져 있다.

class Node {
   int data;
   Node next;
   Node(int d) {
       data = d;
       next = null;
   }
}

방법은 해커스랭크의 도움을 받아 2가지로 정리해보았다.
1번 방법이 코드상으로 더 깔끔해 보인다. 
소스 코드를 보면 메소드 인자로 전달되는 head 변수가 다른 노드 주소로 변동되는 지점이 전혀 없다.

//1번 방법

public static Node insert(Node head,int data) {
    if(head == null){ //처음 시작 지점. head 가 null로 들어온 경우.
        return new Node(data);
    }else if(head.next == null){ //꼬리노드라면,
        Node newNode = new Node(data); //새로운 노드를 만들면서 data를 생성자를 통해 초기화
        head.next = newNode; // 현재 노드의 next 변수에 새로 만든 노드의 참조주소를 세팅한다.
    }else{ //중간 노드라면,
        insert(head.next , data); //재귀 호출을 통해 자신의 꼬리를 찾는다.
    }
    return head; //계속 head 노드를 리턴해 주어 첫번째 참조 변수 값을 잃지 않는다.
}

//2번 방법

public static Node insert(Node head,int data) {    
    if(head == null){ //1번과 동일
        return new Node(data);
    }else if(head.next == null){ //1번과 동일
        Node nextNode = new Node(data);
        head.next = nextNode;
    }else{ //중간 노드라면,
        /*
          tmp 참조 변수에 head 참조 주소를 복사한다.
          head의 값을 복사하는 경우는 while문 안에서 꼬리노드를 찾기 위해 tmp값에 변동이 일어난다.
          만약 tmp 값을 복사하지 않고 head값을 그대로 이용하면 head 참조변수 값을 잃어버리게 된다. 
        */
        Node tmp = head; 
        while(tmp.next !=null){ //tmp의 next가 null이 아닐 때까지 반복한다.
            tmp = tmp.next; //tmp에 tmp.next를 대입하여 다음 노드의 next값을 계속 체크 할 수 있도록 한다.
        }
        //while문을 벗어났다면 tmp는 꼬리노드일 것이다.
        tmp.next = new Node(data);//꼬리 노드의 next에 새로운 노드를 추가한다.
    }
    return head;
}

Hackerrank Day 14 Scope

알고리즘 연습 사이트

www.hackerrank.com

Day 14:Scope

스코프라는 것은 프로그램 안에서 어떤 변수가 미치는 영역, 범위를 말한다. 
어떤 변수가 선언되면 그 지역을 벗어날 때까지 그 변수는 유효하다.
생성자의 파라미터는 보통 인스턴스 변수와 이름을 동일하게 하고 this 키워드를 이용하여 값을 초기화 해준다. 


14일차는 int 형의 양수 배열 elements에 대해 절대값이 가장 큰 숫자를 구하는 문제이다.

어떤 두 수의 뺄셈의 절대값이 가장 크려면, 가장 큰 수에서 가장 작은 수를 빼면 된다.
두 수의 거리가 가장 긴게 절대값이 크다고 이해하면 될 것이다.
배열을 sort하면 기본 오름차순 정렬이 된다.
그리고 마지막 배열의 숫자와 0번째 숫자를 빼면 된다. 
elements에 들어있는 수에는 음수가 없으므로 단순히 빼주기만 하면 된다.

 

class Difference {
   private int[] elements;
   public int maximumDifference;

    Difference(int[] elements){
        this.elements = elements;
    }

    void computeDifference(){
        Arrays.sort(elements); //오름차순 정렬
        maximumDifference = elements[elements.length-1] - elements[0];
    }
} 

Hackerrank Day 13 Abstract Classes

알고리즘 연습 사이트
www.hackerrank.com


Day 13:Abstract Classes



추상 클래스란 ?

class를 abstract 로 선언하기만 하면 추상 클래스다. 추상 클래스 그 자체로는 인스턴스를 생성할 수 없다. 
body가 없는 추상 메소드가 1개 이상 포함되어 있어서 인스턴스를 생성할 수 없기 때문이다. 
추상 클래스를 반드시 subclass가 extends를 하여 abstract 선언된 메소드들의 body를 구현하고나서야 subclass의 인스턴스 생성(new 키워드)을 할 수 있다. 
Day 12에서 배웠던 상속 개념을 확장시킨 것이 추상 클래스 이다.

13일 문제는 추상클래스 Book을 상속하는 MyBook 클래스를 구현하는 것이다.

abstract class Book {
    String title;
    String author;
    
    Book(String title, String author) {
        this.title = title;
        this.author = author;
    }
    
    abstract void display(); //추상 메소드
}

class MyBook extends Book{ //Inherits from Book
    int price;
    MyBook(String title, String author, int price){
        super(title, author);
        this.price = price;
    }
     void display(){ //추상 메소드를 구현
        System.out.println("Title: "+title);
        System.out.println("Author: "+author);
        System.out.println("Price: "+price);
    }
}

Hackerrank Day 12 Inheritance

알고리즘 연습 사이트
www.hackerrank.com


Day 12:Inheritance



상속의 개념에 대해 정리해본다.

아래 소스 코드의 예시에서 Person은 부모클래스(superclass) 이며 Student 는 자식클래스(subclass) 이다.
자바의 상속은 오직 '한번' 만 허용한다.
즉 subclass는 superclass를 extents 딱 한 번만 할 수 있다.

자식 클래스가 부모 클래스의 변수, 메소드들을  그대로 상속받는데, 유일하게 상속되지 않는 것이 생성자(Constructor) 이다.

생성자라는 것 자체가 자기 자신의 클래스의 인스턴스를 초기화하는 것이다. 때문에 절대로 상속되지 않는다. 

생성자를 특별히 만들지 않으면 기본적으로 자동으로 디폴트 (비어있는) 생성자가 만들어 진다.
생성자를 새로 정의하여 파라미터를 추가하여 값을 초기화하는 경우 디폴트 생성자는 생성되지 않는다.

부모클래스를 상속하는 자식클래스는 부모클래스의 생성자를 반드시 먼저 호출해야만 한다.
그 호출을 하기 위한 방법은 super();이다.
부모클래스와 자식 클래스 둘 다 아무런 생성자를 명시하지 않은 경우에도, 자식 클래스의 자동으로 만들어지는 생성자 안에는 부모의 생성자를 호출 할 수 있게 하는 super(); 가 존재한다.

subclass인 Student 클래스에서 생성자를 이용하여 인스턴스 변수들을 초기화 하는데, 생성자가 아래의 코드와 같이 정의 되어 있는 경우에는 디폴트 생성자가 생성 되지 않기 때문에 자식 클래스의 생성자 안에서 반드시 부모 클래스의 생성자를 호출해야만 한다. 

그러면 Student 클래스를 new 할 때 Studnet의 생성자가 호출되고 super로 인해 부모의 생성자까지 호출되면서 부모의 인스턴스 변수까지 초기화 된다.

Student 객체를 생성하면 Student는 Person의 속성들을 전부 상속받았기 때문에, 
Person의 속성을 지니는 Student 객체가 한 개 만들어지게 진다. 

class Person {
 protected String firstName;
 protected String lastName;
 protected int idNumber;
 
 // 부모클래스 생성자 정의. 디폴트 생성자는 없다.
 Person(String firstName, String lastName, int identification){ 
  this.firstName = firstName;
  this.lastName = lastName;
  this.idNumber = identification;
 }
 
 // Print person data
 public void printPerson(){
   System.out.println(
    "Name: " + lastName + ", " + firstName
   +  "\nID: " + idNumber);
 }
 
}

class Student extends Person{
 private int[] testScores;

    /* 
    *   자식클래스 생성자 정의
    *   super 키워드로 부모 클래스의 생성자를 호출하여 부모 클래스의 인스턴스 변수를 초기화.
    *   그리고 자신의 인스턴스 변수를 초기화 한다.
    */
    // Write your constructor here
        public Student(String firstName, String lastName, int id, int[] scores){
            super(firstName,lastName,id);
            testScores = scores;
        }

    // 계산 메소드. 
    public char calculate (){
        char grade;
        int arg = 0;;
        for(int i = 0 ; i < testScores.length;i++){
            arg += testScores[i];
        }
        arg = arg / testScores.length;

        if(arg >= 90 && arg <= 100){
            grade = 'O';
        }else if(arg >= 80 && arg <= 90){
            grade = 'E';
        }else if(arg >= 70 && arg <= 80){
            grade = 'A';
        }else if(arg >= 55 && arg <= 70){
            grade = 'P';
        }else if(arg >= 40 && arg <= 55){
            grade = 'D';
        }else{
            grade = 'T';
        }
        return grade;
    }
}

위 클래스를 사용할 때는 아래와 같다.

Student s = new Student(firstName, lastName, id, testScores);
s.printPerson(); //자식 클래스에서 오버라이드를 하지 않았기 때문에 부모클래스의 메소드를 호출한다.
System.out.println("Grade: " + s.calculate() );

[결과예시]

Name: Memelli, Heraldo
ID: 8135627
Grade: O

Hackerrank Day 11 2D Arrays

알고리즘 연습 사이트
www.hackerrank.com


Day 11:2D Arrays


이번 문제는 아래 예시의 6x6 배열이 주어지는데,

1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 2 4 4 0 0 0 0 2 0 0 0 0 1 2 4 0

위 배열에서 3x3의 모래시계 모양을 만들 수 있는 가짓수는 16가지가 된다.

1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 2 0 2 4 2 4 4 4 4 0 1 1 1 1 1 0 1 0 0 0 0 0 0 2 4 4 0 0 0 0 0 2 0 2 0 2 0 0 0 0 2 0 2 4 2 4 4 4 4 0 0 0 2 0 0 0 1 0 1 2 1 2 4 2 4 0

이 모래시계들의 합 중 가장 큰 값을 찾는 것이 Day 11의 문제이다.

아래 코드를 작성하다 보니 for문 중첩이 4개나 되어버렸다.
우선 가장 바깥 for문 2개는 전체 모래시계의 반복 16가지를 뜻한다.
그리고 안쪽의 for문 2개는 모래시계를 구성하는 요소 9가지를 뜻한다.

if문 안의 조건의 의미는 모래시계 요소가 아닌 것들의 인자들만 빼고 모조리 다 더하겠다는 의미이다.
arr[k+i][z+j] 라고 작성한 이유는 행과 열을 더해줘야 모래시계가 옆으로 한칸씩 이동하거나 아래로 내려가면서 위치가 이동되기 때문이다.

int[] sum = new int[16];
int number = 0;
int max = 0;
for(int i=0 ; i<4 ; i++){ // 행   
    for(int j=0 ; j < 4 ; j++ ){ //열
        for(int k=0; k<3 ; k++ ){
            for(int z=0 ; z<3 ; z++ ){
                if( !(k==1&&z==0) && !(k==1&&z==2))
                    sum[number] += arr[k+i][z+j];
            }  
        }
        if(sum[number] > max || (i ==0 && j ==0)){
            max = sum[number];
        }
        number++;
    }
}
System.out.println(max);

max값을 구하는 것은 이전 Day 10 문제에서 삽질을 좀 해서(?) 이번엔 쉽게 이해하였다.
max값을 대입하는 과정에서 (i ==0 && j ==0) 조건이 추가가 된 이유는, 이 조건을 안 넣으면 max값이 음수인 경우에 문제가 된다.

첫 모래시계의 sum 값을 반드시 max 에 대입하여 최대값이 음수일 때에도 정확하게 출력되게 해야한다.

cf ) 아래와 같이 sort를 사용해서도 max값을 출력할 수 있다.

Arrays.sort(sum); //기본 오름차순 정렬
System.out.println(sum[sum.lenght-1]);

Hackerrank Day 10 Binary Numbers

알고리즘 연습 사이트
www.hackerrank.com


Day 10:Binary Numbers


어떤 10진수를 입력받아 2진수로 변환하면서, 연속된 1이 최대 몇번 나오는가 라는 문제이다.
while문으로 몫(n)이 0보다 클때까지 돌면서 나머지가 1이면 count 수를 증가시킨다.
count가 백업된 숫자(back)보다 크거나 같을 경우 back에 count를 대입한다. 
중간에 나머지가 0인 경우 count수를 0으로 세팅하여 처음부터 다시 연속된 1을 센다.
그러다가 back에 저장된 수보다 같거나 커지게 되면 그 수를 다시 저장하는 것이다.

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

int remainder = 0; //나머지
int count=0 , back = 0;
while(n > 0){
    remainder = n % 2;
    n = n / 2;
   if(remainder == 1) {
      count++;
      if(count >= back) //Max value를 저장하는 것과 비슷
          back = count;   
   }else{
    count = 0;
   }
}
System.out.println(back);