IPv4

[ 해결 방법 ] 

1. DP 알고리즘 활용

2. 위치한 값이 1일 때, [ 왼쪽 / 왼쪽 위 대각선 / 위쪽 ] 의 값을 확인해 가장 작은 값에 +1 해준다.

DP 알고리즘

- DP 사용 조건

1) 겹치는 부분 문제 : 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

ex. 이진 탐색과 피보나치 수열

이진 탐색 : 정렬된 배열 내에서 그 위치를 바로 찾기 때문에 재사용 과정을 거치지 않아 DP 사용 조건에 해당하지 않는다.

피보나치 수열 : f(n) = f(n-1) + f(n-2) 이므로, 트리구조로 동일한 부분 문제가 중복되어 나타나 DP 사용 조건에 해당한다.

2) 최적 부분 구조 : 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우

ex. 최적 경로 문제

여러 경로 중 [ A-X, X-B ] 가 가장 짧은 경로라면 A-X-B 가 정답이 된다.
이와 같이 부분 문제의 최적의 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않는 경우 DP를 사용할 수 있다.

- DP 사용 과정

1) DP로 풀 수 있는 문제인지 확인

2) 변수 간 점화식 만들기

3) Memoization

: 변수의 값에 따른 결과를 저장하는 것을 메모라고 부른다. 보통 배열을 사용하며, 1~3차원 배열이 될 수 있다.

5) 기저 상태 파악하기

: 가장 작은 문제의 상태를 파악해야 한다.

6) 구현하기

Bottom-Up ( 반복문 - Tabulation )
아래에서부터 계산을 수행해 누적시켜 전체 큰 문제를 해결하는 방식

Top-Down ( 재귀 - Memoization )
위에서부터 바로 호출하며 결과 값을 재귀를 통해 전이시켜 재활용하는 방식

[ 문제 코드 ]

- Tabulation 방식으로 해결

public class 가장큰정사각형찾기 {

    /**
     * TODO
     *  - 목표: 가장 큰 정사각형을 찾아라
     *  - DB 알고리즘 활용
  장  * **/

    public static void main(String[] args) {
        int[][] arr = {{0, 0, 1, 1}, {1,1,1,1}};
        int solution = solution(arr);
        System.out.println(solution);
    }

    public static int solution(int [][]board)
    {
        int answer = 0;

        int[][] map = new int[board.length + 1][board[0].length + 1];

        int maxLen = 0;
        for (int i = 1; i <= board.length; i++) {
            for (int j = 1; j <= board[0].length; j++) {
                if(board[i-1][j-1] != 0) {
                    int min = Math.min(Math.min(map[i - 1][j], map[i][j - 1]), map[i - 1][j - 1]);
                    map[i][j] = min + 1;

                    maxLen = Math.max(maxLen, min + 1);
                }
            }
        }

        return maxLen * maxLen;
    }
}

[ 문제 해결1 ]

각 배열에 원소의 자릿 수를 비교해서 정렬해보니 시간이 오버된다는 것을 알 수 있었습니다.

[ 문제 해결2 ]

Comparator 을 사용해 문자열을 붙쳐서 판단 후, 내림차 순 해본다.

compareTo method 는 앞에서부터 비교하고 다른 문자열이 나오면 'a-b' 순서로 문자의 아스키 코드 값을 뺀 결과를 리턴합니다.

* 내림차순 : (o2+o1).compareTo(o1+o2);

* 오름차순 : (o1+o2).compareTo(o1+o2);

[ 코드 ]

import java.util.*;

public class 가장큰수 {

    /**
     *  TODO
     *      - 문제: 주어진 정수에서 가장 큰 수를 만들어라
     *      - 정수 배열을 문자 배열로 변환
     *      - Comparator 을 활용해 내림차 순 정렬
     *      - compareTo 의 아스키 코드 값 비교를 이용
     * **/

    public static void main(String[] args) {
        int[] arr = {3, 30, 34, 5, 9};
        String solution = solution(arr);
        System.out.println(solution);

    }

    public static String solution(int[] numbers) {
        String answer = "";

        String[] arr = new String[numbers.length];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = String.valueOf(numbers[i]);
        }

        Arrays.sort(arr, new Comparator<String>() { // 내림차순 정렬
            @Override
            public int compare(String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);
            }
        });

        if(arr[0].equals("0")) return "0";

        for (String i : arr) {
            answer += i;
        }

        return answer;
    }
}

[ 개념 ]

- Comparator 이 무엇인가?

기본 정렬이 아닌 다른 기준으로 사용하고 싶을 때 사용하는 인터페이스입니다.

그 중 compare를 구현함으로써 임의의 클래스에 대해 정렬 기준을 만들 수 있습니다.

compare override method

- 첫 번째 인자 < 두 번째 인자 : 음수
- 첫 번째 인자 > 두 번째 인자 : 양수
- 첫 번째 인자 == 두 번째 인자 : 0

그래서 Collections.sort 에 comparator 를 인자로 사용하는 부분을 살펴보겠습니다.

인자에는 다음과 같은 항목이 들어갈 수 있습니다.

1. 첫번째 인자 : 서로 다른 클래스에 존재하는 리스트

2. 두번째 인자 : Comparator 인터페이스의 compare 함수를 오버라이딩한 클래스

이렇게 사용하면 사용자가 원하는 형태로 정렬을 구현할 수 있게 됩니다.

다음 큰 숫자

	- 문제 : n의 다음 튼 숫자를 정의해라
     1) n 보다 큰 자연수
     2) n 을 2진수로 변환했을 때 1의 갯수
     3) 조건 1,2를 만족하는 수 중 가장 작은 수

     - 과정 :
     1) 2진수로 변환 후 갯수 구한다. (k)
     2) n을 증가시키며 k를 비교한다.

위 과정을 소스코드로 구현하면 다음과 같습니다.

[ 소스 코드 ]

public class 다음큰숫자 {

    /**
     - 문제 : n의 다음 튼 숫자를 정의해라
     1) n 보다 큰 자연수
     2) n 을 2진수로 변환했을 때 1의 갯수
     3) 조건 1,2를 만족하는 수 중 가장 작은 수

     - 과정 :
     1) 2진수로 변환 후 갯수 구한다. (k)
     2) n을 증가시키며 k를 비교한다.
     **/

    public static void main(String[] args) {
        System.out.println(solution(78));
    }

    public static int solution(int n) {
        int answer = 0;
        String s = Integer.toBinaryString(n);
        int nLen = 0;
        for (int i = 0; i < s.length(); i++) {
            if('1' == s.charAt(i)) nLen++;
        }

        int oneLen = 0;
        while(n <= 1000000){
            n += 1;
            String s2 = Integer.toBinaryString(n);
            for (int i = 0; i < s2.length(); i++)
                if('1' == s2.charAt(i)) oneLen++;
            if(nLen == oneLen) break;
            oneLen = 0;
        }

        answer = n;
        return answer;
    }
}

124 나라의 숫자

위 문제를 단순히 나머지3으로 구하려고 하면 문제가 풀리지 않는다는 것을 알 수 있습니다.

	
    - 문제 :
     124 나라에서는 10진법이 아닌 자신만의 규칙으로 수를 표현
     1) 자연수만 존재
     2) 모든 수를 표현할 때, 1/2/4 만 사용
     ex. 3 = 4, 4 = 11, 5 = 12, 6 = 14 ...

     - 출력:
     n 이 입력됬을 때, 124 나라에서 사용하는 숫자로 바꾼 값을 반환해라

     - 공식:
     1) 입력 n이 들어온다.
     2) n의 나머지 3을 구해 k값을 뽑는다.
     3) k 값은 [ 4, 1, 2 ] 배열의 인덱스 값을 의미한다.
     4) n을 3으로 나눠준다.
     5) 이때, 나머지가 0이면 나눠떨어지는 것이므로 n을 3으로 나눈 후 -1을 해준다.

위의 공식을 코드로 구현하면 다음과 같습니다.

[ 소스 코드 ]

public class 나라의숫자 {

    /**
     - 문제 :
     124 나라에서는 10진법이 아닌 자신만의 규칙으로 수를 표현
     1) 자연수만 존재
     2) 모든 수를 표현할 때, 1/2/4 만 사용
     ex. 3 = 4, 4 = 11, 5 = 12, 6 = 14 ...

     - 출력:
     n 이 입력됬을 때, 124 나라에서 사용하는 숫자로 바꾼 값을 반환해라

     - 공식:
     1) 입력 n이 들어온다.
     2) n의 나머지 3을 구해 k값을 뽑는다.
     3) k 값은 [ 4, 1, 2 ] 배열의 인덱스 값을 의미한다.
     4) n을 3으로 나눠준다.
     5) 이때, 나머지가 0이면 나눠떨어지는 것이므로 n을 3으로 나눈 후 -1을 해준다.

     **/

    public static void main(String[] args) {
        System.out.println(solution(5));
    }

    public static String solution(int n) {
        String answer = "";
        String[] number = {"4", "1", "2"};

        while (n > 0) {
            int reminder = n % 3;
            n /= 3;
            if(reminder == 0) n--;
            answer = number[reminder] + answer;
        }

        return answer;
    }
}

[ 입출력 예제 ]

- 캐시 크기 : 3

- 과정

1) seoul, pangyo, jeju : 15

2) newyork, seoul, pangyo : 20

3) la, newyork, seoul : 25

5) jeju, la, newyork : 30

6) pangyo, jeju, la : 35

7) seoul, pangyo, jeju : 40

8) newyork, seoul, pangyo : 45

9) la, newyork, seoul, pangyo : 50

[ 출력 ]

- 실행시간 : 50

[ 소스코드 ]

1) 첫번째 제출

import java.util.ArrayList;
import java.util.List;
import java.util.Locale;

public class 캐시 {

    /**
     - 설명 :
     1. 테스팅 업무는 어피치
     2. 제이지가 작성한 데이터베이스에서 게시물 불러오는 부분의 실행시간이 오래걸림
     3. 어피치는 제이지에게 해당 로직 개선하라고 지시
     4. 제이지는 DB 캐시를 적용하여 성능 개선을 시도하지만 효율적인 캐시 크기를 몰라 난감

     - 입력 형식 :
     캐시 크기 ( cacheSize ), 도시 이름 배열 ( cities )

     - 입력 조건 :
     공백, 숫자, 특수문자 등이 없는 영문자
     대소문자 구분안함
     최대 20자

     - 조건 :
     캐시 교체 알고리즘 > LRU 사용
     cache hit일 경우 실행 시간은 1
     cache miss일 경우 실행 시간은 5

     - 용어 설명 :
     1) 캐시 히트 = 캐시 메모리에 찾는 데이터가 존재했을 때
     2) 캐시 미스 = 캐시 메모리에 찾는 데이터가 존재하지 않았을 때
     **/

