[알고리즘 뽀개기] the-leetcode-beginners-guide #1

 

비기너 가이드

 

#1 running-sum-of-1d-array

http://leetcode.com/problems/running-sum-of-1d-array

 

시간복잡도는 O(n)이고, 공간복잡도를 O(n) 혹은 O(1)로 할 수 있다.

class Solution {
    public int[] runningSum(int[] nums) {

     /** 
        // 1. runningSum 배열을 만들고, 누적값을 위한 변수 하나를 선언한다.
        int[] runningSums = new int[nums.length];
        int sum = 0;

        // 2. nums를 하나씩 순회하며
        // 3. 누적값+i를 더하여 runningSum에 넣는다. 
        for (int i=0; i<nums.length; i++) {
            runningSums[i] = nums[i] + sum;
            sum += nums[i];
        }
        return runningSums;
*/   
        // 공간복잡도를 O(1)로 하는 솔루션으로 풀어보자
        for (int i=1; i<nums.length; i++) {
            nums[i] = nums[i-1] + nums[i];
        }
        return nums;
    }
}

 

#2 richest-customer-wealth

https://leetcode.com/problems/richest-customer-wealth/

class Solution {
    public int maximumWealth(int[][] accounts) {   
        // 1. max를 선언하고
        int max = 0; 
        
        // 2. 2차원 배열을 순회하면서
        for (int i=0; i<accounts.length; i++) {
            int sum = 0;
            for (int j=0; j<accounts[i].length; j++) {
                sum += accounts[i][j];
            }
            
            // 3. max를 갱신한다. 
            max = Math.max(max, sum);
            sum = 0; 
        }

        return max;
    }
}

// 시간복잡도 O(n*m)
// 공간복잡도 : 어떤 자료구조도 생성하지 않았기 때문에 O(1)

 

#3 fizz-buzz https://leetcode.com/problems/fizz-buzz/

 

class Solution {
    public List<String> fizzBuzz(int n) {

        // 1. n만큼의 문자열 배열을 만든다.

        // 2. 1부터 n까지 순회하면서

        // 3. 15로 나뉘어지면 fizzbuz, 3으로 나누어지면 fizz, 5로 나누어지면 buzz를 삽입한다.
        List<String> result = new ArrayList();
        for (int i=1; i<=n; i++) {
            if (i%15 == 0) {
                result.add("FizzBuzz"); continue;
            }
            if (i%3 == 0) {
                result.add("Fizz"); continue;
            }
            if (i%5 == 0) {
                result.add("Buzz"); continue;
            }

            result.add(Integer.toString(i));
        }

        return result;
    }
}

 

#4 number-of-steps-to-reduce-a-number-to-zero https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/