Dev Chongmin

해시 문제라 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;
    }
}

이번 주 스터디에서는 자료구조 중 스택과 큐에 대해 공부하고 문제를 풀어보는 시간을 가졌습니다.

전에도 스택과 큐에 대해서 공부해봤기 때문에 구조적인 측면에서 이해는 문제가 없었습니다.

하지만 파이썬으로 구현했던 거라 자바로 구현하려고 하니 '어떤 클래스를 사용하고 어떤 메서드를 사용하지?'라는 생각이 들었습니다.

그래서 이걸 간단히 정리해 보려고 합니다.

스택과 큐의 자료구조와 메서드에 대해 정리하겠습니다.

스택(Stack)

스택은 LIFO(Last In First Out)의 특징을 가지고 있습니다.

이건 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질을 말합니다.

다르게 표현하면 가장 먼저 들어간 데이터가 가장 마지막으로 나오는 것을 뜻하기도 합니다.

재귀적인 함수, 알고리즘에 사용됩니다.

데이터를 삽입 및 삭제에 O(1), 탐색에 O(n) 시간이 걸립니다.

자바에서는 Stack 클래스를 구현하여 제공합니다.

Stack 클래스 메서드는 아래와 같습니다.

Stack<Integer> st = new Stack<Integer>();

큐(Queue)

큐는 FIFO(First In First Out)의 특성을 가지고 있습니다.

이는 먼저 집어넣은 데이터가 먼저 나오는 성질을 말합니다.

때문에 데이터를 집어넣으면 뒤부터 순차적으로 생성되고 

뺄 때는 가장 처음 데이터부터 나오게 됩니다.

삽입 및 삭제에 O(1), 탐색에 O(n)의 시간이 걸립니다.

CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬

너비 우선 탐색(BFS), 캐시 등에 사용됩니다.

자바에서 큐의 경우에는 클래스가 아닌 인터페이스를 제공합니다.

물론 구현해 놓은 클래스도 있기 때문에 그중 하나를 사용하면 됩니다.

예시로 ArrayDeque, ConcurrentLinkedDeque, LinkedList가 있습니다.

Deque의 경우에는 앞뒤로 데이터를 넣고 빼는 메서드를 가지고 있습니다.

메서드는 아래와 같습니다.

위 세 개와 아래 세 개의 메서드는 같은 기능을 하지만 오류를 반환하고 하지 않는 차이가 있습니다.

Queue<Integer> q = new LinkedList<Integer>()

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;
    }
}

Java의 정렬 방법 중 Java.util.Arrays 클래스의 sort() 메서드를 사용해 보겠습니다.

sort() 메서드는 매개변수로 기본타입과 객체를 받을 수 있습니다.

그리고 시작 인덱스와 종료 인덱스를 추가로 받아 부분 정렬이 가능합니다.

추가로 기본적으로 오름차순 정렬되지만 내림차순으로도 정렬 가능합니다. 

문법

sort(primitive type array) 

  - 매개변수로 기본타입 배열을 이용합니다.

  - int[], double[], float[], long[], short[], byte[], char[] 

sort(primitive type array, int startIndext, int endIndex)

  - 기본타입에 시작 인덱스 값과 종료 인덱스 값을 지정합니다.

sort(Object[] o)

  - 매개변수로 객체를 받습니다.

  - Wrapper Class 값을 받을 수 있습니다.

sort(Object[] o, int startIndext, int endIndex)

sort(T[] a, Comparator<? super T> c)

  - 매개변수로 객체를 받으며 Comparator의 메서드에 따라 정렬할 수 있습니다.

  - 주로 Comparator.reverseOrder()를 사용해 내림차순으로 사용합니다.

sort(T[] a, int startIndext, int endIndex, Comparator<? super T> c)

예시

오름차순

int[] arr = {5, 3, 4, 1, 2};

Arrays.sort(arr);

String[] arr2 = {"peach", "apple", "banana"};

Arrays.sort(arr2);

Arrays.stream(arr).forEach(a -> System.out.println(a));
Arrays.stream(arr2).forEach(a -> System.out.println(a));

//결과
1
2
3
4
5
apple
banana
peach

내림차순

  - 기본타입의 배열을 내림차순으로 정렬하고 싶다면

기본타입 배열을 래퍼 클래스로 감싸야 내림차순으로 정렬할 수 있습니다.

Integer[] arr = {5, 3, 4, 1, 2};

Arrays.sort(arr, Comparator.reverseOrder());

String[] arr2 = {"peach", "apple", "banana"};

Arrays.sort(arr2, Comparator.reverseOrder());

Arrays.stream(arr).forEach(a -> System.out.println(a));
Arrays.stream(arr2).forEach(a -> System.out.println(a));

//결과
5
4
3
2
1
peach
banana
apple

백준 1008 A/B

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        double c = (double)a/b;
        System.out.println(c);
    }
}

int로 a와 b의 값을 저장했기 때문에
출력을 그대로 하면 소수점이 출력되지 않는다.
따라서 double타입의 변수 c를 생성하고 a/b의 타입을 강제 변환시켜 저장한 후 출력했다.

백준 10998 A*B

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        System.out.println(a*b);
    }
}

System.in.read() 보다 편한 라이브러리를 찾았다.
Scanner를 사용하면 system in read가 아스키코드를 반환하는 것과 달리
입력한 값을 그대로 받아오고 입력받은 값은 공백을 기준으로 끊어서 가져올 수 있다.

백준 1001 A-B

import java.io.*;
public class Main {
    
    public static void main(String[] args) throws IOException {
        int a = System.in.read();
        System.in.read();
        int b = System.in.read();
        
        System.out.println(a-b);
    }
}

백준 1000 A+B

import java.io.*;

public class Main{
        public static void main(String[] args) throws IOException {
        int a = System.in.read();
        System.in.read();
        int b = System.in.read();
        System.out.println(a+b-96);
    }
}

System.in.read()는 입력받은 값의 아스키 값을 반환한다.
때문에 결괏값을 도출할 때 - 96을 해주었다.