    public static void main(String[] args) {
        int cache = 3;
        String[] cities = {
                "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"
        };
        System.out.println(solution(cache, cities));
    }


    public static int solution(int cacheSize, String[] cities) {
        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toLowerCase(Locale.ROOT);
        }
        int answer = LRU(cacheSize, cities);
        return answer;
    }

    public static int LRU(int s, String[] cities){
        List<String> temp = new ArrayList<>();
        int excuteTime = 0;
        int cnt = 0;
        boolean check = false;

        while (cnt < cities.length) {
            for (int i = 0; i < temp.size(); i++) {
                if (temp.get(i).equals(cities[cnt])) {
                    excuteTime += 1;
                    temp.add(0, cities[cnt]);
                    check = true;
                    break;
                }
            }
            
            if (!check){
                temp.add(0, cities[cnt]);
                excuteTime += 5;
            }

            if (temp.size() > s) {
                temp.remove(temp.size() - 1);
            }

            cnt++;
            check = false;
        }

        return excuteTime;
    }
}

테스트 9번부터 실패가 발생함을 볼 수 있습니다.

그 이유는 기존의 캐시에 같은 값이 있는 경우 기존의 값을 삭제해주고 최신화를 해줘야하는데 이 부분을 놓쳤기 때문입니다.

( 추가된 부분 )

[ 정답 소스 코드 ]

import java.util.ArrayList;
import java.util.List;
import java.util.Locale;

public class 캐시 {

    /**
     - 설명 :
     1. 테스팅 업무는 어피치
     2. 제이지가 작성한 데이터베이스에서 게시물 불러오는 부분의 실행시간이 오래걸림
     3. 어피치는 제이지에게 해당 로직 개선하라고 지시
     4. 제이지는 DB 캐시를 적용하여 성능 개선을 시도하지만 효율적인 캐시 크기를 몰라 난감

     - 입력 형식 :
     캐시 크기 ( cacheSize ), 도시 이름 배열 ( cities )

     - 입력 조건 :
     공백, 숫자, 특수문자 등이 없는 영문자
     대소문자 구분안함
     최대 20자

     - 조건 :
     캐시 교체 알고리즘 > LRU 사용
     cache hit일 경우 실행 시간은 1
     cache miss일 경우 실행 시간은 5

     - 용어 설명 :
     1) 캐시 히트 = 캐시 메모리에 찾는 데이터가 존재했을 때
     2) 캐시 미스 = 캐시 메모리에 찾는 데이터가 존재하지 않았을 때
     **/

    public static void main(String[] args) {
        int cache = 3;
        int cache2 = 0;
        int cache3 = 2;
        String[] cities = {
                "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"
        };
        String[] cities2 = {
                "Jeju", "Pangyo", "Seoul", "NewYork", "LA"
        };
        String[] cities3 = {
                "Jeju", "Pangyo", "NewYork", "newyork"
        };
        System.out.println(solution(cache3, cities3));
    }


    public static int solution(int cacheSize, String[] cities) {
        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toLowerCase(Locale.ROOT);
        }
        int answer = LRU(cacheSize, cities);
        return answer;
    }

    public static int LRU(int s, String[] cities){
        List<String> temp = new ArrayList<>();
        int excuteTime = 0;
        int cnt = 0;
        boolean check = false;

        while (cnt < cities.length) {
            for (int i = 0; i < temp.size(); i++) {
                if (temp.get(i).equals(cities[cnt])) {
                    excuteTime += 1;
                    temp.remove(temp.get(i));
                    temp.add(0, cities[cnt]);
                    check = true;
                    break;
                }
            }

            if (!check){
                temp.add(0, cities[cnt]);
                excuteTime += 5;
            }

            if (temp.size() > s) {
                temp.remove(temp.size() - 1);
            }

            cnt++;
            check = false;
        }

        excuteTime += (s - temp.size());

        return excuteTime;
    }
}

문제 설명

두 배열 각각에서 하나의 숫자를 뽑아 두 수를 곱합니다.
이러한 과정에서 배열의 길이만큼 반복하여 두 수를 곱한 값을 누적하여 더합니다.
이때 최종적으로 누적된 값이 최소가 되는게 목표입니다.

조건

각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자를 다시 뽑을 수 없음

해결 과정

1) 예를 들어, [ 1*2+3*3= 11 ], [ 1*3+3*2 = 9 ] 이와 같이 가장 큰 수에 가장 작은 수를 곱해줘야 합니다.
2) 그래서 두 배열 각각을 오름차순, 내림차순으로 정렬한다.
3) 곱을 누적시킨다.

소스코드

import java.util.*;

public class 최솟값만들기 {

    /**
     - 문제 설명:
     두 배열 각각에서 하나의 숫자를 뽑아 두 수를 곱합니다.
     이러한 과정에서 배열의 길이만큼 반복하여 두 수를 곱한 값을 누적하여 더합니다.
     이때 최종적으로 누적된 값이 최소가 되는게 목표입니다.

     - 조건 :
     각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자를 다시 뽑을 수 없음

     - 해결 과정 :
     1) 예를 들어, [ 1*2+3*3= 11 ], [ 1*3+3*2 = 9 ] 이와 같이 가장 큰 수에 가장 작은 수를 곱해줘야 합니다.
     2) 그래서 두 배열 각각을 오름차순, 내림차순으로 정렬한다.
     3) 곱을 누적시킨다.
     **/

    public static void main(String[] args) {
        int[] A = {1,2};
        int[] B = {3,4};
        System.out.println(solution(A,B));
    }

    public static int solution(int []A, int []B)
    {
        int answer = 0;
        Integer[] Bin = new Integer[B.length];
        Arrays.sort(A);

        for (int i = 0; i < B.length; i++) {
            Bin[i] =Integer.valueOf(B[i]);
        }

        Arrays.sort(Bin,Collections.reverseOrder());

        for (int i = 0; i < B.length; i++) {
            answer += A[i] * Bin[i];
        }

        return answer;
    }
}

문제 설명

: 1 ~ n까지 번호가 붙어 있는 n명의 사람이 영어 끝말잇기 진행
 1) 1번부터 번호순으로 차례대로 단어 말함
 2) 마지막 사람이 단어를 말한 다음 다시 1번부터 시작
 3) 앞 사람이 말한 단어의 마지막 문자로 시작하는 단어 말함
 4) 이전에 등장했던 단어는 사용 못함
 5) 한 글자 단어는 사용 금지

출력

가장 먼저 탈락하는 사람의 번호, 그 사람이 몇 번째에 탈락하는지를 구함

조건

1) 단어길이 - 2~50
2) 배열길이 - n ~ 100이하
3) 소문자
4) 탈락자가 생기지 않는다면 0,0 반환

해결 방법

1) 경우에 대한 조건문 작성
2) 번호 : i+1 % n
3) 몇 번째 차례 : i / n 보다 큰 첫번째 정수

소스코드

import java.util.ArrayList;
import java.util.Arrays;

public class 영어끝말잇기 {
    /**
    - 문제 설명: 1 ~ n까지 번호가 붙어 있는 n명의 사람이 영어 끝말잇기 진행
     1) 1번부터 번호순으로 차례대로 단어 말함
     2) 마지막 사람이 단어를 말한 다음 다시 1번부터 시작
     3) 앞 사람이 말한 단어의 마지막 문자로 시작하는 단어 말함
     4) 이전에 등장했던 단어는 사용 못함
     5) 한 글자 단어는 사용 금지

     - 출력 :
     가장 먼저 탈락하는 사람의 번호, 그 사람이 몇 번째에 탈락하는지를 구함

     - 조건 :
     1) 단어길이 - 2~50
     2) 배열길이 - n ~ 100이하
     3) 소문자
     4) 탈락자가 생기지 않는다면 0,0 반환

     - 해결 방법 :
     1) 경우에 대한 조건문 작성
     2) 번호 : i+1 % n
     3) 몇 번째 차례 : i / n 보다 큰 첫번째 정수

     **/
    public static void main(String[] args) {
        String[] input = {"hello", "one", "even", "never", "now", "world", "draw"};
        String result = Arrays.toString(solution(2, input));
        System.out.println(result);

    }

    public static int[] solution(int n, String[] words) {
        ArrayList<String> arr = new ArrayList<>();
        int[] answer = new int[2];
        String prev = words[0];
        arr.add(words[0]);

        for(int i=1; i<words.length; i++){
            char CanFirstLetter = prev.charAt(prev.length()-1);
            if(words[i].length() == 1){
                System.out.println("issue oneLetter: "+i);
                answer[0] = (i % n) + 1;
                answer[1] = (i/n)+1;
                return answer;
            }
            if(CanFirstLetter != words[i].charAt(0)){
                System.out.println("issue not: "+i);
                answer[0] = (i % n) + 1;
                answer[1] = (i/n)+1;
                return answer;
            }
            if (arr.contains(words[i])) {
                System.out.println("issue contain: "+i);
                answer[0] = (i % n) + 1;
                answer[1] = (i/n)+1;
                return answer;
            }

            prev = words[i];
            arr.add(words[i]);
        }

        answer[0] = 0;
        answer[1] = 0;
        return answer;
    }
}

문제

짝지어 제거하기

문제 설명

> 입력 : 알파벳 소문자로 이뤄진 문자열
> 과정 :
 1) 문자열에서 같은 알파벳 두 개가 붙어있는 짝을 찾음
 2) 과정을 반복해서 문자열 모두 제거하면 짝지어 제거하기가 종료
 3) 성공적인 수행은 1, 아니면 0 을 리턴

해결 방식

1) Stack 활용

[ 반복문 ]
2) 문자열을 순회하며 스택에서 peek()한 요소와 현재 순회중인 문자가 같으면 pop
3) 아니면 push()
4) 만약 스택이 비어있으면 push

[ 출력 ]
5) 만약 스택이 비어 있으면 1 출력
6) 아니면 0 출력

소스코드

import java.util.Stack;

