Problem

옷의 종류와 이름이 주어지면 스파이들이 입을 수 있는 옷의 조합의 수를 구하는 문제입니다.

 

스파이들은 하루에 같은 종류의 옷은 하나밖에 입을 수 없고 다른 종류는 최소 한개만 입으면 됩니다.

 

 

Solution

모든 조합을 구하는 문제입니다.

 

리스트를 구하는 문제가 아니라 총 조합의 수를 구하는 문제이기 때문에 비교적 쉽게 구할 수 있습니다.

 

옷의 종류는 하루에 하나씩이기 때문에 입는 경우, 입지 않는 경우 이렇게 두개로 분류하면 됩니다.

 

문제에 나와있는 예제를 보면 얼굴 종류에는 동그란 안경, 검정 선글라스 이렇게 있습니다.

 

그럼 총 세개의 경우가 나옵니다.

 

  1. 아무것도 선택하지 않음
  2. 동그란 안경 선택
  3. 검정 선글라스 선택

 

그리고 상의는

 

  1. 아무것도 선택하지 않음
  2. 파란색 티셔츠 선택

 

그리고 하의는

 

. . .

 

이런 식으로 모든 종류에 대해서 모든 경우를 구하면 됩니다.

 

스파이는 반드시 하나의 종류는 걸쳐야 하므로 전부 아무것도 선택하지 않는 경우만 빼주면 됩니다.

 

식은 (각 종류 + 1) 의 곱 - 1 이 됩니다.

 

 

Java Code

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        HashMap<String, Integer> map = new HashMap<>();
        
        for (String[] cloth : clothes) {
            map.put(cloth[1], map.getOrDefault(cloth[1], 0) + 1);
        }
        
        int result = 1;
        for (String key : map.keySet()) {
            result *= map.get(key) + 1;
        }
        
        return result - 1;
    }
}

 

저작자표시 비영리

'알고리즘 문제 > Programmers' 카테고리의 다른 글

[프로그래머스] 2019 카카오 겨울인턴. 크레인 인형뽑기 게임 (Java)  (0) 2020.05.12
[프로그래머스] 체육복 (Java)  (1) 2020.03.27
[프로그래머스] 전화번호 목록 (Java)  (0) 2019.11.26
[프로그래머스] 완주하지 못한 선수 (Java)  (0) 2019.11.26
2018 KAKAO BLIND 캐시 (Java)  (0) 2019.09.06

Problem

전화번호 리스트가 주어지면 한 번호가 다른 번호의 접두어가 되는 경우가 있는지 확인하는 문제입니다.

 

예를 들어 ["119", "119231"] 이 있으면 "119" 는 "119231" 의 접두어가 되기 때문에 false 가 됩니다.

 

카테고리는 해시로 분류되어있는데 해시를 써도 되고 안써도 됩니다.

 

 

Solution 1

첫번째 풀이는 HashSet 을 사용했습니다.

 

일치하는 문제를 찾는게 아니기때문에 HashSet.contains() 을 사용하지는 못하고 Set 을 순회하며 startsWith 으로 비교하였습니다.

 

 

Java Code 1

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        HashSet<String> set = new HashSet<>();

        for (String phone : phone_book) {
            for (String s : set) {
                if (phone.startsWith(s) || s.startsWith(phone))
                    return false;
            }

            set.add(phone);
        }

        return true;
    }
}

 

 

Solution 2

두번재 풀이는 String 정렬의 특징을 이용하였습니다.

 

String 은 정렬하면 사전순으로 정렬되기 때문에 ["1", "2", "11"] 을 정렬하면 ["1", "11", "2"] 가 됩니다.

 

따라서 무조건 앞의 변수만 비교하면 되기 때문에 for 문 한번으로 끝낼 수 있습니다.

 

하지만 정렬하는 비용이 들기 때문에 효율성 테스트에서는 Solution 1 보다 비효율적이었습니다.

 

 

Java Code 2

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        
        String beforePhone = "dummy";
        for (String phone : phone_book) {
            if (phone.startsWith(beforePhone))
                return false;
            
            beforePhone = phone;
        }
        
        return true;
    }
}

 

