※문제 풀이의 경우 블로그 등에 작성이 가능하다는 답변을 확인하고 글을 작성했습니다.

혹시 정책이 변경되는 경우 알려주시면 해당 글을 비공개 처리하도록 하겠습니다.

감사합니다.

※ 확인한 글의 출처 : https://career.programmers.co.kr/questions/34688

Q1

package com.company;

public class Quiz1 {
    static public void main(String[] args) {
        String X1 = "100";
        String Y1 = "2345";
        String X2 = "100";
        String Y2 = "203045";
        String X3 = "100";
        String Y3 = "123450";
        String X4 = "12321";
        String Y4 = "42531";
        String X5 = "5525";
        String Y5 = "1255";
        String X6 = "55251232131231231231231231";
        String Y6 = "1255123123123123123123123123123123123";

        System.out.println(solution(X1, Y1).equals("-1"));
        System.out.println(solution(X2, Y2).equals("0"));
        System.out.println(solution(X3, Y3).equals("10"));
        System.out.println(solution(X4, Y4).equals("321"));
        System.out.println(solution(X5, Y5).equals("552"));
        System.out.println(solution(X6, Y6));
    }

    static public String solution(String X, String Y) {
        // StringBuilder 를 사용하면 속도가 빠르다. 그냥 문자열 붙이기를 사용할 경우 시간초과가 된다.
        StringBuilder answer = new StringBuilder();
        // x와 y 문자열의 숫자들을 보관할 Array 그리고 공통의 짝을 보관할 Array
        int[] xNumberArray = new int[10];
        int[] yNumberArray = new int[10];
        int[] commonNumberArray = new int[10];
        // 공통되는 숫자가 몇개인지 셀 변수
        int commonNumberCount = 0;

        //String X를 분해해서 xNumberArray에 채우기 , 해당 문자열의 숫자를 Index 로 바꿔서 Array 의 값을 ++
        for (int i = 0; i < X.length(); i++) {
            xNumberArray[(X.charAt(i) - '0')]++;
        }
        //String Y를 분해해서 xNumberArray에 채우기 , 해당 문자열의 숫자를 Index 로 바꿔서 Array 의 값을 ++
        for (int i = 0; i < Y.length(); i++) {
            yNumberArray[(Y.charAt(i) - '0')]++;
        }
        //중복되는 요소들 확인하기
        for (int i = 0; i < 10; i++) {
            while (xNumberArray[i] != 0 && yNumberArray[i] != 0){
                commonNumberCount++; // 공통되는 수가 있을 때마다 ++
                commonNumberArray[i]++;
                xNumberArray[i]--;
                yNumberArray[i]--;
            }
        }

        // 공통되는 짝이 없는 경우에는 -1 을 리턴
        if(commonNumberCount == 0) {
            return "-1";
        }

        //배열 끝에서부터 값이 있는지 확인해서 큰 자리수 만들기
        while (commonNumberCount > 0) {
            for (int i = 9; i >= 0; i--) {
                //배열의 값이 있는 경우 해당 숫자를 써야하므로 StringBuilder를 사용하여 answer 문자열에 붙인다.
                if(commonNumberArray[i] != 0){
                    answer.append(String.valueOf(i));
                    commonNumberArray[i] --; // 해당 숫자를 사용했으므로 해당 배열의 값을 1만큼 줄인다.
                    break;
                }
            }
            // 공통되는 숫자의 카운트 -1 시킨다.
            commonNumberCount--;
        }

        //문자열이 0으로만 구성되어 있는 경우 "0"으로 split을 하면 공백 Array가 나온다. => 사이즈가 0이라면 "0"을 리턴
        if(answer.toString().split("0").length == 0){
            return "0";
        }

        return answer.toString();
    }
}

Q2

package com.company;

import java.util.HashMap;

public class Quiz2 {

    static public void main(String[] args) {
        String[] quizWant1 = {"banana", "apple", "rice", "pork", "pot"};
        int[] quizNum1 = {3, 2, 2, 2, 1};
        String[] quizDiscount1 = {"chicken", "apple", "apple", "banana", "rice", "apple", "pork", "banana", "pork", "rice", "pot", "banana", "apple", "banana"};

        String[] quizWant2 = {"apple"};
        int[] quizNum2 = {10};
        String[] quizDiscount2 = {"banana", "banana", "banana", "banana", "banana", "banana", "banana", "banana", "banana", "banana"};

        System.out.println(solution(quizWant1, quizNum1, quizDiscount1) == 3);
        System.out.println(solution(quizWant2, quizNum2, quizDiscount2) == 0);
    }