public class 짝지어제거하기 {
    /**
     - 문제 설명:
     > 입력 : 알파벳 소문자로 이뤄진 문자열
     > 과정 :
      1) 문자열에서 같은 알파벳 두 개가 붙어있는 짝을 찾음
      2) 과정을 반복해서 문자열 모두 제거하면 짝지어 제거하기가 종료
      3) 성공적인 수행은 1, 아니면 0 을 리턴

     - 해결 방식:
     1) Stack 활용
     [ 반복문 ]
     2) 문자열을 순회하며 스택에서 peek()한 요소와 현재 순회중인 문자가 같으면 pop
     3) 아니면 push()
     4) 만약 스택이 비어있으면 push
     [ 출력 ]
     5) 만약 스택이 비어 있으면 1 출력
     6) 아니면 0 출력

     **/
    public static void main(String[] args) {
        System.out.println(solution("baabaa"));
    }

    public static int solution(String s)
    {
        int answer = -1;

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            if(stack.isEmpty()){
                stack.push(s.charAt(i));
            }
            else if (stack.peek() == s.charAt(i)) {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
        }

        if(stack.isEmpty()) answer = 1;
        else answer = 0;

        return answer;
    }
}

문제 주제

숫자 n이 주어지고, 1234567 로 나눈 나머지를 리턴하는 피보나치 함수를 작성해라

문제 해결 방법

1. 재귀는 시간 초과

2. 반복문을 사용하되 각 요소 값마다 123456 나머지를 구해서 배열에 넣어줌

3. 입력받은 n의 인덱스에 위치하는 배열 요소 값을 반환

public class 피보나치수열 {

    /*
    - 문제 : 숫자 n이 주어지고, 그 수를 1234567 로 나눈 나머지를 리턴하는 함수를 작성해라

    * */
    public static void main(String[] args) {
        System.out.println(solution(3));
    }

    public static int solution(int n) {
        int[] answer = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            if(i==0) answer[i] = 0;
            else if(i==1) answer[i] = 1;
            else{
                int sum = answer[i-2] + answer[i-1];
                answer[i] = sum % 1234567;
            }
        }

        return answer[n];
    }

}

N개의 최소 공배수

문제 요구사항 :

- 배열의 공배수가 되는 가장 작은 숫자를 구해라

문제 해결 과정 :

- 유클리드 호제법 알고리즘으로 최대 공약수를 구한다.
- 첫 번째 원소 * 두 번째 원소 / gcd 의 계산을 해서 배열들의 최소 공배수를 구함

[ 소스 코드 ]

public class n개의최소공배수 {
    /*
    - 배열의 공배수가 되는 가장 작은 숫자를 구해라

    [ 해결과정 ]
    - 유클리드 호제법 알고리즘으로 최소 공배수/최대 공약수를 구한다.
    - 여기서 구한 최소 공배수를 다음 배열에 반복
     */
    public static void main(String[] args) {
        int[] arr = {2, 6, 8, 14};
        System.out.println(solution(arr));
    }

    public static int solution(int[] arr) {
        int answer = arr[0];

        for (int i = 1; i < arr.length; i++) {
            int gcd = gcd(answer, arr[i]); // 최대 공약수
            answer = answer * arr[i] / gcd; // 최소 공배수
        }
        return answer;
    }

    public static int gcd(int a,int b){
        int max = Math.max(a, b);
        int min = Math.min(a, b);

        while(max % min != 0){
            int r = max % min;
            max = min;
            min = r;
        }
        return min;
    }
}

[ 문제 설명 ]

문제를 정리하면 다음과 같습니다.

- 문제 설명:
길이가 같은 두 개의 큐가 주어짐
> 하나의 큐를 골라 원소를 추출
> 추출된 원소를 다른 큐에 집어 넣는 작업을 수행
> 그 작업을 통해 각 큐의 원소 합을 같게 만듬
> 이때, 필요한 작업의 최소 횟수를 구해라
> 한 번씩 pop,insert 를 하면 작업 수행 1회로 간주

- 주의
> long type 권장
> 큐 길이 : 30만
> 원소 크기 : 10에 9승

[ 해결 방법 ]

* s1 = 배열1의 합 | s2 = 배열2의 합 | sum = 배열1,2의 합/2

* problem1,2 = pop(), insert() 한 횟수

1) 입력 받은 배열을 Queue 에 넣어준다.

2) 두 배열의 합이 만약 홀수이면 -1을 리턴해준다.

3) 합을 나누기 2를 해준다.

4) 반복문을 통해 아래의 내용을 비교해준다. ( 반복문은 problem1,2 가 큐의 길이가 두배가 되면 종료 )

 - s1 이 sum 과 같으면 problem1 + problem2 를 리턴해준다.

 - s1 이 sum 보다 크면,

s1 에 queue1 에서 peek() 한 값을 빼줌
s2 에는 더해줌
queue2 에 queue1 을 pop() 한 값을 poll() 해줌
problem1 을 하나 증가시킴

- 둘 다 아니면,

s2 에 queue2 에서 peek() 한 값을 빼줌
s1 에 더해줌
queue1 에 queue2를 pop()한 값을 poll() 해줌
problem2 를 하나 증가시팀

[ 소스 코드 ]

import java.util.ArrayDeque;
import java.util.Queue;

public class 큐문제 {

    /**

     - 문제 설명:
     길이가 같은 두 개의 큐가 주어짐
     > 하나의 큐를 골라 원소를 추출
     > 추출된 원소를 다른 큐에 집어 넣는 작업을 수행
     > 그 작업을 통해 각 큐의 원소 합을 같게 만듬
     > 이때, 필요한 작업의 최소 횟수를 구해라
     > 한 번씩 pop,insert 를 하면 작업 수행 1회로 간주

     - 주의
     > long type 권장
     > 큐 길이 : 30만
     > 원소 크기 : 10에 9승

     **/

    public static void main(String[] args) {
        int[] queue1 = {3, 2, 7, 2};
        int[] queue2 = {4, 6, 5, 1};
        int solution = solution(queue1, queue2);
        System.out.println(solution);

    }

    public static int solution(int[] queue1, int[] queue2) {
        Queue<Integer> que1 = new ArrayDeque<>();
        Queue<Integer> que2 = new ArrayDeque<>();

        long s1 = 0, s2 = 0, sum = 0;

        for (int i = 0; i < queue1.length; i++) {
            que1.add(queue1[i]);
            s1 += queue1[i];

            que2.add(queue2[i]);
            s2 += queue2[i];
        }

        sum = s1 + s2;

        // 홀수가 될 경우 풀 수 없음
        if (sum % 2 == 1) return -1;

        sum = sum/2;

        int problem1 = 0;
        int problem2 = 0;
        int limit = queue1.length * 2;

        while (problem1 <= limit && problem2 <= limit) {
            if(s1 == sum) return problem1 + problem2;
            else if(s1 > sum){
                s1 -= que1.peek();
                s2 += que1.peek();
                que2.add(que1.poll());
                problem1++;
            }
            else {
                s1 += que2.peek();
                s2 -= que2.peek();
                que1.add(que2.poll());
                problem2++;
            }
        }
        return -1;
    }
}

[ 문제 해석 ]

갈색 격자수, 노란색 격자 수 yellow 가 매개변수로 주어질 때,
카펫의 가로/세로 크기를 수너대로 담은 배열을 나타내라

- 단, 중앙에는 노란색, 테두리 1줄은 갈색으로 칠해져 있음

[ 풀이 방법 ]

1) 갈색,노란색 격자 수를 더한 값의 약수를 구한다.
2) 그 약수 중에 정답이 있다.
3) (가로-2) * (세로-2) = 노란색의 개수이다.

* 조건 : 가로 길이 >= 세로 길이

[ 처음 시도 한 소스 코드 ]

import java.util.ArrayList;

public class 카펫 {

    /**
    - 문제 해석:
     갈색 격자수, 노란색 격자 수 yellow 가 매개변수로 주어질 때,
     카펫의 가로/세로 크기를 수너대로 담은 배열을 나타내라

     - 단, 중앙에는 노란색, 테두리 1줄은 갈색으로 칠해져 있음

     - 풀이 방법:
     1) 갈색,노란색 격자 수를 더한 값의 약수를 구한다.
     2) 그 약수 중에 정답이 있다.
     3) (가로-2) * (세로-2) = 노란색의 개수이다.

     * 조건 : 가로 길이 >= 세로 길이
    **/

    static int brown;
    static int yellow;

    public static void main(String[] args) {
        brown = 10;
        yellow = 2;
        int[] solution = solution();
        System.out.println(solution[0] + " " + solution[1]);
    }

    public static int[] solution() {
        int[] answer = new int[2];
        int sum = brown + yellow;
        ArrayList<String> calNumber = cal(sum);
        for (String i : calNumber) {
            String[] strArr = i.split(" ");
            int x = Integer.parseInt(strArr[0]);
            int y = Integer.parseInt(strArr[1]);

            if ((x - 2) * (y - 2) == yellow) {
                answer[0] = x;
                answer[1] = y;
            }
        }
        return answer;
    }

    public static ArrayList<String> cal(int n) {
        ArrayList<String> cal = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (i * j == n) {
                    if (i >= j) {
                        cal.add(i + " " + j);
                    }
                }
            }
        }

        return cal;
    }


}

[ 테스트 결과 ]

몇몇 테스트 코드에서 시간 초과가 발생함을 알 수 있습니다.

다른 사람의 코드를 가져와 비교해 보겠습니다.

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int sum = brown + yellow;
        
        for (int i = 3; i < sum; i++) {
            // 노란 격자가 가운데에 위치하기 위해 세로,가로가 모두 3이상이여야 하므로 3부터 시작
            int j = sum / i;
            // 가로길이를 바로 합에 나눠줘버려 세로를 구해줌
            
            if (sum % i == 0 && j >= 3) { 
            // 약수가 되고, j 길이도 3이상인 것을 선택
                int col = Math.max(i, j);
                int row = Math.min(i, j);
                // i,j 중 더 큰 값이 가로 길이가 됨
                
                int center = (col - 2) * (row - 2);
				// 가로-2 * 세로-2 = 노란색 격자 수 공식을 사용
                
                if (center == yellow) {
                    answer[0] = col;
                    answer[1] = row;
                    return answer;
                }
            }
        }
        return answer;
    }
}

* 출처 : https://easybrother0103.tistory.com/110

[ 풀이 방법 ]

