문제설명

🤔 고민사항

• 백트래킹을 정복하기 위해 백준에서 백트래킹 문제집을 조지고 있다.
• 얼핏 어렵지 않게 느껴졌고, [백준 1182번] 부분수열의 합 (실버2, Java) 와 유사하게 느껴졌다. 트리를 그려서 dfs를 구현해야겠다.
• 예제의 N=4, M=2 일 경우의 트리 탐색이다.
• 제약 조건의 '오름차순 수열이어야 한다'는 깊이 탐색을 왼쪽에서부터 하면 자연스레 해결이 된다.
• 제약 조건의 '중복되는 수열을 여러 번 출력하면 안된다'는 현재 노드의 값보다 큰 값만 탐색하도록 하면 된다. 의외로 문제에서 제약조건으로 주어지는 사항들 중 꽤 많은 경우는 출제의도에 맞게 풀어내면 알아서 해결이 되는 경우다.
• dfs의 _각 depth(node)에서 _ 지금껏 탐색해온 node를 담을 배열을 갖도록 할 것이다 즉 dfs 메서드 콜마다 스택메모리에 각자의 배열을 갖도록. (비슷한 상황에서 이거 전역변수로 설정했다가 1시간 삽질한 경험이 있다.)
• 여기까지 문제를 풀고 코딩을 해본 결과다.

  import java.util.Scanner;
  

public class N과M_2 {

static int N, M;
static int[] ARR;

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    M = sc.nextInt();
    ARR = new int[N + 1];
    for (int i = 1; i < N + 1; i++)
        ARR[i] = i;

    dfs(1, 0, new int[M]);

}

public static void dfs(int num, int depth, int[] arr) {
    if (num > N)
        return;

    if (depth == M) {
        for (int i : arr)
            System.out.print(i + " ");
        System.out.println();
        return;
    }

    arr[depth] = num;

    for (int i = num; i < N + 1; i++)
        dfs(i + 1, depth + 1, arr);
}

}

- 부끄럽지만 실패한 과정을 올려놓는다. 코테 공부를 좀 쉬긴 했나보다. dfs 코드 짜는 감을 제대로 잃어버렸다.
현타가 씨게 왔다. 대충 큰 흐름은 맞긴한데, 
- main에서 각 **node에 대해 dfs 탐색을 시켜놓고선 dfs 과정중에 다시 for문을** 돌리고 있다. 중복된 값이 안나올 수가 없다.
- if(num < N) return; 부분은 boilerplate code다. 어차피 dfs의 for문에서 저 범위 안으로 값을 준다.
- arr[depth] = num 을 하게되면 tree 탐색이 똑바로 되겠나.. for문 안의 i로 초기화해주어야한다.
- 사실 코드짜다 막혀서 **ChatGPT**에게 도움을 구했었고, 그러고 나서야 이런 부족함을 볼 수 있었다.
![](https://velog.velcdn.com/images/dev_hsyang/post/d5b0cf8a-fe06-484d-b2e9-3f1b32a983fd/image.png)진짜 무시무시한 녀석이다..
- 아직 Recursive한 사고, 코딩 능력이 미숙하면 이러한 과정을 겪게 된다. 
잘못 작성했던 코드를 기록하고 꺼내보면서 깨달아가는 이 순간과 과정이 남았으면 좋겠다.

# 👨‍💻 CODE

import java.util.Scanner;

public class N과M_2 {

static int N, M;

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

    dfs(1, 0, new int[M]);

}

public static void dfs(int num, int depth, int[] arr){
    if(depth == M){
        for(int i : arr)
            System.out.print(i + " ");
        System.out.println();
        return;
    }

    for(int i=num; i<N+1; i++){
        arr[depth] = i;
        dfs(i + 1, depth + 1, arr);
    }
}

}