    static public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;

        //HashMap 생성
        HashMap<String, Integer> wantHashMap = new HashMap<String, Integer>();

        //hashMap에 필요한 물품의 수량을 저장
        for (int i = 0; i < want.length; i++) {
            wantHashMap.put(want[i], number[i]);
        }

        //discount 를 for문으로 10개씩만 돌면서 내가 원하는 수량만큼 있는지 비교하기.
        for (int i = 0; i <= discount.length - 10; i++) {
            HashMap<String, Integer> discountHashMap = new HashMap<String, Integer>();
            int tempCount = 0;

            for (int j = i; j < i + 10; j++) {
                discountHashMap.put(discount[j], discountHashMap.getOrDefault(discount[j], 0) + 1);
            }

            for (String st : want ) {
                if(wantHashMap.get(st) == discountHashMap.get(st)){
                    tempCount++;
                }else{
                    break;
                }
            }

            if (tempCount == want.length)
                answer++;
        }

        return answer;
    }
}

Q3

package com.company;

import java.util.Stack;

public class Quiz3 {
    static public void main(String[] args) {
        int[] quiz1 = { 4,3,1,2,5 };
        int[] quiz2 = { 5,4,3,2,1 };

        System.out.println(solution(quiz1) == 2);
        System.out.println(solution(quiz2) == 5);
    }

    static public int solution(int[] order) {
        int answer = 0;
        Stack<Integer> stack = new Stack<Integer>();
        // order 길이만큼이 box의 총량
        int boxTotalNum = order.length;
        //boxIndex 는 1번 박스부터 시작
        int boxIndex = 1;
        //현재까지 처리된 order 박스 Index
        int orderIndex = 0;

        while (true){
            // order[orderIndex] 와 boxIndex 가 다른 상황인데 order[orderIndex] 가 boxIndex 보다 크다면,
            // boxIndex 를 stack에 집어 넣는 것으로 order[orderIndex] 를 맞출 수 있으므로 stack 에 boxIndex 를 Push 한다.
            // 그런데 만약 order[orderIndex] 가 boxIndex 보다 작다면 일단 stack 에 들어있는 것을 확인하고
            // stack 에서도 해당 값이 없다면 box 를 stack 에 집어 집어넣어도 쓸모가 없다.
            if (order[orderIndex] != boxIndex && order[orderIndex] > boxIndex) {
                stack.push(boxIndex);
                boxIndex++;
            }
            // boxIndex 와 order[orderIndex] 가 같으므로 answer 를 한개 올리고 boxIndex 를 올린다.
            // orderIndex 도 올려야 하는데 그냥 ++ 하면은 OutOfRangeError 가 뜨므로 조건을 걸었다.
            else if (order[orderIndex] == boxIndex) {
                boxIndex++;
                answer++;
                if(orderIndex + 1 != boxTotalNum)
                    orderIndex++;
            }
            // boxIndex 로 order[orderIndex]를 맞출 수 없을 때 stack 을 확인해야 하며
            // stack 을 사용할때는 Empty 인지 확인 후에 사용해야함
            // 그리고 peek 를 사용해서 일단 최상단 값을 확인하고 맞으면 pop 을 해준다.
            // answer 와 orderIndex 관련은 바로 위에 와 같다.
            else if ( !stack.isEmpty() && stack.peek() == order[orderIndex]) {
                stack.pop();
                answer++;
                if(orderIndex + 1 != boxTotalNum)
                    orderIndex++;
            }
            // 위의 3조건에 아무것도 해당하지 않는 경우에는 while 을 지속하는 의미가 없으므로 break 로 빠져나온다.
            else {
                break;
            }
        }

        return answer;
    }
}

Q4

package com.company;

import java.util.Arrays;

public class Quiz4 {
    static public void main(String[] args) {
        int[][] quiz1 = {
                {0, 1, 0, 0, 0},
                {1, 0, 1, 0, 1},
                {0, 1, 1, 1, 0},
                {1, 0, 1, 1, 0},
                {0, 1, 0, 1, 0}
        };
        int[][] target1 = {
                {0, 0, 0, 1, 1},
                {0, 0, 0, 0, 1},
                {0, 0, 1, 0, 1},
                {0, 0, 0, 1, 0},
                {0, 0, 0, 0, 1}
        };

        int[][] quiz2 = {
                {0, 0, 0},
                {0, 0, 0},
                {0, 0, 0}
        };
        int[][] target2 = {
                {1, 0, 1},
                {0, 0, 0},
                {0, 0, 0}
        };

        int[][] quiz3 = {
                {0,0,0,0,0,0,1,1,1,0},
        };
        int[][] target3 = {
                {1,0,1,0,1,0,0,0,0,0},
        };

//        System.out.println(solution(quiz1, target1) == 5);
//        System.out.println(solution(quiz2, target2) == -1);
        System.out.println(solution(quiz3, target3));
    }