스택을 이용하면 풀기 쉽습니다.

1) 문자열을 char 배열로 만들어줌

2) '(' 를 만나면 푸쉬

3) ')' 를 만나면 pop

* return false 가 되는 두 가지 경우

1) pop 하는데 스택이 비어 있을 때

2) pop 을 다 했는데 스택에 요소가 남아 있는 경우

import java.util.Stack;

public class 괄호문제 {

    static Stack<Character> stack = new Stack<>();

    public static void main(String[] args) {
        String s = ")()(";
        System.out.println(solution(s));
    }

    static boolean solution(String s) {
        boolean answer = true;

        char[] ch = s.toCharArray();
        for (int i = 0; i < ch.length; i++) {
            if (ch[i] == '(') {
                stack.push(ch[i]);
            } else if (ch[i] == ')') {
                if(stack.empty()){
                    return false;
                }
                Character pop = stack.pop();
            }
        }

        if(!stack.isEmpty()){
            return false;
        }

        return answer;
    }

}

위 문제는 DFS의 개념을 이해하고 있으면 한결 풀기 편합니다.

https://tjdwns4537.tistory.com/137?category=955960 

1. 재귀로 풀 수 있는가?

경우의 수를 생각해보면 배열의 첫 번째부터 끝까지 더 할 수도 있고, 뺄 수도 있습니다. 그래서 각 원소당 2개의 경우의 수가 발생합니다.

재귀 함수를 사용할 수 있는가에 대해 판단하는 기준은 시간복잡도로 계산하시면 됩니다.

일반적으로 500만 번 이하의 탐색을 하게 되면 재귀함수를 사용할 수 있다고 보고 있습니다.

그러면 최대 20개의 원소를 가진다고 했으므로, 100만 번 정도의 탐색을 하므로 충분히 사용 가능합니다.

2. 재귀로 풀 때 고려사항

재귀로 풀 때 고려해야하는 사항은 크게 두가지가 존재합니다.

- 수행 동작

: 한 번의 동작 안에 어떤 동작을 수행할 것인지를 정의 해야 합니다.

- 언제 탈출 시킬 것인가

: 탈출을 시켜야 재귀 함수가 종료가 되므로 위에 대한 부분도 생각해야합니다.

문제에 대해서는 재귀 함수가 콜 된 인덱스가 배열 길이만큼 되면 탈출 시키면 됩니다.

* 프로그래머스 문제 풀이 팁

: 바뀌지 않을 값들은 멤버 변수로 정의해 사용하는게 편리하다.

[ 소스 코드 ]

public class TargetNumber {

    /**
     1. 문제
     - n개의 음이 아닌 정수들 존재
     - 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟넘버 만들기
     - [ 1,1,1,1 ] 로 숫자3 을 만드는 방법을
        ( -1+1+1+1+1 = 3 )
        ( +1-1+1+1+1 = 3 ) ...
     **/

    static int answer = 0;
    static int[] numbers;
    static int target;

    public static void main(String[] args) {
        int[] numbers1 = {1, 1, 1, 1, 1};
        int[] numbers2 = {4,1,2,1};

        solution(numbers1, 3);
        System.out.println(answer);
    }

    public static int solution(int[] _numbers, int _target) {
        answer = 0;
        numbers = _numbers;
        target = _target;

        dfs(0,0);

        return answer;
    }

    public static void dfs(int index, int sum) {
        
        // 1. 탈출 방법
        if (index == numbers.length) { // 인덱스가 배열 길이가 될 때
            if(sum == target){ // 합이 타겟이 될 때
                answer++;
                return;
            }
        }

        // 2. 구현 동작
        try{
            // 덧셈을 수행
            dfs(index + 1, sum + numbers[index]);
            // 뺄셈을 수행
            dfs(index + 1, sum - numbers[index]);
        } catch (Exception e){

        }

    }
}

현재까지 풀었던 문제 중 가장 이해가 어려웠던 문제인것 같습니다.

확률과 통계에 대한 개념이 있으신 분들은 쉽다곤 하네요..

[ 풀이 ]

순열을 이용하는 문제입니다.

n이 3이면 3!의 경우의 수만 구하면되지만, 최대값인 20!의 값을 구해야 한다면 모든 경우의 수를 살펴볼 수 없습ㄴ디ㅏ.

따라서 k번째의 순열만 빠르게 구할 수 있는 방법을 찾아봐야합니다.

문제 예시를 먼저 보겠습니다.

1. [1, 2, 3]
2. [1, 3, 2]
3. [2, 1, 3]
4. [2, 3, 1]
5. [3, 1, 2]
6. [3, 2, 1]

n은 3인데 앞자리의 숫자는 2개를 기준으로 변경된다는 것을 알 수 있습니다.

만약 앞자리가 고정되어 있다면 나머지 2개의 숫자들만 사용해서 순열을 구하면 됩니다.

그래서 앞자리 교체주기를 생각해봅시다.

[ 1 ~~ ]

[ 2~~ ]

이렇게 앞자리가 바뀌는 교체주기는 (n-1)! 가 되는것을 알 수 있습니다.

그리고 k는 모든 순열에서 k번째 위치한 순열을 의미합니다.

그래서 만약 k가 5라면

arr [ index / (n-1)! ] 을 하게 되면 현재 주기에서 맨 앞에 위치한 숫자입니다.

여기서 k는 순번을 의미하므로 저희가 필요한 인덱스를 찾으려면 인덱스는 0부터 시작하므로 1을 빼줘야합니다.

따라서 초기 인덱스 값은 k-1로 잡아주면 됩니다.

즉, arr [ k-1 / (n-1)! ] 를 해주면 현재 주기에서의 맨 앞에 위치한 숫자의 인덱스가 됩니다.

예를 들어,

n = 5, k = 110 일 때를 예를 들어 보겠습니다.

- 모든 경우의 수 : 5!

- 맨 앞자리 교체주기 : 4!

- 맨 앞자리 숫자의 인덱스 : 109 / 4!

이제 맨 앞자리를 구했으니 다음 숫자를 구해봅시다.

그러면 맨 앞자리 하나의 숫자를 고정 해줬으므로 다음과 같이 그 다음 숫자를 구할 수 있습니다.

이를 위해선 두가지 작업이 추가적으로 더 구현됩니다.

 1) 인덱스 값을 다음 순열을 위해 재조정

 2) 사용한 배열 원소를 제거

인덱스 값은 현재 주기에서 가장 앞자리의 숫자를 찾아주는 역할을 합니다.

그래서 앞자리 숫자의 인덱스를 찾고 난 후 다음 순열에서도 맨 앞자리를 찾을 수 있도록 k 값을 재조정해줘야 합니다.

(k-1) % (n-1)! 해주면 됩니다.

이렇게하면 자연스레 (n-1)! 를 넘을 수 없고, 다음 경우의 수에서 맨 앞자리 숫자를 가리키는 인덱스를 동일한 로직으로 찾을 수 있습니다.

이때, 만약 k의 값이 0이 되면 정확하게 나눠떨어졌다는 소리이므로 반복문이 종료됩니다.

n = 4, k = 5 라고 예를 들어봅니다.

[ 1,2,3,4 ]
[ 1,2,4,3 ]
[ 1,3,2,4 ]
[ 1,3,4,2 ]
[ 1,4,2,3 ]
[ 1,4,3,2 ]
[ 2,1,3,4 ]

첫 번째 자리 수가 특정 수가 되는 경우 : (n-1)! 단위로 끊어짐

( 단, 앞이 1인 배열은 0번의 위치에 해당됩니다.
ex. [ 1,2,3,4 ] , [1,~~~] : 0
      [ 2,3,4,1 ] , [2,~~~] : 1... )

그래서 해당하는 위치를 구하려면
k / (n-1)! : 배열의 순서의 번호
k % (n-1)! : 배열 순서 내부 번호

import java.util.ArrayList;

public class skillCheck2 {
    /**
     - 문제 해석
     > 일렬로 줄 서 있음
     > 1~n 까지 번호가 매겨져 있음
     > n명의 사람이 줄 서는 방법은 여러가지 있음
     > 사람의 수 n, 자연수 k가 주어질 때, 사람을 나열하는 방법을 사전순으로 정렬
     > k번째 정렬된 수의 배열을 리턴
     **/
    public static void main(String[] args) {

    }
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        ArrayList<Integer> list = new ArrayList<>();

        int fn = 1;
        for (int i = 1; i <= n; i++) {
            fn *= i; // fac 구하기
            list.add(i);
        }
        k--;
        int idx = 0;
        while (idx < n) {
            fn /= n - idx;
            answer[idx++] = list.remove((int) (k / fn));
            k %= fn;
        }

        return answer;
    }
}

* 참조했던 블로그입니다.

https://gogoma.tistory.com/150

/**
     * - 문제
     * 방문하는 공항 경로를 배열에 담아 출력

     * - 조건
     * 1) 주어진 항공권을 모두 이용해 여행경로를 구성
     * 2) 항상 ICN 공항에서 출발
     * 3) 만약 출발 경로가 같을 경우 정렬 필요
**/

[ 제가 작성한 코드 ]

import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;

public class TripCourse {
    /**
     * - 문제
     * 방문하는 공항 경로를 배열에 담아 출력

     * - 조건
     * 1) 주어진 항공권을 모두 이용해 여행경로를 구성
     * 2) 항상 ICN 공항에서 출발
     **/

    private static boolean[] visit;
    private static Stack<String> stack = new Stack<>();
    private static String[] answer;
    private static int cnt = 0;

    public static void main(String[] args) {
        String[][] tickets = {
                {"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}
                ,{"ATL","ICN"},{"ATL","SFO"}};

        String[][] tickets2 = {
                {"ICN", "JFK"}, {"HND", "IAD"}, {"JFK", "HND"}
                };

        String res = Arrays.toString(solution(tickets));
        System.out.println(res);
    }

    public static String[] solution(String[][] tickets) {
        answer = new String[tickets.length + 1];
        visit = new boolean[tickets.length];
        answer[cnt++] = tickets[0][0];

        for (int i = 1; i < tickets.length; i++) {
            String prev = tickets[i-1][0];

            if (tickets[i][0].equals(prev)) {
                Arrays.sort(tickets, new Comparator<String[]>() {
                    @Override
                    public int compare(String[] o1, String[] o2) {
                        return o1[1].compareTo(o2[1]);
                    }
                });
                break;
            }
        }

        dfs(tickets,tickets[0][1],0);
        return answer;
    }

    public static void dfs(String[][] tickets, String start, int check) {
        stack.push(start);
        visit[check] = true;

        while (!stack.isEmpty()) {
            String nodeString = stack.pop(); // 방문 노드
            answer[cnt++] = start;
            for (int i = 0; i < tickets.length; i++) {
                if (tickets[i][0].equals(nodeString)) {
                    if(!visit[i]){
                        dfs(tickets, tickets[i][1], i);
                    }
                }
            }
        }
    }
}

[ 코드 채점 결과 ]

[ 다른 사람 코드 리뷰 ]

1) 모든 경우의 수를 구한 다음  Collections.sort() 를 통해 정렬하기 위해 리스트 선언