> 문제를 복기하다가 헷갈리는 지점을 찾았다.
어떻게 dfs(1, 0, new arr[])로 모든 노드를 다 탐색했지? 하는 의구심. 역시 dfs는 진짜진짜 헷갈린다.
직접 그려보면서 이해를 해봤다. 필기가 너무 더러워서 올려놓진 않겠지만, 

    for(int i=num; i<N+1; i++){
        arr[depth] = i;
        dfs(i + 1, depth + 1, arr);
    }

에서 잘보면 arr[depth] = i 다. 그러니까 depth가 0으로 시작하기 때문에, 탐색을 시작하는 노드가 i에 따라 바뀌는 것이다. 배열의 첫번째 값이 dfs내의 for문에 의해 계속 상승하는 것.
<_arr[depth] = num 을 하게되면 tree 탐색이 똑바로 되겠나.. for문 안의 i로 초기화해주어야한다._> 라고 저 위에 헛똑똑이씨는 이해한줄 알고 넘어가셨다.


# 🛠 리뷰
코딩테스트를 공부하면서 dfs를 자신있게 코딩했던 적은 생각해보니 graph 탐색이었다. 왜 그 visited배열 찍어가면서 노드 탐색하는 과정..
그리고 dfs를 코딩할때 어려움을 느꼈던 분야는 이 문제와 같이 **재귀적으로 알고리즘을 직접 짜야하는 경우**, 특히 백트래킹 문제였던 것 같다. 머슬 메모리에 의해 그냥 타이핑하는 dfs가 아니라 직접 설계하는... 생각해보니 삼성그룹 코테 기출문제에서도 dfs에서 애먹었던 문제는 이런쪽이었다.
좋아 넌 내가 정복한다

문제설명

🤔 고민사항

• 괄호문제는 전형적인 스택 문제다. 오랜만이긴 했지만 어렵지 않게 풀어 나갔다.
• 다음과 같이 풀이과정을 도출했다. 배열을 순차적으로 순회하며

1. ")"이 들어올땐 스택에 "("이 있는 경우에만 가능하다. => 즉, 스택이 비어있으면 return false
2. ")"이 들어왔을 때 스택에 "("이 있다면 스택에서 "("를 하나 pop한다.
3. "("이 들어올때는 제약사항이 딱히 없으니 바로 스택에 push한다.
4. 순회가 끝났을때 스택에 "("이 남아있으면 괄호가 올바르지 않은 것이다.

• 처음에는 "(" 스택, ")" 스택 2개의 스택을 두고 풀어야 하는줄 알았는데 생각해보니 "(" 스택만 있으면 된다. 필요에 따라 push, pop, isEmpty() 연산을 하면 되는 것.
• 스택에 꼭 "("을 push할 필요는 없다. 나같은 경우 "("이 들어오면 int 1을 push해서 카운팅 했다.

  import java.util.*;
  

class Solution {

boolean solution(String s) {
    String[] input = s.split("");
    Stack<Integer> stack = new Stack<Integer>();

    for(int i=0; i<input.length; i++){
        String now = input[i];
        if(now.equals("(")){
            stack.push(1);
        }else if(now.equals(")")){
            if(stack.isEmpty())
                return false;
            stack.pop();
        }
    }

    if(stack.isEmpty())
        return true;
    else
        return false;
}

}