저작자표시 비영리

'알고리즘 문제 > Programmers' 카테고리의 다른 글

[프로그래머스] 체육복 (Java)  (1) 2020.03.27
[프로그래머스] 위장 (Java)  (0) 2019.11.26
[프로그래머스] 완주하지 못한 선수 (Java)  (0) 2019.11.26
2018 KAKAO BLIND 캐시 (Java)  (0) 2019.09.06
2018 KAKAO BLIND 비밀지도 (Java)  (0) 2019.09.06

Problem

마라톤에 참여한 선수들의 명단과 완주한 선수들의 명단이 주어졌을 때

 

완주하지 못한 선수의 이름을 구하는 문제입니다.

 

단, 동명이인이 존재할 수 있습니다.

 

 

Solution

HashMap 을 사용하면 됩니다.

 

{ "이름": "인원수" } 의 key-value 형식을 갖게 선언해서 완주한 사람들을 전부 넣습니다.

 

그리고 participant 를 순회하면서 key 값이 존재하면 인원수를 하나씩 빼줍니다.

 

만약 인원수가 음수가 된다면 그 사람이 완주하지 못한 선수입니다.

 

 

Java Code

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<>();
        
        for (String person : completion) {
            map.put(person, map.getOrDefault(person, 0) + 1);
        }
        
        for (String person : participant) {
            map.put(person, map.getOrDefault(person, 0) - 1);
            
            if (map.get(person) < 0)
                return person;
        }
        
        return "";
    }
}

 

저작자표시 비영리

'알고리즘 문제 > Programmers' 카테고리의 다른 글

[프로그래머스] 체육복 (Java)  (1) 2020.03.27
[프로그래머스] 위장 (Java)  (0) 2019.11.26
[프로그래머스] 전화번호 목록 (Java)  (0) 2019.11.26
2018 KAKAO BLIND 캐시 (Java)  (0) 2019.09.06
2018 KAKAO BLIND 비밀지도 (Java)  (0) 2019.09.06

Problem


Medium 문제입니다. (체감 난이도는 Easy)


두 리스트를 받아서 더하기만 하면 되는 문제입니다.



Solution 1

각 노드에는 음수가 아닌 한 자리의 정수가 있으며 각 자리의 숫자가 거꾸로 되어 있습니다.


따라서 l1, l2 를 순서대로 비교하면서 더해주고 10 이상인 경우 carry 를 다음 노드로 넘기면 됩니다.


l1, l2 의 길이가 다를 수 있기 때문에 null 체크만 잘 해주면 쉽게 풀 수 있는 문제입니다.



Java Code 1

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0);
        ListNode result = node;
        int carry = 0;
        
        while (l1 != null || l2 != null) {
            int sum = carry;
            
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            
            if (sum >= 10) {
                node.next = new ListNode(sum - 10);
                carry = 1;
            } else {
                node.next = new ListNode(sum);
                carry = 0;
            }
            
            node = node.next;
        }
        
        if (carry == 1) {
            node.next = new ListNode(1);
        }
        
        return result.next;
    }
}



Solution 2

Discuss 를 보니 굳이 carry 를 쓰지 않고 sum 변수 하나만을 사용하며 % / 연산으로 풀이할 수도 있었습니다.


% 연산 비용이 부담되지 않는다면 훨씬 깔끔한 것 같습니다.



Java Code 2

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0);
        ListNode result = node;
        int sum = 0;
        
        while (l1 != null || l2 != null || sum > 0) {
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            
            node.next = new ListNode(sum % 10);
            sum /= 10;
            
            node = node.next;
        }
        
        return result.next;
    }
}


저작자표시 비영리

'알고리즘 문제 > LeetCode' 카테고리의 다른 글

[LeetCode Easy] Single Number (Java, Kotlin)  (0) 2019.12.11
[LeetCode Easy] Maximum Depth Of Binary Tree (Java, Kotlin)  (0) 2019.12.02
[LeetCode Medium] Path Sum III (Java)  (1) 2019.11.24
[LeetCode Medium] Combination Sum (Java)  (0) 2019.11.24
[LeetCode Medium] 3Sum (Java)  (0) 2019.11.23