2) 첫 출발은 항상 "ICN" 이기 때문에 DFS 시작을 "ICN"으로 해주고, route 시작도 "ICN" 으로 시작해준다.

3) DFS 함수에서 모든 티켓을 다 썼을 때, allRoute에 구한 경로를 add() 해준다.

4) 연결되어 있는 공항으로 꼬리물기를 하며 티켓의 시작 공항이 start 와 같고 방문하지 않은경우

    dfs() 의 start 자리에 ticket[i][1] 을 넣고 재탐색해준다.

5) 이때 visited[i] = false 로 바꿔 주는 이유는 모든 경로를 탐색하기 위함이다.

6) 모든 경우의 수를 allRoute에 넣은 후 Collections.sort() 로 정렬하고

     첫번째 문자를 가져오게 되면 알파벳 순으로 가장 빠른 경로를 구할 수 있다.

     이때, split() 을 통해 문제에서 원하는 출력으로 바꿔준다.

import java.util.*;

public class TripCourse {
    /**
     * - 문제
     * 방문하는 공항 경로를 배열에 담아 출력

     * - 조건
     * 1) 주어진 항공권을 모두 이용해 여행경로를 구성
     * 2) 항상 ICN 공항에서 출발
     **/

    private static boolean[] visit;
    private static ArrayList<String> allRoute;

    public static void main(String[] args) {
        String[][] tickets = {
                {"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}
                ,{"ATL","ICN"},{"ATL","SFO"}};

        String[][] tickets2 = {
                {"ICN", "JFK"}, {"HND", "IAD"}, {"JFK", "HND"}
                };

        String res = Arrays.toString(solution(tickets));
        System.out.println(res);
    }

    public static String[] solution(String[][] tickets) {
        String[] answer = {};
        int cnt = 0;
        visit = new boolean[tickets.length];
        allRoute = new ArrayList<>();

        dfs("ICN", "ICN", tickets, cnt);

        Collections.sort(allRoute);
        answer = allRoute.get(0).split(" ");

        return answer;

    }

    public static void dfs(String start, String route, String[][] tickets, int cnt) {
        if (cnt == tickets.length) {
            allRoute.add(route);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if (start.equals(tickets[i][0]) && !visit[i]) {
                visit[i] = true;
                dfs(tickets[i][1], route + " " + tickets[i][1], tickets, cnt+1);
                visit[i] = false;
            }
        }

    }
}

    /**

     - 문제 이해하기
     n개의 노드 그래프
     1~n까지의 각 노드
     1번 노드에서 가장 멀리 떨어진 노드의 갯수구하기
     가장 멀리 떨어진 노드란 최단 경로로 이동했을 때 간선의 개수가 가장 많은 노드

     - 해결 과정
     * bfs를 활용해 이동 경로 확인
     1) 각 노드별 depth를 저장하는 visit를 설정
     2) 이를 통해 노드에 depth를 저장

    **/

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class FarNode {

    private static ArrayList<Integer>[] adj;
    private static int[] visit;
    private static int depth = 0;
    private static int answer = 0;

    public static void main(String[] args) {
        int n = 6;
        int[][] egdes = {{3,6},{4,3},{3,2},{1,3},{1,2},{2,4},{5,2}};
        solution(n, egdes);
        System.out.println(answer);
    }

    public static int solution(int n, int[][] edge) {
        answer = 0;

        visit = new int[n + 1]; // 정점 갯수만큼의 방문 배열 만들기
        adj = new ArrayList[n+1]; // 인접리스트 생성

        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < edge.length; i++) { // 노드 연결
            adj[edge[i][0]].add(edge[i][1]);
            adj[edge[i][1]].add(edge[i][0]);
        }

        bfs(1, 1); // 시작 정점을 넣어줌

        for (int i = 1; i <= n; i++) { // 그래프 정점이 1부터 시작
            if(depth == visit[i]) answer++;
        }

        return answer;
    }

    public static void bfs(int start,int count) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        q.add(count);
        visit[start] = count;

        while (!q.isEmpty()) {
            int node = q.poll();
            int n = q.poll();

            if(depth<n) depth = n; // 가장 깊은 노드를 구함
            for (int i = 0; i < adj[node].size(); i++) {
                int next = adj[node].get(i); // 다음 정점을 방문함
                if(visit[next] != 0) continue; // 연결 간선이 없는 경우
                visit[next] = n + 1; // 방문할때마다 카운트 증가
                q.add(next); // 다음 방문할 연결된 정점
                q.add(n + 1);
            }
        }
    }
}

     - 목표
     베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 출력

     - 노래를 수록하는 기준
     1) 속한 노래가 많이 재생된 장르를 먼저 수록
     2) 장르 내에서 많이 재생된 노래를 먼저 수록
     3) 장르 내에서 재생 횟수가 같은 노래중에서 고유 번호가 낮은 노래를 먼저 수록

     - 배열 설명
     1) genres : 노래의 장르를 나타냄
     2) plays : 노래별 재생횟수를 나타냄

     - 해결과정
     1) play 횟수를 중첩해서 더해준다.
     2) 키 값만을 추출하여 리스트를 만들고, 리스트를 play횟수를 기준으로 정렬한다.
        ( 그 이유는 hashMap 은 순서가 없기 때문에 정렬할 수 없기 때문이다. )
     3) key값을 정렬한 리스트에서 제일 많은 횟수를 재생한 장르부터 장르별 제일 많은 횟수가 플레이된 인덱스,
        두번째로 많은 횟수가 플레이된 인덱스를 찾아 정답 배열에 순서대로 넣어준다.
     4) 이때, 두번째로 많은 횟수가 플레이된 인덱스는 존재하지 않을 수 있기 때문에 이를 처리
     5) 정답 리스트를 배열로 변환하여 반환
     
      * 단, 장르별 두 곡까지 수록곡에 담을 수 있음

[ 소스코드 ]

import java.util.*;

public class BestElbum {

    public static void main(String[] args) {
        String[] genres = {"classic", "pop", "classic", "classic", "pop"};
        int[] plays = {500, 600, 150, 800, 2500};
        String resultArr = Arrays.toString(solution(genres, plays));
        System.out.println(resultArr);
    }



    public static int[] solution(String[] genres, int[] plays) {
        ArrayList<String> genre = new ArrayList<>();
        Map<String, Integer> hashMap = new HashMap<>();
        ArrayList<Integer> list = new ArrayList<>();

        // 키 값이 이미 있으면 0을 반환하고 중첩되는 부분이 있으면 더해준다.
        for (int i = 0; i < genres.length; i++) {
            hashMap.put(genres[i], hashMap.getOrDefault(genres[i], 0) + plays[i]);
        }

        for (String key : hashMap.keySet()) {
            genre.add(key);
        }

        Collections.sort(genre, (o1, o2) -> hashMap.get(o2) - hashMap.get(o1));
        // key 값을 더해준 hashMap 에 대한 값을 내림차순으로 정렬한다.

        for (int i = 0; i < genre.size(); i++) {
            String g = genre.get(i); // 내림차순 정렬된 장르 리스트를 조회

            int max = 0; // 장르의 음악에서 재생 횟수가 가장 큰 인덱스를 찾는다.
            int firstIdx = -1;
            for (int j = 0; j < genres.length; j++) { // 기존의 장르 배열만큼 반복
                if(g.equals(genres[j]) && max < plays[j]){
                    // 장르 명이 동일하면 그 장르의 인덱스를 뽑아준다.
                    max = plays[j];
                    firstIdx = j;
                }
            }

            max = 0;
            int secondIdx = -1;
            for (int j = 0; j < genres.length; j++) {
                if (g.equals(genres[j]) && max < plays[j] && j != firstIdx) {
                    max = plays[j];
                    secondIdx = j;
                }
            }

            list.add(firstIdx);
            if (secondIdx >= 0) { // 장르에 대한 곡이 하나밖에 없는 경우는 -1로 남음
                list.add(secondIdx);
            }
        }

        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}

[ 문제 해설 ]

     - 문제
     begin 에서 target 으로 변환하는 가장 짧은 변환 과정을 찾아라

     - 조건
     1) 한 번에 한 개의 알파벳만 바꿀 수 있음
     2) words 에 있는 단어로만 변환할 수 있음

     - 알고리즘
     dfs

     - 해결 과정
     1) 한 글자 빼고 나머지가 같은 단어를 words 에서 찾는다.
     2) 찾은 단어를 visited = true 로 설정
     3) cnt 를 증가시키며 dfs 함수를 재귀 호출
     4) 모든 경우의 수를 보기 위해 check = false 로 재설정
     5) begin 과 target이 같은 경우 cnt를 answer에 대입하고 종료

[ 소스코드 ]

public class wordChange {

    static boolean[] check;
    static int answer = 0;

    public static void main(String[] args) {
        String begin = "hit";
        String target = "cog";
        String[] words = {"hot", "dot", "dog", "lot", "log", "cog"};

        answer = solution(begin, target, words);
        System.out.println(answer);

    }

    public static int solution(String begin, String target, String[] words) {
        check = new boolean[words.length];
        dfs(begin, target, words, 0);
        return answer;
    }

