SW 역량 테스트 기출 문제(뱀, 시험 감독)

[뱀 _ 3190]

 

 

* 조건

1. 뱀은 몸 길이를 한칸 늘려 위치시킨다

2. 이동한 칸에 사과가 존재한다면 사과를 없애고 몸의 길이가 늘어난다(해당 칸을 흡수)

3. 사과가 없다면 꼬리를 없앤다(몸의 길이는 변하지 않음)

4. 사과 좌표를 위해 size = n+1로 설정

5. 뱀의 시작 위치는 (1,1) / 처음엔 오른쪽(2차원 배열 시점)으로 전진

6. 좌우 방향의 개념은 뱀의 시선에서 적용해야함

7. 벽 또는 자기자신의 몸통에 부딪히면 종료

 

* 알고리즘

• 명령에 맞게끔 방향을 조작해야함 : 시뮬레이션

 

* 로직(Logic)

• 우선 2차원 배열에서 사과가 위치하는 곳에 1값을 부여
• 뱀의 몸통을 담을 좌표 클래스를 생성하고 출발점에 우선적으로 큐에 삽입
• 방향은 시계방향(위,오,아,왼)으로 설정
• 요구되는 방향에 맞게 뱀을 한 칸 늘림
• 늘어난 좌표 기준으로
  • 사과가 존재하면 => 해당 부분을 0으로 값을 바꿔줌
  • 존재하지 않으면 => 처음 큐에 담긴 부분(꼬리부분)을 pop & 마킹 풀어주기
• 사과가 있든 없든 우선적으로 한 칸 움직인 곳은 뱀이 존재하기 때문에 큐에 삽입 & 마킹(조건-7)
• 벽 또는 자기자신의 몸통에 부딪히면 종료
  
  
• '현재 진행되는 방향 + 입력된 명령의 방향 = 새로운 방향' 을 고려해 Switch Case문 설정
• ex. 오 + 오 = 아래, 오 + 왼 = 위..
• 새로운 방향을 리턴하고 다시 전진하는 프로세스를 반복

 