Problem


Easy 문제입니다. (체감 난이도는 Medium 입니다)


이진 트리가 주어지고, root 부터 아래로 내려가면서 연속된 노드들의 합이 sum 이 되는 경우의 수를 구하는 문제입니다.



Solution 1

반드시 연속되야만 하기 때문에 연속되지 않은 값은 갖고 있을 필요가 없습니다.


예를 들면 root 가 10 이고 left 자식인 5 를 탐색해야 합니다.


5는 현재 자신의 값과 root 와의 합인 [5, 15] 와 sum 을 비교해야 합니다.


이걸 List 를 넘기는 대신에 10 을 더하는 경우, 더하지 않는 경우 두가지로 나누어서 호출하면 됩니다.



Java Code 1

class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        
        return pathSequenceSum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    public int pathSequenceSum(TreeNode node, int sum) {
        if (node == null) return 0;
        
        int count = (sum == node.val) ? 1 : 0;
        count += pathSequenceSum(node.left, sum - node.val) + pathSequenceSum(node.right, sum - node.val);
        
        return count;   
    }
}



Solution 2

Discuss 에서는 HashMap 을 사용하여 O(n) 에 푸는 풀이가 있었습니다.


처음에는 이해를 잘 못했지만 차근차근 로그를 찍어가면서 확인해보니 어느정도 알 것 같았습니다.


HashMap 에다가 지금까지 지나온 노드들의 누적 합을 저장해두고 있는지 확인하면 됩니다.


예제를 보고 설명해보겠습니다. 위 Example 중에서 [10, 5, 3, 3] 만 본다고 생각합시다.


가장 끝의 자식노드인 3 에서 확인해야될 값은 [현재 노드의 값, 부모 노드부터 누적합, 조부모 노드부터 누적합... root 노드부터 현재까지 누적합]


이렇게 트리의 높이에 비례하여 비교해야될 값이 늘어나서 첫 풀이에는 List 를 넘겼었습니다.


이번에는 루트노드부터의 누적합을 HashMap 에 저장해두면 됩니다.


HashMap 은 { "누적합" : "갯수" } 형식으로 예제를 기준으로 {10 : 1, 15: 1, 18: 1, 21: 1} 이렇게 [10, 15, 18, 21] 이 한개씩 들어가있습니다.


그리고 누적합에서 target 넘버를 뺀 값이 map 에 존재한다면 현재 노드부터 루트 노드까지 연속된 노드들의 합 중에 일치하는 값이 있다는 뜻입니다.


마지막 노드인 3 에서 가능한 sum 의 경우는 [21, 11, 6, 3] 입니다.


현재 노드까지의 누적합 21 에서 [21, 11, 6, 3] 을 빼면 [0, 10, 15, 18] 입니다.


HashMap 에 들어있는 값과 똑같지 않나요?


마지막 노드까지 나올 수 있는 연속합들을 한번에 비교할 수 있습니다.


근데 map 에 0은 없는데 어디서 넣을까요?


root 부터 현재 노드까지 더한 경우가 sum 이 될 수도 있기 때문에 처음에 {0: 1} 을 넣고 시작합니다.


그림 없이 설명하려니 좀 힘들 수가 있는데 코드를 보면 더 이해하기 쉬울 수도 있습니다.



Java Code 2

class Solution {
    public int pathSum(TreeNode root, int sum) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return recursive(root, 0, sum, map);
    }
    
    public int recursive(TreeNode node, int accumulateSum, int sum, HashMap<Integer, Integer> map) {
        if (node == null) return 0;
        
        accumulateSum += node.val;
        int count = map.getOrDefault(accumulateSum - sum, 0);
        
        map.put(accumulateSum, map.getOrDefault(accumulateSum, 0) + 1);
        count += recursive(node.left, accumulateSum, sum, map) + recursive(node.right, accumulateSum, sum, map);
        map.put(accumulateSum, map.get(accumulateSum) - 1);
        
        return count;
    }
}