    public static void dfs(String begin, String target,String[] word, int cnt) {

        if (begin.equals(target)) { // 타겟과 시작 단어가 같으면 바로 리턴
            answer = cnt; // 두 글자 빼고 같은 경우 0 -> 1 -> 2로 증가함
            return;
        }

        for (int i = 0; i < word.length; i++) {
            int k = 0; // 같은 스펠링이 몇개인지 세기 위한 변수
            if(check[i]){ // 한번 지나간 단어는 패스
                continue;
            }
            for (int j = 0; j < begin.length(); j++) {
                if(begin.charAt(j) == word[i].charAt(j)){
                    // begin 과 word 의 각 단어 내부를 확인
                    /*
                    ex. hit, dog, ["hot", "dot", "dog", "lot", "log", "cog"] 일 때,
                    begin : hit
                    word[0] : hot
                    k : 2
                     */
                    k++;
                }
            }

            /*
            ex. k = 2 이므로,
            check[0] = true;
            dfs ( hot, cog, word, 1 );
            check[0] = false;

             */
            if (k == begin.length() - 1) { // 한글자 빼고 두 같은 경우만 보면 됨
                check[i] = true; // 지나간 자리는 true
                dfs(word[i], target, word, cnt + 1);
                check[i] = false;
            }
        }
    }


}

[ 해결 과정 ]

1) n개수만큼 불린 배열을 만들고 false 로 초기화

2) n만큼 for문을 돌리다가, check[i] 값이 false 인게 있으면 깊이 우선 탐색을 하는 dfs 메서드를 호출하고,

     네트워크 연결 개수를 ++ 해준다.

   * dfs 인자 : computer[][] , i , check[]

3) 전달받은 피라미터인 check[i] 값을 true로 바꿔준다.

4) computer[]의 길이만큼 반복문을 돈다.

5) 만약 아래 조건이 모두 만족하면, 재귀호출을 한다.

 - 자기 자신이 아니다. ( i != j )

 - check 배열 i 위치의 값이 false 이며, (check[i] == false )

 - computer 배열의 값이 1인 것 ( computer[i][j] == 0 )

6) 2번으로 돌아간다.

7) answer을 리턴한다.

[ 작성 코드 ]

public class network {

    /**
    - 컴퓨터 개수 n
    - 연결에 대한 정보가 담긴 2차원 배열 (computer)
     - 출력 : 네트워크 개수
    **/
    
    public static void main(String[] args) {
        int n = 3;
        int[][] computer1 = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
        int[][] computer2 = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};

        solution(n, computer1);
        solution(n, computer2);
    }

    public static int solution(int n, int[][] computers) {
        int answer = 0;

        boolean[] check = new boolean[computers.length];
        for (boolean i : check) {
            i = false;
        }

        for (int i = 0; i < computers.length; i++) {
            if (check[i] == false) {
                dfs(computers, i, check);
                answer++;
            }
        }
        return answer;
    }

    public static boolean[] dfs(int[][] computers, int n, boolean[] check) {
        // n : 방문 노드, computer : 네트워크 배열, check : 방문했는지 확인하는 배열
        check[n] = true;
        for (int i = 0; i < computers.length; i++) {
            if(n != i && computers[n][i] == 1 && check[i] == false){
                // n != i : 방문 할 노드의 인덱스와 방문한 노드가 같지 않음
                // computer[n][i] : 네트워크 배열에서 이제 방문할 배열 원소가 1인 경우
                // check[i] == false : 아직 방문 하지 않은 경우
                check = dfs(computers, i, check);
            }
        }
        return check;
    }
}

[ 해결 과정 ]

1. [ I : 뒤의 숫자를 넣어준다. ] 

2. [ D - 큐에 값을 삭제한다 ] => D 1 : 최대값 삭제, D -1 : 최솟값 삭제

( 두번째 입출력 과정 예제 )

// -45 653 
// -45 -642 45 97
// -45 -642 45
// -45 45
// -45 45 333
// 최솟값 : -45, 최대값 : 333

[ 풀이 방향 ]

1. string 배열을 split 해줌

2. 우선순위 큐 2개를 생성해 오름차순 내림차순으로 초기화시켜 사용

[ 우선순위 큐 개념 ]

https://tjdwns4537.tistory.com/126

[ 소스코드 ]

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class heapQueue {
    public static void main(String[] args) {
        String[] b = {"I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"};

        String resultArr = Arrays.toString(solution(b));
        System.out.println(resultArr);
    }

    public static int[] solution(String[] operations) {
        int[] answer = {0,0};

        PriorityQueue<Integer> priorityQueueMax = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> priorityQueueMin = new PriorityQueue<>();

        for (String operation : operations) {
            String[] splitOrder = operation.split(" ");

            if (splitOrder[0].equals("I")) {
                // 일단 두 큐에 뒤에 숫자를 넣어준다.
                priorityQueueMax.add(Integer.parseInt(splitOrder[1]));
                priorityQueueMin.add(Integer.parseInt(splitOrder[1]));
            }

            if (splitOrder[0].equals("D")) {
                if (!priorityQueueMax.isEmpty()) {
                    // 우선순위 큐가 비지 않을경우만 동작
                    if (splitOrder[1].equals("1")) {
                        // 1이면 최대값을 삭제한다.
                        int max = priorityQueueMax.peek();
                        priorityQueueMax.remove(max);
                        priorityQueueMin.remove(max);
                        // 삭제는 max,min 큐 둘다 해준다.
                    }
                    else {
                        // -1 이면 최솟값을 삭제한다.
                        int min = priorityQueueMin.peek();
                        priorityQueueMax.remove(min);
                        priorityQueueMin.remove(min);
                    }
                }
            }
        }

        if (!priorityQueueMax.isEmpty()) {
            answer[0] = priorityQueueMax.peek();
            answer[1] = priorityQueueMin.peek();
        }

        return answer;
    }
}

문제 : 정수 삼각형

- 출력: 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는다.
- 조건: 아래 칸으로 이동할 때에는 대각선 방향으로 한 칸 오른쪽 or 왼쪽으로만 이동 가능

- 해결 방법:
[ DFS or DP ] 이 중 DP를 활용해 중복해서 거쳐가는 곳의 값을 따로 저장해 사용합니다.

예를 들어서 설명해보면 위 그림에서 
 1) [ 8,1,0 ] 에서 1은 7+3 / 7+8 중 큰 값을 골라주면 됩니다.
 2) [ 2,7,4,4 ] 에서 
 		- 7은 (7+3+8) / (7+8+1) 중에 큰 값을 고르게 됩니다.
 		- 4는 (7+8+0) / (7+8+1) 중에 큰 값을 고르게 됩니다.
        
이렇게 계산은 맨 왼쪽값, 중간값, 맨 오른쪽 값을 나눠서 계산하게 됩니다.
그러면 저장될 배열인 dp[][] 에는 dp[i-1][j-1], dp[i-1][j] 중 큰 값 + 현재 선택된 값이 들어가게 됩니다. 