기존 2차원 배열의 시계방향 배열과 뱀의 시점에서의 방향을 인덱스로 관리해 새로운 방향을 만들어주는 방법도 있어서 이 방법도 시도해봐야겠다...

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Position_3190{
    public int y, x;

    public Position_3190(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Problem_3190 {

    static int size;
    static int[][] map;
    static StringTokenizer st;

    static ArrayList<String> operationLists;
    static int operIdx = 0;
    static boolean[][] checked;

    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    static int time = 0;
    static Queue<Position_3190> snake = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        size = Integer.parseInt(br.readLine());
        map = new int[size+1][size+1];
        checked = new boolean[size+1][size+1];

        int appleNum = Integer.parseInt(br.readLine());
        for(int i=0; i<appleNum; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            map[y][x] = 1;  //사과 마킹
        }

        //명령을 리스트에 미리 담아두기
        operationLists = new ArrayList<>();
        int convertNum = Integer.parseInt(br.readLine());   //방향 변환 횟수
        for(int i=0; i<convertNum; ++i){
            String operation = br.readLine();
            operationLists.add(operation);
        }

        //0,1,2,3 (위, 오, 아, 왼)
        int dir = 1;
        snake.add(new Position_3190(1, 1));
        checked[1][1] = true;
        
        doProcess(1, 1, dir);
        System.out.println(time);
    }

    private static void doProcess(int y, int x, int dir) {
        //(1,1)을 기준으로 한칸씩 전진
        while (true){
            ArrayList<Integer> movedPosition = moveSnake(y, x, dir);
            
          	//아무것도 없다면 벽 or 자기자신에 부딪힌거
            if(movedPosition.size() == 0){
                return;
            }
            y = movedPosition.get(0);
            x = movedPosition.get(1);

            //명령어 조건
            if(operIdx < operationLists.size()){
                String oper = operationLists.get(operIdx);
                st = new StringTokenizer(oper, " ");
                int operTime = Integer.parseInt(st.nextToken());
                String operation = st.nextToken();
				
                int operDir = 0;
                if(operation.equals("D")) operDir = 1;
                else if(operation.equals("L")) operDir = 3;

				//해당 시간의 경우를 처리하면 그 다음 명령어를 수행할 수 있도록
                if(operTime == time){
                    dir = doOperation(operDir, dir);
                    operIdx++;
                }
            }
        }
    }

    private static ArrayList<Integer> moveSnake(int y, int x, int dir) {
        ArrayList<Integer> arrayList = new ArrayList<>();

        //머리를 늘리고
        int moveY = y + dy[dir];
        int moveX = x + dx[dir];

        //벽에 부딪히거나 자신의 몸에 부딪히면 time++, list에는 아무것도 넣지 않음
        if(!isRanged(moveY, moveX) || checked[moveY][moveX]){
            time++;
            return arrayList;
        }

        //사과가 있다면 0으로 만들어줌
        if(map[moveY][moveX] == 1){
            map[moveY][moveX] = 0;
        }
        //사과가 없다면 꼬리 제거
        else if (map[moveY][moveX] == 0){
            Position_3190 tail = snake.poll();
            checked[tail.y][tail.x] = false;
        }

        //머리를 내민 위치는 어찌됐든 큐에 담겨야 함
        snake.add(new Position_3190(moveY, moveX));
        checked[moveY][moveX] = true;

        arrayList.add(moveY);
        arrayList.add(moveX);
        time++;

        return arrayList;
    }

    private static int doOperation(int operation, int preDir) {
        int dir = 0;
        switch (operation){
            case 1:
                //이전 방향이 위,오,아,왼인 경우
                if(preDir == 0){
                    dir = 1;
                }
                else if(preDir == 1){
                    dir = 2;
                }
                else if(preDir == 2){
                    dir = 3;
                }
                else if(preDir == 3){
                    dir = 0;
                }
            break;

            case 3:
                //이전 방향이 위,오,아,왼인 경우
                if(preDir == 0){
                    dir = 3;
                }
                else if(preDir == 1){
                    dir = 0;
                }
                else if(preDir == 2){
                    dir = 1;
                }
                else if(preDir == 3){
                    dir = 2;
                }
            break;
        }

        return dir;
    }

    private static boolean isRanged(int moveY, int moveX) {
        if(moveY > 0 && moveY <= size && moveX > 0 && moveX <= size) return true;
        return false;
    }
}

 

 

[시험 감독 _ 13458]

 

 

* 조건

1. 총 n개의 시험장

2. 감독관은 2부류(총 감독관, 부 감독관)

3. 총 감독관은 응시자 수 B명을 관리, 부 감독관은 C명 관리 가능

4. 각 시험장마다 총 감독관은 무조건 1명이 배치되어야 함

 

* 알고리즘

- 최적이라고 생각되는 부분부터 진행: 그리디 알고리즘

 

* 로직(Logic)

- 각 강의실마다 총 감독관을 우선적으로 배치하고 남은 인원을 부 감독관으로 채우면 된다

- 총 감독관은 무조건 1명은 배치되어야되기 때문에 우선적으로

해당 강의실 % 총 감독관이 관리할 응시자 수(B) >= 0이면 해당 강의실의 응시자 수를 그만큼 빼준다 / 한명만 배치 가능하기 때문에 check = true로 마킹

- 나머지 부 감독관의 경우, 강의실의 남은 인원 % C == 0 이면 몫이 곧 배치 가능한 인원이고, 나누어 떨어지지 않으면 (몫 + 1)가 곧 배치 가능 인원

- 해당 강의실 인원이 끝나면 리턴

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Problem_13458 {

    static int[] classes;
    static int classNum;
    static long count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        classNum = Integer.parseInt(br.readLine());
        classes = new int[classNum];
        String input = br.readLine();
        st = new StringTokenizer(input, " ");

        int idx = 0;
        while (st.hasMoreTokens()){
            classes[idx++] = Integer.parseInt(st.nextToken());
        }

        String admin = br.readLine();
        st = new StringTokenizer(admin, " ");
        int supervisorNum = Integer.parseInt(st.nextToken());
        int subNum = Integer.parseInt(st.nextToken());

        for(int i=0; i<classNum; ++i){
            doProcess(supervisorNum, subNum, i);
        }

        System.out.println(count);
    }

    private static void doProcess(int supervisorNum, int subNum, int index) {
        boolean check = false;

        while (true){
            int superAdmin = supervisorNum;
            int subAdmin = subNum;

            if(classes[index] <= 0) return;

            if(!check && classes[index] % superAdmin >= 0){
                classes[index] -= superAdmin;
                count++;
                check = true;
            }
            else{
                if(classes[index] % subAdmin == 0) count += (classes[index] / subAdmin);
                else count = count + (classes[index] / subAdmin) + 1;

                return;
            }
        }
    }
}

 

시간이 너무 오래걸린다.. 알거 같은데 라는 느낌은 진짜 말 그대로 알거 같은데인거 같다. 정확하게 문제를 파악하고 조건을 세우며 구현하는 능력의 필요성을 느꼈다. 제 시간에 풀 수 있는 날을 기대하며..!