저작자표시 비영리

'알고리즘 문제 > LeetCode' 카테고리의 다른 글

[LeetCode Easy] Single Number (Java, Kotlin)  (0) 2019.12.11
[LeetCode Easy] Maximum Depth Of Binary Tree (Java, Kotlin)  (0) 2019.12.02
[LeetCode Medium] Add Two Numbers (Java)  (0) 2019.11.24
[LeetCode Medium] Combination Sum (Java)  (0) 2019.11.24
[LeetCode Medium] 3Sum (Java)  (0) 2019.11.23

Problem


Medium 문제입니다.


candidates 에 있는 원소들 중 합이 target 이 되는 리스트 묶음을 return 하면 됩니다.



Solution

원소들은 중복해서 사용될 수 있지만 결과에는 중복되는 list 가 없어야 합니다.


처음에는 DP 로 생각했으나 우리가 구해야되는건 List 들의 목록입니다.


각 단계별로 저장되는 값은 List 이고 결국 메모이제이션을 통해서 다음 값을 구하려고 해도 저장된 List 만큼 전부 순회해야 합니다.


결국 백트래킹과 큰 차이가 없기 때문에 정해는 백트래킹이라고 생각합니다.


현재 candidate 값이 target 보다 작으면 temp 리스트에 넣은 뒤 다음 target 을 target - candidate 하여 계속 호출해줍니다.


만약 target 값이 0 이 된다면 temp 에 있는 값들의 합이 target 이라는 뜻이므로 result 리스트에 넣어주면서 쭉 돌면 됩니다.


candidates[0] 부터 시작하며 candidates[1] 부터 시작할 때는 이전값인 candidates[0] 값을 볼 필요가 없으므로 백트래킹 함수에 index 를 같이 넘깁니다.



Java Code

class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        for (int i = 0, len = candidates.length; i < len; i++) {
            List<Integer> temp = new ArrayList<Integer>();
            temp.add(candidates[i]);
            backtracking(candidates, i, 1, target - candidates[i], temp);
        }
        
        return result;
    }
    
    public void backtracking(int[] candidates, int index, int tempSize, int target, List<Integer> temp) {
        if (target == 0) {
            result.add(new ArrayList(temp));
            return;
        }
        
        for (int i = index, len = candidates.length; i < len; i++) {
            if (candidates[i] <= target) {
                temp.add(candidates[i]);
                backtracking(candidates, i, tempSize + 1, target - candidates[i], temp);
                temp.remove(tempSize);
            }
        }
    }
}


저작자표시 비영리

'알고리즘 문제 > LeetCode' 카테고리의 다른 글

[LeetCode Easy] Single Number (Java, Kotlin)  (0) 2019.12.11
[LeetCode Easy] Maximum Depth Of Binary Tree (Java, Kotlin)  (0) 2019.12.02
[LeetCode Medium] Add Two Numbers (Java)  (0) 2019.11.24
[LeetCode Medium] Path Sum III (Java)  (1) 2019.11.24
[LeetCode Medium] 3Sum (Java)  (0) 2019.11.23

Problem


Medium 난이도의 문제입니다.


nums 배열에서 합이 0이 되는 세개의 원소 리스트들을 return 하면 됩니다.



Solution

백준에 있는 세 용액과 비슷한 문제이지만 해당되는 리스트를 전부 return 해야된다는 점과


배열에는 중복된 원소가 존재하지만 실제 return 하는 값에는 중복된 리스트를 전부 빼야 한다는 점이 다르다고 할 수 있습니다.


세 용액을 풀었던 것과 마찬가지로 모든 원소들에 대하여 두 용액 풀이로 리스트를 구했습니다.