- 점화식 : dp[i][j] = MAX(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

[ 작성 코드 ]

public static int solution(int[][] triangle) {
        int answer = 0;

        int[][] dp = new int[triangle.length][triangle.length];
        dp[0][0] = triangle[0][0]; // 맨 위에 값을 넣어줌

        for (int i = 1; i < triangle.length; i++) {
            /* 맨 왼쪽 */
            dp[i][0] = dp[i - 1][0] + triangle[i][0];
            // 7+3, 7+8, 7+2 와 같이 맨 왼쪽 부분을 더하게 된다.
            // dp[1][0] (10) = dp[0][0] (7) + triangle[1][0] (3) -- 1
            // dp[2][0] (18) = dp[1][0] (10) + triangle[2][0] (8) -- 2

            /* 중간값 */
            for (int j = 1; j <= i; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
                // dp[1][1] = dp[0][1], dp[0][0] 중에 max + triangle[1][1] (8) -- 1
                // dp[2][1] = dp[1][1], dp[1][0] 중에 max + triangle[2][1] (1)
                // dp[2][2] = dp[1][2], dp[1][1] 중에 max + triangle[2][2] (0) -- 2
            }

            /* 맨 오른쪽 */
//            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
            // dp[1][1] (15) = dp[0][0] (7) + triangle[1][1] (8) -- 1
            // dp[2][2] (15) = dp[1][1] (중간값의 max 값) + triangle[2][2] (1) -- 2

            for (int w = 0; w < dp.length; w++) {
                for (int k = 0; k < dp.length; k++) {
                    System.out.print(dp[w][k] + " ");
                }
                System.out.println();
            }

            System.out.println("------------------------------");
        }

        for (int i = 0; i < triangle.length; i++) {
            answer = Math.max(answer, dp[triangle.length - 1][i]);
        }

        return answer;
}

* 위 DP 문제에는 중간 값 구할 때 맨 오른쪽 값도 같이 구해지기 때문에 맨 오른쪽 구하는 경우를 주석 처리 하였습니다.

문제 설명

import static java.util.Arrays.sort;

class Solution {

	/**
     - 문제
        마라톤 선수 이름이 담긴 배열 participant
        완주한 선수 이름이 담긴 배열 completion
        완주하지 못한 선수의 이름을 return 하는 함수 작성

     - 제한 사항
        1) 참여자수 : 1~100,000
        2) completion == participant + 1
        3) 참가자 이름
            - 알파벳 소문자 20글자 이하
            - 동명이인 있을 수 있음
     */
    public String solution(String[] participant, String[] completion) {
        String result = "";

        sort(participant);
        sort(completion);

        for (int i = 0; i < participant.length-1; i++) {
            if(!participant[i].equals(completion[i])){
                return participant[i];
            }
        }

        result = participant[participant.length-1];

        return result;
    }
}

[ 해결 방법 ]

1. 입력받은 배열을 정렬

2. 정렬하고 나면 두 가지 경우만 다루면 됩니다.

  - 참가자의 명단에 일치하지 않는 사람

  - 모두 비교하다가 참가자 명단의 끝에 나오는 사람

문제 설명

1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다.
2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.
3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.
6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다.
     만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.

[ 내가 작성한 코드 ]

import java.util.Locale;

public class 신규아이디추천 {
    /*
    - 해야할 일
    1) 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천

    - 아이디 규칙
    1) 길이: 3 ~ 15
    2) 사용가능 문자 : 소문자, 빼기, 밑줄, 마침표
    3) 단, 마침표는 시작과 끝에 사용 불가능, 연속으로 사용 불가능

    - 해야할 일의 처리 과정
    1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다.
    2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.
    3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
    4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
    5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.
    6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다.
         만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
    7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.
  능  */
    public static void main(String[] args) {
        String newId = 	"00.@cdefgTWhijklm...!_I',"	;
        String solution = solution(newId);

        System.out.println("res: " + solution);
    }

    public static String solution(String new_id) {
        String answer = "";
        String one = "";
        String two = "";
        String three = "";
        String four = "";
        String five = "";
        String six = "";
        String seven = "";

        // 1
        one = new_id.toLowerCase(Locale.ROOT);

        char[] ch = one.toCharArray();

        // 2
        for (int i = 0; i < ch.length; i++) {
            if(('a'<= ch[i] && ch[i] <= 'z') || ('0' <= ch[i] && ch[i] <= '9') ||
                    (ch[i]=='-') || (ch[i] =='_') || (ch[i] == '.')){
                two += ch[i];
            } else {
                continue;
            }
        }

        // 3
        three = two;
        while(three.contains("..")){
            three = three.replace("..", ".");
        }

        //4
        four = three;
        if (four.length() > 0 && four.charAt(0) == '.') {
            four = four.substring(1, four.length());
        }
        if (four.length() > 0 && four.charAt(four.length() - 1) == '.') {
            four = four.substring(0, four.length() - 1);
        }

        //5
        five = four;
        if (five.isEmpty()) {
            five = "a";
        }

        //6
        six = five;
        if(six.length() > 15){
            six = six.substring(0, 15);
            if(six.substring(six.length()-1,six.length()).equals(".")){
                six = six.substring(0,six.length()-1);
            }
        }

        //7
        seven = six;
        while(seven.length()<=2){
            ch = seven.toCharArray();
            seven += ch[ch.length-1];
        }

        answer = seven;
        return answer;
    }
}

저는 위와 같이 1단계부터 7단계까지 각 단계별로 풀이를 하였습니다.

하지만 다른 사람의 풀이를 보니 replaceAll 과 정규표현식의 중요성을 알 수 있었습니다.

replaceAll()

형식

String replaceAll(String regex, String replacement)

대상 문자열을 원하는 문자값으로 변환하는 함수입니다.

- 첫번째 매개변수는 변화하고자 하는 대상이 될 문자열

- 두번째 매개변수는 변환할 문자 값

그렇다면 replace 와 차이점이 무엇일까요??

이는 CharSequence 와 String 의 차이점입니다. CharSequence 에 정규 표현식이 사용 가능한것입니다.

정규 표현식 (정규식)

특정한 규칙을 가진 문자열의 집합을 표현하는데 사용되는 언어입니다.

주로 텍스트 편집기나 스크립트 언어에서 문자열의 검색과 치환을 위해 지원되고 있습니다.

정규표현식 문법은 다음과 같습니다.

자주 사용하는 정규 표현식

위를 응용한 예시를 살펴보겠습니다.

알파벳의 중복은 허용하고, 띄어쓰기 ( \s ) 는 한칸만 허용

@Pattern(regexp = "^[a-zA-Z]*\\s?[a-zA-Z]*$")

- [ ] * : 해당 알파벳이 0회 이상 반복 ( 있어도 되고, 없어도 됨 )

- \\s? : 공백이 1회 또는 0회만 있어야함

- [ ] * : 공백 뒤에 알파벳 0회 이상 반복을 한번 더 선언해줌으로써 공백 뒤에 알파벳 오는 경우를 대비

** 정규식 확인 페이지

https://www.regexplanet.com/advanced/java/index.html

프로그래머스

문제: 신고 결과 받기

[ 오답 풀이 ]

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class 신고결과받기 {
    /*
    - 문제 : 불량 이용자 신고 후 처리 결과를 메일로 발송하는 시스템 개발
    - 시스템 :
    1) 각 유저는 한 번에 한명의 유저 신고 가능
     + 신고 횟수 제한 없음
     + 서로 다른 유저 계속 신고 가능
     + 한 유저를 여러본 신고할 수 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됨

    2) k번 이상 신고된 유저는 게시판 이용 금지되며,
    그 유저에 대해 모든 유저에게 정지 사실 메일로 발송됨
     + 유저가 신고한 모든 내용을 취합해서 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송

    - 입력 값 :
    id_list : 유저 목록
    report : 신고 한 사람과 신고 당한 사람
    k : 정지되는 횟수

    - 신고 메일 양식 :
    "muzi"가 "frodo"를 신고했습니다.

    - 유저 목록 :
    "muzi", "frodo", "apeach", "neo"

    - 결과 :
    각 유저별 메일을 받은 횟수를 배열에 담은 것을 리턴

        // report 에 (띄어쓰기) 를 기준으로 split 해서 배열에 담음
        // 0번부터 짝수는 신고인, 홀수는 신고 당한사람
        // 신고인과 신고 당한사람 비교 문법 필요
        // k번 이상된 사람 있으면 cnt 의 해당하는 인덱스에 카운터가 증가됨

    */
    public static void main(String[] args) {
        String[] id_list = {"muzi", "frodo", "apeach", "neo"};
        String[] report = {"muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"};
        String[] report2 = {"ryan con", "ryan con", "ryan con", "ryan con"};
        int k = 2;
        int[] solution = solution(id_list, report2, k);
        for (int i = 0; i < solution.length; i++) {
            System.out.println(solution[i] + " ");
        }

    }
    public static int[] solution(String[] id_list, String[] report, int k) {
        int[] answer = new int[id_list.length];

        HashMap<String, String> map = new HashMap<>();
        String[][] SplitString = new String[report.length][2];

        int[] cnt = new int[id_list.length];
        
        for (int i = 0; i < cnt.length; i++) {
            cnt[i] = 0;
        }
        for (int i = 0; i < report.length; i++) {
            SplitString[i] = report[i].split(" ");
        }

        for (int i = 0; i < SplitString.length; i++) {
            for (int w = 0; w < id_list.length; w++) {
                // > 신고한사람, 당한사람이 한번이라도 있으면 map 에 담기기 때문에 map 을 다시 조회해서 해당하는 인원이 나오면 신고 카운트가 증가되지 않음
                Iterator<Map.Entry<String, String>> entries = map.entrySet().iterator();
                while (entries.hasNext()) {
                    Map.Entry<String, String> entry = entries.next();
                    if (entry.getKey().equals(SplitString[i][0]) && entry.getValue().equals(SplitString[i][1])) {
                        System.out.println(entry.getKey() + "  " + entry.getValue());
                        continue;
                    }
                    if(entry.getKey().equals(SplitString[i][0])){
                        answer[w] = answer[w] + 1;
                    }
                }
                // <
                if(SplitString[i][1].equals(id_list[w])){
                    map.put(SplitString[i][0],SplitString[i][1]);
                    cnt[w] = cnt[w]+1;
                }
            }
        }

        return cnt;
    }
}

해결 방식의 문제점

문제를 잘못 이해한게 가장 큰 실수였습니다.

id_list 별 신고 당한 횟수로 이해를 하고 다음과 같이 코드를 작성하였습니다.

저렇게 작성하게 될 경우, 신고한 사람의 기준에서 카운트를 세는 과정을 구할 수가 없습니다.

그래서 저 방식을 그대로 유지한 채 코드를 수정해보려 했지만 해결 방법을 찾지 못했습니다.

다른 사람들의 코드를 보니 HashSet 을 이용하는 것으로 보입니다.

그래서 다시 풀이를 작성해보겠습니다.

public static int[] solution(String[] id_list, String[] report, int k){
        int[] answer = new int[id_list.length];

        /*
        HashMap<String,HashSet<String>> DeclaratedMap
        -> 중복 체크

        HashMap<String,Integer> DeclarateMap
        -> 키값 : 신고당한사람, value값 : 카운트 횟수

        HashSet<String> repSet
        -> report 를 리스트로 변환한 후 hashSet 의 요소로 넣어줌
         */

        HashMap<String, HashSet<String>> DeclaratedMap = new HashMap<>();
        HashMap<String, Integer> DeclarateCountMap = new HashMap<>();
        HashSet<String> DeclarateSet = new HashSet<>(Arrays.asList(report));

        for (String DeclareInfo : DeclarateSet) {
            String Declarater = DeclareInfo.split(" ")[0];
            String Declarated = DeclareInfo.split(" ")[1];

            // HashSet 에 신고 당한 대상을 담아준다.
            HashSet<String> temp = new HashSet<>();
            temp.add(Declarated);

            // 만약 신고 당한 대상의 map에 신고 한 사람 이름의 키 값이 존재 하지 않으면 추가해준다.
            DeclaratedMap.putIfAbsent(Declarater, temp);

            // 신고 당한 대상의 map 에 신고한 사람의 키에 대한 HashSet에 신고당한 대상의 이름을 넣어준다.
            DeclaratedMap.get(Declarater).add(Declarated);

            DeclarateCountMap.put(Declarated, DeclarateCountMap.getOrDefault(Declarated, 0) + 1);
        }

        //
        for (String Declared : DeclarateCountMap.keySet()) {
            int DeclaredCount = DeclarateCountMap.get(Declared);
            if (DeclaredCount >= k) {
                for (int i = 0; i < id_list.length; i++) {
                    if (DeclaratedMap.containsKey(id_list[i]) && DeclaratedMap.get(id_list[i]).contains(Declared)) {
                        answer[i]++;
                    }
                }
            }
        }

        return answer;
    }

코드참조 : https://velog.io/@ckr3453/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%8B%A0%EA%B3%A0-%EA%B2%B0%EA%B3%BC-%EB%B0%9B%EA%B8%B0-java

네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다.

다음은 숫자의 일부 자릿수를 영단어로 바꾸는 예시입니다.

• 1478 → "one4seveneight"
• 234567 → "23four5six7"
• 10203 → "1zerotwozero3"

이렇게 숫자의 일부 자릿수가 영단어로 바뀌어졌거나, 혹은 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어집니다. s가 의미하는 원래 숫자를 return 하도록 solution 함수를 완성해주세요.

참고로 각 숫자에 대응되는 영단어는 다음 표와 같습니다.

숫자영단어

제한사항

• 1 ≤ s의 길이 ≤ 50
• s가 "zero" 또는 "0"으로 시작하는 경우는 주어지지 않습니다.
• return 값이 1 이상 2,000,000,000 이하의 정수가 되는 올바른 입력만 s로 주어집니다.

[ 나의 풀이 ]

import java.util.HashMap;
import java.util.Map;

public class NumberAndWord {
    public static void main(String[] args) {
        /*
        - 숫자놀이
        : 네오 -> 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면
        프로도는 원래 숫자를 찾는 게임

        //when
        네오가 프로도에게 일부 자릿수를 영단어로 바꾼 카드를 건네줌

        //then
        프로도는 원래 숫자를 찾음

        // how
        1. hashMap 에 0 ~ 9 까지 저장
        2. 입력받은 문자열을 char 형으로 변환
        3. 변환된 char 형이 문자일 경우 하나씩 합치면서 hash value 값과 동일한지 비교
         ( 숫자일 경우 결과 값에 바로 합쳐줌 )
        4. 비교 후 같으면 해당 값을 hashMap 가 비교해서 같은 값을 가지는 key 값을
           결과 값에 합쳐줌
        */
        int res = solution("one4seveneight");
        System.out.println(res);
    }

    public static int solution(String s){
        int answer = 0;
        String temp = "";


        HashMap<Integer, String> hashMap = new HashMap<>();
        hashMap.put(0, "zero");
        hashMap.put(1, "one");
        hashMap.put(2, "two");
        hashMap.put(3, "three");
        hashMap.put(4, "four");
        hashMap.put(5, "five");
        hashMap.put(6, "six");
        hashMap.put(7, "seven");
        hashMap.put(8, "eight");
        hashMap.put(9, "nine");

        //when
        char[] ch = s.toCharArray();

        for (int i = 0; i < ch.length; i++) {
            int k = Character.getNumericValue(ch[i]);
            if(0 <= k && k <= 9){
                if(answer == 0){
                    answer += k;
                }
                else{
                    answer = (answer * 10) + k;
                }
            }
            else {
                temp += ch[i];
                for (Map.Entry<Integer, String> entry : hashMap.entrySet()) {
                    if (entry.getValue().equals(temp)) {
                        if (answer == 0) {
                            answer += entry.getKey();
                        } else {
                            answer = (answer * 10) + entry.getKey();
                        }
                        temp = "";
                    }
                }
            }
        }

        return answer;
    }
}

다른 사람의 코드를 보니 너무 깔끔하고 짧게 구현해놔서 제 코드를 다시 보니 부끄럽네요..

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        StringBuilder sb = new StringBuilder("");
        int len = s.length();
        String[] digits = {"0","1","2","3","4","5","6","7","8","9"};
        String[] alphabets = {"zero","one","two","three","four","five","six","seven","eight","nine"};

        for(int i=0; i<10; i++){
            s = s.replaceAll(alphabets[i],digits[i]);
        }

        return Integer.parseInt(s);
    }
}

