[hackerrank] hackerrank challenges Day 25 자바 강의 리뷰

 

 

해커랭크 Day 25 챌린지를 시작해보자. 😊

(필자가 day 카운트를 헷갈려서 day 25 문제를 뛰어넘고 포스팅을 진행했다.

그래서 오늘은 day 25 포스팅을 진행해보려고 한다.

day 26 포스팅은 이미 진행했으므로 내일은 day 27을 포스팅한다.)

 

오늘은 Running TIme & Complexity(시간 복잡도)에 대해 학습했다.

 

바로 소스코드를 살펴보자. 👇👇

 

import java.util.HashMap;

public class Complexity {
    public static int  findNumsOfRepetitions(String s, char c) {
        // Linear time; O(n) time
        int sum = 0;
        for(int i=0; i<s.length(); i++) {
            if(s.charAt(i) == c) {
                sum++;
            }
        }
        return sum;
    }

    public static int[] findNumsOfRepetitionsv1(String s, char[] c) {
        // Quad time: O(n * m) time
        int[] sums = new int[c.length];
        for(int i=0; i<s.length(); i++) {
            for(int j=0; j<c.length; j++) {
                if(s.charAt(i) == c[j]) {
                    sums[j] = sums[j] + 1;
                }
           }
        }
        return sums;
    }

    public static int[] findNumsOfRepetitionsv2(String s, char[] c) {
        // Optimal time: O(n + m)
        int[] sums = new int[c.length];
        HashMap<Character, Integer> map = new HashMap<>();
        for(int i=0; i<s.length(); i++) {
            if(!map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), 1);
            }else {
                int sum = map.get(s.charAt(i));
                map.put(s.charAt(i), sum+1);
            }
        }

        for(int j=0; j<c.length; j++) {
            int sum;
            if(!map.containsKey(c[j])) {
                sums[j] = 0;
            }else {
                sums[j] = map.get(c[j]);
            }
        }
        return sums;
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        System.out.println(findNumsOfRepetitions("abca", 'a'));
        long endTime = System.currentTimeMillis();
        long duration = endTime - startTime;
        System.out.println("Test " + duration + "ms");

        char[] a = {'a', 'b'};

        startTime = System.currentTimeMillis();
        System.out.println(findNumsOfRepetitionsv1("abca", a));
        endTime = System.currentTimeMillis();
        duration = endTime - startTime;
        System.out.println("Test " + duration + "ms");

        startTime = System.currentTimeMillis();
        System.out.println(findNumsOfRepetitionsv2("abca", a));
        endTime = System.currentTimeMillis();
        duration = endTime - startTime;
        System.out.println("Test " + duration + "ms");
    }
}

Complexity.java

 

 

 

같은 문제(문자열 안의 스펠링 갯수)를 여러 방식으로 풀어보며

시간 복잡도를 계산해 여러 메서드를 만드는 내용이다.

 

이 소스 코드는 실제 추후에 백준 문제풀이를 진행할 때

참고해야겠다고 생각할 정도로 의미있었다!!

 

반복 또 반복하는 것이 가장 중요한 것 같았다.

 

 

---

 

 

그럼 우리는 다음 포스팅에서

소스 코드 리뷰로 다시 만나자. 😊