두 용액 풀이 (a + b = c 가 되는 a, b 구하기)

  1. 배열을 오름차순으로 정렬합니다.
  2. 배열의 양 끝에 있는 숫자의 합과 c 를 비교합니다.
  3. 합이 c 보다 작다면 왼쪽 index 를 1 증가 시킵니다. (c 보다 작기 때문에 작은 값을 증가시킴)
  4. 합이 c 보다 크다면 오른쪽 index 를 1 감소 시킵니다. (c 보다 크기 때문에 큰 값을 감소시킴)
  5. 순차적으로 두 숫자의 사이를 좁히면서 만나기 전까지 합이 c 가 되는 모든 경우를 구합니다.


위 풀이를 응용하면 a + b + c = d 또한 구할 수 있습니다.


c 값을 미리 정해두고 a, b 값을 구하면 됩니다.


배열 원소 중 하나를 미리 c 값으로 정해두고 a, b 값을 구하는 방식으로 모든 a, b, c 경우의 수를 구할 수 있습니다.


두 용액은 O(n) 이지만 세 용액은 모든 n 에 대하여 두 용액을 한번씩 적용해야되므로 O(n^2) 의 시간 복잡도를 가집니다.


그리고 이 문제는 시간을 줄일 수 있는 요소가 존재합니다.


먼저 숫자에 해당하는 값이 나오면 left 또는 right 중 하나만 바꿀 필요 없이 둘다 바꿔도 됩니다.


a + b = 0 인데 a 나 b 만 바꾸면 0 이 무조건 되지 않기 때문입니다.


두번째로 nums 배열에는 중복값이 존재합니다.


left++ 혹은 right-- 할때 이전값과 비교해서 중복되는 값이 나오지 않을 때까지 계속 패스할 수 있습니다.


[1, 1, 1, 1, 1] 이런 배열이 들어왔을 때 기존 코드는 일일히 비교해야하지만 중복되는 값을 패스하게 하면 처음만 비교하고 나머지는 전부 넘길 수 있습니다.



Java Code

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int sum = nums[left] + nums[right] + nums[i];
                
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while (nums[left] == nums[left - 1] && left < right) left++;
                    while (nums[right] == nums[right + 1] && left < right) right--;
                } else if (sum > 0) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        
        return res;
    }
}


저작자표시 비영리

'알고리즘 문제 > LeetCode' 카테고리의 다른 글

[LeetCode Easy] Single Number (Java, Kotlin)  (0) 2019.12.11
[LeetCode Easy] Maximum Depth Of Binary Tree (Java, Kotlin)  (0) 2019.12.02
[LeetCode Medium] Add Two Numbers (Java)  (0) 2019.11.24
[LeetCode Medium] Path Sum III (Java)  (1) 2019.11.24
[LeetCode Medium] Combination Sum (Java)  (0) 2019.11.24

Problem


연속적인 합 중에서 가장 큰 수를 구하는 문제입니다.




Solution

한 가지만 기억하면 됩니다.


이전까지의 합이 음수면 새로 더하는 값은 무조건 현재보다 작다


예를 들어 [A, B, C, D] 가 입력으로 들어옵니다.


A + B + C 가 음수라면 A + B + C + D 는 무조건 D 보다 작겠죠?


어차피 구해야 하는건 최댓값이기 때문에 이전까지의 합은 음수라면 버리고 D 부터 다시 합을 구해나가면 됩니다.




Java Code

import java.util.*;
import java.io.*;

class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int[] numbers = new int[n];

        st = new StringTokenizer(br.readLine());

        for (int i=0; i<n; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        int max = numbers[0];
        int sum = 0;
        for (int i=0; i<n; i++) {
            sum += numbers[i];
            max = Math.max(max, sum);
            if (sum < 0) sum = 0;
        }

        System.out.print(max);
    }
}


저작자표시 비영리

'알고리즘 문제 > 백준' 카테고리의 다른 글

백준 2293 동전 1 (Java)  (0) 2020.03.28
백준 2437번. 저울 (Java)  (2) 2020.03.17
백준 5397번. 키로거 (Java)  (0) 2019.09.24
백준 2178번. 미로 탐색 (Java)  (0) 2019.09.22
백준 16940번. BFS 스페셜 저지 (Java, Kotlin)  (0) 2019.09.14

+ Recent posts

티스토리툴바