Dev Chongmin

DFS/BFS 문제 유형의 한 문제입니다.

왜 우선 탐색 문제일까 고민하던 중에 스터디원이 준 힌트를 듣고 풀이 방법을 알아냈습니다.

트리로 보면 리프 노드를 구한다음 타깃과 같은 값을 가진 노드의 개수를 구하면 됩니다.

아래의 그림처럼 생각할 수 있습니다.

예를 들어 배열로 [4, 1, 2, 1]이 들어오고 타겟 넘버가 4일 경우의 수는 두 가지입니다.

import java.util.*;
class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        Queue<Integer> answerList = new LinkedList<Integer>();
        answerList.add(0);
        
        for(int i: numbers){
            int size = answerList.size();
            for(int k = 0; k < size; k++){
                int pop = answerList.poll();
                answerList.add(pop + i);
                answerList.add(pop - i);
            }
        }
        
        for(int i :answerList){
            if(i == target){
                answer += 1;
            }
        }
        
        return answer;
    }
}

그래프를 그리면서 탐색할 Queue를 하나 만들어 주고 루트 노드로 0을 넣어줬습니다.

이후로는 해당 레벨의 갯수 만큼 반복하며 하위 노드를 만들고 부모 노드를 삭제하는 것을 반복합니다.

마지막에는 큐에 리프 노드의 숫자들만 남게 됩니다.

해시 문제라 HashSet을 사용하긴 했는데 전체적인 사고방식은 수학 풀이 같습니다.

일단 N 마리의 포켓몬 중에서 N/2 마리의 포켓몬을 선택할 수 있고, 포켓몬의 종류 개수를 P라고 가정하겠습니다.

그렇다면 P가 N/2보다 크다면 가져갈 수 있는 포켓몬의 최대 종류의 수는 N/2의 값이되고

P가 N/2보다 작거나 같다면 가져갈 수 있는 포켓몬의 최대 종류의 수는 P가 됩니다.

nums = [피카츄, 피카츄, 파이리, 꼬부기]
hashset = [피카츄, 파이리, 꼬부기]

 때문에 위의 예시처럼 가져갈 수 있는 포켓몬의 수인 2마리보다 포켓몬의 종류 개수가 많다면

그냥 가져갈 수 있는 수를 리턴하면 됩니다. 

nums = [피카츄, 피카츄, 피카츄, 파이리, 파이리, 파이리]
hashset = [피카츄, 파이리]

반대로 위처럼 가져갈 수 있는 포켓몬의 숫자가 3마리인데 포켓몬의 종류가 그 숫자보다 적다면

포켓몬 종류의 수를 리턴하면 됩니다.

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        int length = nums.length;
        
        Set<Integer> ponketmon = new HashSet<Integer>();
        for(int i: nums){
            ponketmon.add(i);
        }
        
        if((int)length/2 < ponketmon.size()){
            return (int)length/2;
        }else{
            return ponketmon.size();
        }
    }
}

위에 코드는 제 풀이 코드입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/42587

3개의 배열을 이용해 풀었습니다.

answer는 프린터가 된 순서가 담길 배열입니다.

array는 매개변수로 입력받는 priorities의 배열이 큐로 변환될 배열입니다.

index는 array의 각 숫자들의 원래 인덱스를 저장할 배열입니다.

풀이 코드는 아래와 같은데 코드를 하나씩 풀어보면서 설명해보겠습니다.

import java.util.*;
class Solution {
    public int solution(int[] priorities, int location) {
        int[] answer = new int[priorities.length];
        Deque<Integer> array = new ArrayDeque<Integer>();
        Deque<Integer> index = new ArrayDeque<Integer>();
        
        for(int i = 0; i < priorities.length; i++ ){
            array.offer(priorities[i]);
            index.offer(i);
        }
        int sum = 1;
        while(array.peek() != null){
            int max = Collections.max(array);
            if(array.peek() < max){
                array.offer(array.poll());
                index.offer(index.poll());
            }else{
                array.poll();
                answer[index.poll()] = sum;
                sum += 1;
            }
        }
        
        return answer[location];
    }
}

초기값을 array와 index에 넣으면 위와 같습니다.

sum값은 프린터 되는 순서를 세어줄 변수입니다.