모르겠는 메소드와 타입이 있어서 분석 먼저 해보겠습니다.

StringBuilder

변경 가능한 문자열을 만들어줍니다.

아래와 같이 String 형을 그냥 더하게 된다면 메모리 할당과 해제를 시키는 면에서 비효율적인 코드가 완성됩니다.

String a = "aa";
String b = "bb";
String c = a+b;

자바에서 String 형은 변경이 불가능합니다.

[ 문자열이 더해지는 과정 ]

1) 하나의 문자열을 다른 문자열과 연결하면 새 문자열이 생성

2) 이전 문자열은 가비지 컬렉터로 들어갑니다.

만약, 이러한 행위를 100만번을 하게 된다면 많은 메모리를 잡아 먹게 됩니다.

이 경우 사용하는게 StringBuilder 입니다.

[ 사용 방법 ]

1) StringBuilder 객체 생성

2) append 로 더해줌

3) toString() 으로 할당

StringBuilder sb = new StringBuilder();
sb.append("aa").append("bb");
String c = sb.toString();

replaceAll

• replace ( 변환하고자 하는 대상 문자열 , 변환할 문자 )

String str = "aaaa";
System.out.prinln(str.replace("aa","bbb");

// 결과값 : bbbbbb

• replaceAll ( 변환하고자 하는 대상 문자열, 변환할 문자 )

String str = "jajavava";
System.out.println("java","cool");

// jacoolva 출력

이렇게 보면 차이가 없어 보이지만 중요한 차이점은 지금부터 입니다.

String random = "AbCdGgZz";
System.out.println(random.replaceAll("[bdz]",Y);

// AYCYGgZY 출력

b,d,z 라는 값을 모두 Y로 바꿔주겠다는 의미입니다.

그러면 위의 코드가 이해가 됩니다.

[ 동작과정 ]

1. 알파벳 배열의 값들이 옴

2. 해당 알파벳 배열 값을 찾은 인덱스와 동일한 위치의 digit 배열로 대체

ㅇ 폰켓몬 문제 :
n 마리의 폰켓몬 중에 n/2 마리를 가질 수 있음.
각 폰켓몬에는 종류에 따라 번호가 붙어있음 -> 같은 종류의 폰켓몬은 같은 번호를 가짐.
ex. 4마리의 폰켓몬 : [3 , 1 , 2 , 3] 이 될 수 있는 거임. 따라서 위 종류에서 1,4번 폰켓몬을 선택하는 것이 아닌 이상
    최대  2 개 종류의 폰켓몬을 가질 수 있음.


- 원하는 결과
: n 마리 중 N/2 마리를 선택하는데 최대 종류를 가질 수 있는 수를 찾는 것


- 주어진 변수
1) nums : n 마리 폰켓몬의 종류 번호가 담긴 배열


- 제한사항
1) nums 는 1차원 배열
2) nums 의 길이는 1 ~ 10,000 중에서 짝수이다.
3) 폰켓몬의 종류 번호는 1 ~ 200,000
4) 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러가지라도 그 최대값만 return 하면 됨




- ArrayList 를 사용
1) list.contains()  :  list에 인자로 전달받은 객체가 있는지 없는 확인

2) List<Integer> 을 통해 정수 리스트를 생성

3) nums[0] 의 시작 주소에 담긴 데이터를 리스트에 넣어줌

4) list.size() 와 nums.length 를 통해 크기 비교 후 결과값을 반환해줌

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]); // nums 배열의 주소를 list 연결리스트로 복사해줌

        for(int i=1; i<nums.length; i++){
            if(!list.contains(nums[i])){
                list.add(nums[i]);
            }
        }

        answer = list.size() > nums.length/2 ? nums.length/2 : list.size();

        return answer;
    }
}

ㅇ 문제
: 도둑이 들어 일부 학생이 체육복을 도난 당함 -> 여벌 체육복이 있는 학생이 이들에게 빌려줌.
학생들의 번호는 체격 순으로 매겨져 있음 -> 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있음.
이 문제의 핵심은 체육복이 없으면 수업을 못 듣기때문에 최대한 많은 학생이 빌릴 수 있도록 하는 것.


- 주어지는 변수
1) n : 전체 학생의 수
2) lost : 체육복을 도난당한 학생들의 번호가 담긴 배열 ( 앞 뒤 번호 확인 필요 )
3) reserve : 여벌의 체육복을 가진 학생들 ( lost 와 비교 필요 )


- 결과값 : 체육수업을 들을 수 있는 학생의 최댓값

   ex. 2 ,4 가 lost 이고 reverse 가 3 이면 최대는 4 ( 1,2,3,5 ) -> return 4


- 제한사항
1) 2 ~ 30 명
2) 도난 당한 학생의 수 : 1 ~ n 명 ( 중복되는 번호 없음 )
3) 여벌 체육복을 가져온 학생의 수 : 1 ~ n 명 ( 중복되는 번호 없음 ) 
4) 여벌 체육복을 가져온 학생이 체육복을 도난 당했을 수도 있습니다. 이때, 이 학생은 체육복을 하나만 도난당했다고 가정함.
   그러면 이 학생은 더 이상 체육복을 빌려줄 수 없음.

import java.util.Arrays;
class Solution {
    public int solution(int n, int[] lost, int[] reserve){
        int answer = n - lost.length;
        Arrays.sort(lost);
        Arrays.sort(reserve);

        for(int i=0; i<lost.length; i++){
            for(int j =0; j<reserve.length; j++){
                if(lost[i] == reserve[j]){
                    answer++;
                    lost[i] = -1;
                    reserve[j] = -1;
                    break;
                }
            }
        }

        for(int i=0; i<lost.length; i++){
            for(int j =0; j<reserve.length; j++){
                if(lost[i]-1 == reserve[j] || lost[i]+1 == reserve[j]){
                    answer++;
                    reserve[j] = -1;
                    break;
                }
            }
        }

        return answer;
    }
}

* Arrays 패키지를 사용안하니 마지막 문제가 풀리지 않았다. 아마 정렬되지 않은 배열이 예제로 있었기 때문이라고 생각한다.

ㅇ 로또의 최고 순위와 최저 순위

1위 : 6개 모두 일치
2위 : 5개 일치
3위 : 4개 일치
4위 : 3개 일치
5위 : 2개 일치
6위 : 그 외



- 해결해야 하는 것

1) 로또 번호가 낙서되어 알아 볼 수 없음
 -> 예상해서 확률을 만들어야함
 -> 알아볼 수 없는 번호를 0으로 표기


2) 당첨 번호 발표 후 자신이 구매했던 로또의 최고 순위와 최저 순위를 알아내야 함
  -> 순서는 상관없이 번호만 일치하면 됨




- 주어진 변수

1) lottos : 구매한 로또 번호를 담은 배열

2) win_nums : 당첨 번호를 담은 배열




- 제한사항

1) lottos 의 길이는 6 인 정수 배열
2) lottos 의 모든 원소는 0 ~ 45 정수
3) win_num 의 길이는 6 인 정수배열
4) win_num 의 모든 원소는 1 ~ 45 정수


- 결과 값
: 당첨 가능한 최고 순위와 최저 순위가 담긴 배열




- 해결 과정
1) 0 ~ 45 중 랜덤한 숫자를 lottos 에 입력받음
2) 1 ~ 45 중 랜덤한 숫자를 win_nums 에 입력받음
3) 0에 숫자를 넣었을때 win_nums 배열 수 중 최대 갯수가 중복되게 하는 수와
   중복이 최대가 되는 수를 찾는다.
4) 1~6위 중 최대와 최소를 찾는다.

class Solution{
	public int[] solution(int[] lottos,int[] win_nums){
		int cntR = 0;
        int cntZ = 0;

        for(int i : lottos){
            for(int j : win_nums){
                if(i==j) cntR++;
            }
            if(i == 0) cntZ++;
        }
        int upRes = 7 - (cntR + cntZ) > 6 ? 6 : 7 - (cntR + cntZ);

        int downRes = 7 - cntR > 6 ? 6 : 7 - cntR;

        int[] answer = {upRes,downRes};

        return answer;
    }
}

* 어려웠다. 다시 풀어보자