    static int[][] startBoard;

    static public int solution ( int[][] beginning, int[][] target){
        int[] answer = new int[2];
        int[] answer1 = new int[2];

        int whileCount = 0;
        int i = 0;
        //행 , 열 중에 어떤 것을 먼저 순회할지 정할 변수
        int odd = 0;

        //사각형의 왼쪽면 , 윗쪽면 순회하는 Loop
        for (int j = 0; j < answer.length; j++) {
            odd = j;
            whileCount = 0;

            startBoard = new int[beginning.length][beginning[0].length];
            for(int jj=0; jj<startBoard.length; jj++){
                System.arraycopy(beginning[jj], 0, startBoard[jj], 0, beginning[0].length);
            }

            //2개의 사각형이 일치할떄까지 While문 순회
            while(!Arrays.deepEquals(startBoard, target)){
                if(odd == 0){
                    //row 비교
                    for (i = 0; i < beginning.length; i++) {
                        if(startBoard[i][0] != target[i][0]){
                            reverseRow(i);
                            answer[j]++;
                        }
                    }
                    odd = 1;
                }else{
                    //column 비교
                    for (i = 0; i < beginning[0].length; i++) {
                        if(startBoard[0][i] != target[0][i]){
                            reverseColumn(i);
                            answer[j]++;
                        }
                    }
                    odd = 0;
                }

                whileCount ++;

                if(whileCount > 20){
                    System.out.println("해당 알고리즘은 실패 ㅠㅠ");
                    answer[j] = -1;
                    break;
                }
            }
        }

        //사각형의 오른쪽면 , 아래쪽면 순회하는 Loop
        for (int j = 0; j < answer1.length; j++) {
            odd = j;
            whileCount = 0;

            startBoard = new int[beginning.length][beginning[0].length];
            for(int jj=0; jj<startBoard.length; jj++){
                System.arraycopy(beginning[jj], 0, startBoard[jj], 0, beginning[0].length);
            }

            //2개의 사각형이 일치할떄까지 While문 순회
            while(!Arrays.deepEquals(startBoard, target)){
                if(odd == 0){
                    //row 비교
                    for (i = 0; i < beginning.length; i++) {
                        if(startBoard[i][beginning[0].length - 1] != target[i][beginning[0].length - 1]){
                            reverseRow(i);
                            answer1[j]++;
                        }
                    }
                    odd = 1;
                }else{
                    //column 비교
                    for (i = 0; i < beginning[0].length; i++) {
                        if(startBoard[beginning.length - 1][i] != target[beginning.length - 1][i]){
                            reverseColumn(i);
                            answer1[j]++;
                        }
                    }
                    odd = 0;
                }

                whileCount ++;

                if(whileCount > 20){
                    System.out.println("해당 알고리즘은 실패 ㅠㅠ");
                    answer1[j] = -1;
                    break;
                }
            }
        }

        //사각형을 완전 순회 하면서 최솟값을 찾아야함
        //1. 왼쪽 면 순회 + 윗쪽 면 순회 + 오른쪽 면 순회 + 아래쪽 면 순회
        //2. 윗쪽 면 순회 + 왼쪽 면 순회 + 오른쪽 면 순회 + 아래쪽 면 순회
        //3. 왼쪽 면 순회 + 윗쪽 면 순회 + 아래쪽 면 순회 + 오른쪽 면 순회
        //4. 윗쪽 면 순회 + 왼쪽 면 순회 + 아래쪽 면 순회 + 오른쪽 면 순회

        //위에서 나온 4가지 케이스 중에서 가장 최솟값을 return 해주면 된다.
        return Math.min(Math.min(answer[0], answer[1]), Math.min(answer1[0], answer1[1]));
    }

    //가로줄 뒤집기 메서드
    private static void reverseRow(int row) {
        for (int i = 0; i < startBoard[row].length; i++) {
            startBoard[row][i] = startBoard[row][i] ^ 1;
        }
    }

    //세로줄 뒤집기 메서드
    private static void reverseColumn(int column) {
        for (int i = 0; i < startBoard.length; i++) {
            startBoard[i][column] = startBoard[i][column] ^ 1;
        }
    }
}