max는 array에서 가장 큰 값이 담기게 됩니다.

우선 array 배열의 첫 번째 값과 max값을 비교해서 첫 번째 값이 작을 경우

첫 번째 값을 배열 맨 뒤에 추가하고 인덱스의 첫 번째 값도 맨 뒤에 추가해줍니다.

이것을 반복하다가 array의 가장 큰 값과 만나면 가장 큰 값을 array에서 제거합니다.

그리고 answer의 해당 index에 순서 값인 sum을 넣어 주고 sum을 + 1 해줍니다.

이렇게 반복해서 array의 숫자가 사라질 때까지 반복하면 

프린터 순서가 담긴 answer 배열이 생성됩니다.

거기서 location으로 들어온 위치의 값을 반환하면 됩니다.

https://school.programmers.co.kr/learn/courses/30/lessons/12906

연속된 숫자가 중복될 경우 하나만 남기고 지워주면 되는 문제입니다.

처음에는 문제를 잘못 일고 중복된 숫자를 다 지우는 것인 줄 알았는데 아니었습니다.

제 문제 풀이 방식의 기본 개념은 아래와 같습니다.

우선 결과값을 담을 리스트와 비교할 숫자를 담을 변수를 하나 준비합니다.

그리고 배열의 첫 번째 숫자를 배열과 비교할 숫자의 변수에 담고 시작합니다.

그리고 배열을 순차적으로 돌면서 비교할 숫자와 숫자를 비교해 같으면 무시합니다.

다르다면 숫자를 결괏값 리스트에 담고 비교 변수도 같은 값으로 변경해줍니다. 

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        List<Integer> l = new ArrayList<Integer>();
        int s = -1;
        for(int i : arr){
            if(s != i){
                l.add(i);
                s = i;
            }
        }
        int[] answer = new int[l.size()]; 
        for(int k = 0; k < l.size(); k++){
            answer[k] = l.get(k);
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/42748

정렬 알고리즘 1단계 문제입니다.

java.util.Arrays 클래스에 있는 메서드를 사용하지 않았다면 1단계지만 상당히 애먹었을 것 같습니다.

우선 코드는 아래와 같습니다.

import java.util.*;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = {};
        answer = new int[commands.length];
        int index = 0;
        for(int[] ijk : commands){
            int[] arr = Arrays.copyOfRange(array,ijk[0]-1,ijk[1]);
            Arrays.sort(arr);
            answer[index] = arr[ijk[2]-1];
            index += 1;
        }

        return answer;
    }
}

문제 풀이의 키는 commands의 이차원 배열을 분리해 i, j, k 각각의 값을 추출하는 것이라 판단했습니다.

그래서 향상된 for문을 사용해 ijk라는 일차원 배열로 값을 받고 배열의 인덱스를 사용해 해결했습니다.

배열이 있으면 자연스럽게 향상된 for문을 사용하게 되는데 이번 문제의 경우 일반 for문을 사용했으면 

index 변수를 새로 생성하지 않아도 됩니다.

아래의 코드는 같이 공부하는 스터디원의 풀이입니다.

Arrays 클래스의 copyOfRange() 메서드를 사용하지 않고 풀려고 했습니다.

그랬더니 sort() 메서드를 사용할 경우 배열의 실제 데이터까지 변경되어 올바른 답이 나오지 않았습니다.

그다음에는 새로운 int[] 배열을 만들어 매번 매개변수 array값으로 선언해주면 되지 않을까?라고 생각했지만

이때 새로운 int[] 배열이 array의 메모리 주소 값을 참조하는 것이기 때문에 새로운 int[] 배열을 정렬할 경우 실제 array의 

데이터 값도 정렬되어 올바른 답이 나오지 않았습니다.

때문에 얕은복사가 아닌 깊은 복사가 필요했고, clone()이라는 메서드를 생성해서 데이터 값을 담아 문제를 해결했습니다.

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        for(int a = 0; a < commands.length; a++){
            
            int i = commands[a][0];
            int j = commands[a][1];
            int k = commands[a][2];
            int[] arr = array.clone(); // clone을 사용하지 않는다면?
             
            Arrays.sort(arr,i-1,j);
            answer[a] = arr[i+k-2];
        }
        return answer;
    }
}