관리 메뉴

KoreanFoodie's Study

SW 역량테스트 - [모의 SW 역량테스트] 보호 필름 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

SW 역량테스트 - [모의 SW 역량테스트] 보호 필름 문제 풀이/해답/코드 (C++ / JAVA)

hashnut 2020. 9. 29. 11:18


SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 


문제 링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

해답 코드 : 

 

// java

import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;
import java.io.FileInputStream;

/*
   사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
   이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
 */

class Pallet {
    int r;
    int c;

    Pallet(int row, int color) {
        r = row;
        c = color;
    }
}

class Solution
{
    static int D, W;
    static int[][] map;
    static int K;
    static int min_shot;
    static boolean[] alloc;


    // check it passes the K-test
    static boolean checker(int[][] my_map) {


        for (int j = 0; j < W; j++) {

            int series = 1;
            int sum = 0;

            for (int i = 0; i < D-1; i++) {
                if (my_map[i][j] == my_map[i+1][j]) {
                    series++;
                    sum = Math.max(sum, series);
                } else {
                    series = 1;
                }
            }

            sum = Math.max(1, sum);

            if (sum < K) return false;
        }

        return true;
    }

    // copy map (to clear the map state)
    static void map_copy(int[][]temp, int[][] original) {

        for (int i = 0; i < D; i++) {
            for (int j = 0; j < W; j++) {
                temp[i][j] = original[i][j];
            }
        }
    }

    // allocate the number of rows and positions
    static void allocate(int total, int cur_len, int last) {

        // if minimal is found, just return
        if (min_shot != 9999) return;

        // terminator -> if allocation is over, call divide()
        if (total == cur_len) {

            int[] p = new int[total];

            divide(total, p, 0);
            return;
        }


        // execution (for loop)
        for (int i = last; i < D; i++) {

            alloc[i] = true;

            allocate(total, cur_len+1, i+1);

            alloc[i] = false;
        }


    }

    // divide allocation to A or B (2 ^ length)
    static void divide(int total, int[] p, int last) {

        // terminator -> if division is over, call checker
        if (total == last) {
            paint(total, p);
            return;
        }

        // executor

        // Try A
        p[last] = 0;
        divide(total, p, last+1);

        // Try B
        p[last] = 1;
        divide(total, p, last+1);

    }

    static void paint(int total, int[] p) {
        int[][] temp = new int[D][W];

        map_copy(temp, map);

        int p_cnt = 0;

        // paint temp
        for (int i = 0; i < D; i++) {

            if (!alloc[i]) continue;

            int color = p[p_cnt++];

            for (int j = 0; j < W; j++) {

                temp[i][j] = color;
            }
        }

        // check temp -> call checker
        if (checker(temp)) min_shot = Math.min(min_shot, total);



    }

    public static void main(String args[]) throws Exception
    {
		/*
		   아래의 메소드 호출은 앞으로 표준 입력(키보드) 대신 input.txt 파일로부터 읽어오겠다는 의미의 코드입니다.
		   여러분이 작성한 코드를 테스트 할 때, 편의를 위해서 input.txt에 입력을 저장한 후,
		   이 코드를 프로그램의 처음 부분에 추가하면 이후 입력을 수행할 때 표준 입력 대신 파일로부터 입력을 받아올 수 있습니다.
		   따라서 테스트를 수행할 때에는 아래 주석을 지우고 이 메소드를 사용하셔도 좋습니다.
		   단, 채점을 위해 코드를 제출하실 때에는 반드시 이 메소드를 지우거나 주석 처리 하셔야 합니다.
		 */
        //System.setIn(new FileInputStream("sample_input.txt"));

		/*
		   표준입력 System.in 으로부터 스캐너를 만들어 데이터를 읽어옵니다.
		 */
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
		/*
		   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
		*/

        for(int test_case = 1; test_case <= T; test_case++)
        {

            D = sc.nextInt();
            W = sc.nextInt();
            K = sc.nextInt();
            map = new int[D][W];

            min_shot = 9999;

            for (int i = 0; i < D; i++) {
                for (int j = 0; j < W; j++) {
                    map[i][j] = sc.nextInt();
                }
            }


            for (int i = 0; i < K; i++) {
                alloc = new boolean[D];
                allocate(i, 0, 0);
            }

            // min_shot is bigger than K-1, then the answer is K
            if (min_shot > K) min_shot = K;

            System.out.println("#" + test_case + " " + min_shot);

        }
    }
}

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제

 
0 Comments
댓글쓰기 폼