- 3분만에 자신있게 완성했다. 그런데
![](https://velog.velcdn.com/images/dev_hsyang/post/e9e54b12-18df-4f36-8e7a-c887422aeef3/image.png) 이게 뭐지?
- 제약사항에 문자열 s의 길이는 100,000이하의 자연수로 worst case가 크기는 한데, 
**Stack의 push, pop, isEmpty는 O(1)**이고, 전체 O(N)으로 해결한게 아닌가? 싶었다.
- 문제는 Stack연산에 없었고, **문자열의 split()**에 있었다. 확인해보니 **split()연산이 시간 복잡도가 O(N * M)**, 그러니까 이 문제 같은 경우 최대 O(N^2)이 나오는 것이다.
- 그러면 s를 어떻게 처리하지? 고민하다가 substring()연산으로 바꾸어 보았다. **substring()은 O(N)**의 시간복잡도로, for문 안에서 사용하면 어차피 O(N^2)이겠지만 그래도 한번 시도해 봤다.

import java.util.*;

class Solution {

boolean solution(String s) {
    Stack<Integer> stack = new Stack<Integer>();

    for(int i=0; i<s.length(); i++){
        String brc = s.substring(i, i+1);
        if(brc.equals("(")){
            stack.push(1);
        }else if(brc.equals(")")){
            if(stack.isEmpty())
                return false;
            stack.pop();
        }
    }

    if(stack.isEmpty())
        return true;
    else
        return false;
}

}

![](https://velog.velcdn.com/images/dev_hsyang/post/2cbfbda0-8303-4f53-9311-05142d70bc9c/image.png)~~쫌 되라~~
- 코딩테스트에서 제일 골치아픈 상황을 마주해버렸다.. 이문제는 사실 스택을 활용한 문제가 아니라 문자열 처리를 시간복잡도를 최소화하여 구현하는 문제였던 것이다.
- **아니, 그냥 내가 바보였던 것이다.** String 클래스의 **charAt()**메서드를 사용하면 배열마냥 문자열의 특정 인덱스 값을 char형으로 가져올 수 있단다. 이런 세상에 자바 개발이 몇년짼데 이걸 몰랐다니..

# 👨‍💻 CODE

import java.util.*;

class Solution {

boolean solution(String s) {
    Stack<Integer> stack = new Stack<Integer>();

    for(int i=0; i<s.length(); i++){
        char brc = s.charAt(i);
        if(brc == '('){
            stack.push(1);
        }else if(brc == ')'){
            if(stack.isEmpty())
                return false;
            stack.pop();
        }
    }

    if(stack.isEmpty())
        return true;
    else
        return false;
}

} ```

문제설명

🤔 고민사항

• 몇차례 코딩테스트 경험을 통해 특히 '백트래킹' 유형에 약하다는 것을 알았다. 백준에서 백트래킹 문제집을 전부 풀어보자고 마음먹고 시작했는데 실버2 문제에서 걸려버렸다.
• 처음에 '부분수열', '다 더한값이 S가 되는'을 보고 구간합을 적용하면 되겠구나 하고 삽질했다. _(논리적으로 좀 생각해라)~~_
• 풀이과정을 생각해내 봤다.

1. 입력받은 Array를 오름차순으로 sort한다.
2. 첫번째 인덱스 값부터 순차적으로 합해간다. 이때 S와 같아지면 ANS++하고 다음 인덱스로 넘어가고, S보다 값이 커지면 바로 다음 인덱스로 넘어간다.

• 이때까지만 해도 이정도면 풀어질줄 알았다. 또 2중 for문으로 구현할 수 있겠다 싶어 recursive하지 않게 구현해봤다.

public class 부분수열의합 {

    static int N, S, ANS;
    static int[] ARR;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt();
        ARR = new int[N];

        for(int i=0; i<N; i++)
            ARR[i] = sc.nextInt();

        Arrays.sort(ARR);

        for(int i=0; i<N; i++){
            int n = ARR[i];
            for(int j=i+1; j<N; j++){
                n += ARR[j];
                if(n == S){
                    ANS++;
                    break;
                }
                if(n > S)
                    break;
            }
        }

        System.out.println(ANS);
    }
}

• ㅋㅋ 될리가 있나 12%에서 틀린다. 생각해보니 배열을 순차적으로 탐색하면 크기가 양수인 부분수열 조합을 전부 찾지 못한다.
• 다른 블로그를 참고해서 아이디어를 얻었다.

  [백준-1182]부분수열의 합 (Java) :: 기억 안 나면 다시 보면 되지

• 전체 집합에서 부분집합, 즉 부분수열을 구하는 테크닉이 있었다. 생각해보니 알고리즘 전공때 해봤던 기억이 있다. 역시 전공자는 '어디서 봤던건데' 하는사람이다
• 블로그에서 친절히 수필로 부분수열을 구하는 트리까지 그려줬다. 부분수열을 찾고 합이 S인 경우 answer++ 하기만 하면 된다.

• 직접 TREE 를 그려봤다. TREE의 각 depth는 배열의 각 원소를 나타낸다. 즉, depth 끝까지 TREE를 탐색하면 전체 수열의 부분수열을 구할 수 있다. (정확히는 부분수열의 합을 구하는 것) TREE의 link를 살펴보면, 왼쪽 가지는 원소를 포함하고, 오른쪽 가지는 원소를 포함하지 않음을 뜻한다. 쉽게 말해 왼쪽으로 탐색하는 과정과 오른쪽으로 탐색하는 과정을 재귀적으로 구현하면 된다.

문제를 복기하면서.. (2023.09.03) 검색의 힘을 받아 문제를 해결하고 며칠 후 다시 한번 풀어봤다. 역시 처음 풀 땐 안보였던 요소들을 발견할 수 있었다.

import java.util.Scanner;
public class 부분수열의합_prac {
    static int N, S, ANS;
    static int[] ARR;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt();
        ARR = new int[N];
        for(int i=0; i<N; i++)
            ARR[i] = sc.nextInt();
        dfs(0, 0);
        if(S == 0)
            ANS -= 1;
        System.out.println(ANS);
    }
    public static void dfs(int depth, int sum){
        if(depth == N){
            if(sum == S)
                ANS++;
            return;
        }
        dfs(depth + 1, sum + ARR[depth]);
        dfs(depth + 1, sum);
    }
}

직접 다시한번 트리를 그려보며 dfs를 구현해봤다.

• 백트래킹, DFS 문제를 풀 때에는, 일단 그림을 그려봐야한다. 일단 그리고 볼 것.
• 다시 생각을 해보니 이 문제는 말만 바꾸면 전체 집합에서 가능한 모든 경우의 조합을 찾는 문제이기도 하다. 비교적 최근 어딘가의 코딩테스트에서 '가능한 조합의 갯수를 찾는 문제'를 해결하지 못했던 기억이 난다. 그래도 몇 문제는 풀어봤기에, 이게 dfs를 활용한 백트래킹으로 해결하는 문제라는 것을 눈치채기 까지는 했는데, 정작 구현을 못했었다.
• dfs() 코드를 자세히 따라가다 보면 전체 수열에서 나올 수 있는 모든 부분수열(즉 집합)을 탐색해낸다.

👨‍💻 CODE

mport java.util.Scanner;

/**
 * 백준 1182
 * 실버 2
 *
 */
public class 부분수열의합 {

    static int N, S, ANS;
    static int[] ARR;

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt();
        ARR = new int[N];
        for(int i=0; i<N; i++)
            ARR[i] = sc.nextInt();

        dfs(0, -1);

        if (S == 0)
            ANS -= 1;

        System.out.println(ANS);
    }

    public static void dfs(int val, int depth){

        /**
         * 부분 수열을 전부 구하고, 부분수열의 합과 S 를 비교할려고 한다.
         * depth + 1 == N 이면 tree 에서 부분수열을 전부 구한 단계이고, 부분수열의 합인 val 이 S 와 같으면 ANS++
         * depth 를 -1에서 시작하여 depth + 1 을 N 과 비교하는 이유는, ARR[depth + 1] 할때 INDEX OUT OF BOUND 에러를 방지하기 위함이다.
         */
        if(depth + 1 == N){ // 부분수열을 전부 구하기 때문에, depth 가 N 이 되면 부분수열의 합을 S 와 대조해본다.
            if(val == S)
                ANS++;
            return;
        }

        dfs(val + ARR[depth + 1], depth + 1); // TREE 에서 왼쪽 경로로 탐색하는 경우
        dfs(val, depth + 1); // TREE 에서 오른쪽 경로로 탐색하는 경우
    }
}

🛠 리뷰

recursion 그러니까 dfs를 구현해서 문제를 여럿 풀어봤다고 생각했는데, 여전히 dfs를 구현하는 과정이 어려운것 같다. 초기값이 뭔지, 어느 depth에서 return할 것인지, 어떤 값을 return할 것인지 고민하는게 중요하고 경우에 따라 특정 depth에서 계산을 통해 바뀐 state를 return후 돌려놓는 작업도 필요하다. 방법이 있나, 될때까지 문제를 많이 풀어보는 수밖에

문제설명

🤔 고민사항

• 난 아직 프로그래머스 Lv.2도 어려운것 같다. 요구사항을 어떻게 구현해야할지 처음에 막막했다.
• '입출력 예 설명 #2' 중

모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

• 에서 힌트를 얻었다. 다시 말하면 이 구문이 없었다면 굉장히 헤맸을 문제였다.
• 눈치빠른 사람들은 알아챘겠지만, '각각 5일, 10일, 1일, 1일, 20일, 1일입니다.' 문장에서 Queue가 떠올랐을 것이다. 즉, 입력받은 두 배열을 통해 남은일수를 계산해서 순차적으로 Queue에 담아놓으면 쉽게 풀리는 문제이다.
• 다시! (5, 10, 1, 1, 20, 1) 큐에서 처음 뽑은 토큰보다 낮은 숫자가 나오면 다음 배포까지 보류, 높은 숫자가 나오면 바로 배포하는 식으로 계산하면 되는것이다. 사실 직관적으로 패턴을 파악해서 풀었다. 첫번째 기능은 5일 걸리고 두번째 기능은 10일이 걸리면 첫번째 기능만 우선 배포하고 두번째 날까지 기다리면 된다. 두번째 기능은 10일, 세번째와 네번째가 1일, 다섯 번째가 20일이 걸린다면 두번째, 세번째, 네번째 기능을 배포하고 다섯번째 기능까지 기다리는 것이다.
• 나 같은 경우 ArrayList를 활용해서 큐에서 더 큰 숫자(배포까지 걸리는 일수)가 나올 때까지 센 카운트(기능 갯수)를 순서대로 담았고, ArrayList를 정답배열로 복사하여 반환하였다.

👨‍💻 CODE

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] answer = {};
        Queue<Integer> queue = new LinkedList<Integer>();
        ArrayList<Integer> ans = new ArrayList<Integer>();

        for(int i=0; i<progresses.length; i++){
            int progress = progresses[i];
            int speed = speeds[i];
            int dateUntilDeploy = calculDate(progress, speed);
            queue.add(dateUntilDeploy);
        }

        int pivot = queue.poll();
        int cnt = 1;
        while(!queue.isEmpty()){
            int num = queue.poll();
            if(pivot >= num){
                cnt++;
            }
            else{
                ans.add(cnt);
                pivot = num;
                cnt = 1;
            }
        }
        ans.add(cnt);

        answer = new int[ans.size()];
        for(int i=0; i<ans.size(); i++)
            answer[i] = ans.get(i);

        return answer;
    }

    public int calculDate(int p, int s){
        return (100 - p) % s == 0 ? (100 - p) / s : (100 - p) / s + 1;
    }
}

⚒️ 리뷰

아직 코드를 작성하는 요령이 부족한 것 같다. 문제를 해결하는 논리과정을 생각하는데 집중하느라 클린코드나 코드 표현력에 신경쓸 여유가 없다. 동일한 기능을 수행하더라도 가독성이 좋고 이해가 잘 가는 코드를 작성하고 싶다.

문제설명

🤔 고민사항

• 전형적인 스택 또는 큐를 사용하면 되는 간단한 문제였다.
• 사실 프로그래머스에 익숙하지 않아, '정답 배열에 값을 어떻게 추가하지???' 라는 굉장히 초보적이고 부끄러운 고민을 잠시 했다. (백준이나 코드트리였으면 정답 배열을 반환하는게 아니라 그냥 찍어내면 됐으니까)
• 어쨌든, 파라메터로 주어진 배열에서 중복된 숫자를 제거하여 반환하면 되는 문제다. 주의해야할 요소는 '주어진 배열의 순서'를 지켜야 한다는 것. 스택이던 큐던 FIFO, FILO 속성을 잘 활용하면 쉬운 문제다.
• 나 같은 경우 스택 하나로 구현했다. 입력 배열의 원소를 순차적으로 스택에 넣을건데, (1) 스택의 peek() 메서드를 통해 가장 마지막에 추가된 토큰을 확인할 수 있고, 중복값이 들어올 때 peek()을 통해 확인하고 스택에 안 넣으면 그만이다.
• (2) 스택의 크기만큼 int배열을 초기화하고, (3) 배열의 뒷 인덱스부터 스택값을 pop하여 초기화해주면 순서를 원복시킬 수 있다.

👨‍💻 CODE

``` import java.util.*;

public class Solution { public int[] solution(int []arr) { int[] answer = {}; Stack stack = new Stack();

    // (1)
    for(int i=0; i<arr.length; i++){
        if(stack.isEmpty()){
            stack.push(arr[i]);;
        }else{
            if(stack.peek() != arr[i])
                stack.push(arr[i]);
        }
    }

    // (2)
    answer = new int[stack.size()];
    int n = stack.size();

    // (3)
    for(int i=n-1; i>=0; i--)
        answer[i] = stack.pop();

    return answer;
}

}```

문제설명

🤔 고민사항

• 솔직히 처음에 조합문제인줄 알고 쫄았다.
• 조합문제 맞다.
• 종류별로 최대 1가지 의상만 착용할 수 있고, 최소 1개 의상은 입는(이 문제에서 제일 이해 안가는 내용) 조합을 어떻게 구현해 내는지가 관건인 것 같다.
• 잘 생각해보면 의상 종류의 갯수가 중요하지, 의상의 이름은 중요하지 않다. 앞전의 [프로그래머스] 완주하지 못한 선수 (Lv.1, Java) 문제와 유사한 포인트가 있는데, 중복되는 데이터를 어떻게 해싱처리할지 이다. 여기서 중복데이터는 같은 종류의 여러 의상이다. 즉, (key값에 의상종류, value값에 해당종류 의상 수)로 표현한다.
• HashMap을 써서 데이터를 표현했으면, 조합 연산을 어떻게 해야할지 고민해야한다. 생각보다 간단하다. 모자 종류가 2개, 안경 종류가 1개일 경우를 예를 들어보면,

  모자의 경우의 수 : A모자 착용, B모자 착용, 모자 착용 X (3경우) 안경의 경우의 수 : C안경 착용, 안경 착용 X (2경우) 모자와 안경을 합한 경우의 수 = 3 * 2 = 6가지

• 그런데 '최소 1개 의상은 입습니다' 에 따라, 저 6가지 경우 중 모자착용 X & 안경착용 X 경우를 빼야 한다.
• 일반화 하면 (1번 종류 의상의 수 + 1) x (2번 종류 의상의 수 + 1) x....(n번 종류 의상의 수 + 1) - 1 이 된다.
• 그럼 이제, HashMap에 value로 저장된 각 종류별 의상수를 활용해 연산을 하면 된다.

👨‍💻 CODE

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        Map<String, Integer> hashmap = new HashMap<String, Integer>();

        for(int i=0; i<clothes.length; i++)
            hashmap.put(clothes[i][1], hashmap.getOrDefault(clothes[i][1], 0) + 1);

        for(int i : hashmap.values())
            answer *= (i + 1);

        return answer - 1;
    }
}

문제설명

🤔 고민사항

• 초반에 풀이를 어떻게 해야할지 갈피를 못 잡았다.
• 해싱을 어떻게 해야하지?* 라는 고민, 해시 특성을 어떻게 응용해야 할지 어려웠다.
• 풀이 방법을 먼저 생각하기 보다, 문제의 요구사항을 한번 직접 구현해서 풀이법을 도출해보자.
• phone_book에 각각 길이가 다른(같을수도 있는) 번호가 있는데, 길이가 짧은 번호가 자신보다 길이가 긴 번호에 포함되는지 확인하면 되는 문제다.
• 여기서 풀이법을 도출해본다. 1) 번호를 substring하여 앞에서부터 자른다. 2) 1자리부터 번호 전체 길이까지 늘려가며, 각 자른 번호가 phone_book에 존재하는지 확인하면 된다. 3) (1), (2) 과정을 phone_book의 모든 번호에 대해 반복하면 된다.
• phone_book의 각 번호에 대해 substring을 하려면 이중 for문을 사용하게 되니, substring한 번호가 phone_book에 존재하는지 탐색하는 시간을 O(1)로 맞추기 위해 HashSet을 이용했다.

👨‍💻 CODE

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Set<String> hashSet = new HashSet<String>();

        for(String s : phone_book)
            hashSet.add(s);

        for(int i=0; i<phone_book.length; i++)
            for(int j=0; j<phone_book[i].length(); j++)
                if(hashSet.contains(phone_book[i].substring(0, j)))
                    answer = false;

        return answer;
    }
}

문제설명

🤔 고민사항

• participant 리스트와 completion 리스트를 비교해서 participant에는 없는 completion 인원을 찾으면 된다 라고 풀이를 출발했다.
• 처음에는 탐색 속도가 O(1)인 속성을 고려하여, 두 리스트를 각각 HashSet에 담아 for문으로 비교해서 participant set에는 없는 completion set 인원을 찾아서 풀었는데
• 사고발생 참가자 중에는 동명이인이 있을 수 있댄다 문제를 똑바로좀 읽자
• 동명이인, 그러니까 중복되는 데이터가 있는데 Hash를 어떻게 쓰지? 라는 고민을 했다.
• HashMap을 써서 (Key에 참가자 이름, Value에 참가자 수) 이렇게 표현하면 중복되는 데이터를 처리할 수 있다.
• 중복 key값에 대해 중복갯수를 데이터화*하면, 후에 처리하기 용이할 것이다.

👨‍💻 CODE

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hashmap = new HashMap<String, Integer>();

        for(String s : participant)
            hashmap.put(s, hashmap.getOrDefault(s, 0) + 1);

        for(String s : completion)
            hashmap.put(s, hashmap.get(s) - 1);

        for(String s : hashmap.keySet())
            if(hashmap.get(s) == 1)
                answer = s;

        return answer;
    }
}

⚒️ 리뷰

Java HashMap에 다양한 메서드가 있더라. getOrDefault(), keySet(), values() 메서드에 대해 알아보게 되었던 문제였다. 이외에도 Iterator 활용에도 익숙해져야 한다. Hash문제에 대한 숙련도를 빠르게 길러야겠다.

문제설명

🤔 고민사항

• 어떤 자료형을 사용해야 할지부터 고민했다. Key - Value 페어가 굳이 필요하지 않았고, 중복을 제거하는 속성을 이용하기 위해 HashSet을 사용했다.
• 입력받는 폰켓몬의 종류(int로 표현되었다)를 HashSet에 삽입하면 중복되는 종류가 제거된다.
• HashSet의 크기는 즉, 중복이 제거되어 가질 수 있는 가장 많은 종류의 폰켓몬 숫자이다. 문제에서 N/2마리까지 가져가도 좋다고 했으니, HashSet의 크기가 N/2보다 크면 N/2만큼, 그렇지 않으면 HashSet의 크기만큼이 정답이 된다.

🧑‍💻 Code

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int thres = nums.length / 2;
        Set<Integer> hashset = new HashSet<Integer>();

        for(int i=0; i<nums.length; i++)
            hashset.add(nums[i]);

        if(hashset.size() > thres)
            answer = thres;
        else
            answer = hashset.size();

        return answer;
    }
}