[CodeTree] 가능한 수열 중 최솟값 구하기, 벽 짚고 미로 탈출하기 (Java)

삼성 코테를 준비하면서 코드트리를 써봤는데, 문제별로 유형이 다양해서 매번 문제를 고르는 나한테 딱이었다..

그래서 요즘은 백준, 프로그래머스 보다 코드트리를 쓰는 중.. 코드트리 모든 문제를 푸는 게 목표(?)

 

 

BackTracking: 가능한 수열 중 최솟값 구하기

문제설명

4,5,6으로 만들 수 있는 수열 중에서 인접한 연속 부분 수열 중에서, 사전순으로 (오름차순)에서 가장 앞에 있는 수열을 출력하기

가능한 수열 중 최솟값 구하기

 

해결방법

1. 중복 순열을 만든다.

2. check()함수를 만들어서 만든 중복 순열이 인접한 부분이 있는지 없는지 확인해준다.

 

==> 결론: 시간초과 ㅜ_ㅜ 

내가 했던거는 대강 3^(n^3)이정도 인듯하다. 인접한 수열을 확인하는 부분에서 3중배열로 돌렸기에 이런 결과가 난듯하다. 

그래서 다른 해결 방법을 찾아야했다.

 

시간 제한이 자바 기준으로 1초였기에, 현재 내가 했던 코드처럼 중복순열 만들고 -> 확인 하는 방법 보다는

중복 순열을 만들면서 수를 추가하면서 확인하는 방법을 사용해야 했다.

 

여기서 확인해주는 방법은 의외로(?) 간단했다.

 

len(인접한 수열 길이)에 따라서 간격을 두어 i번째로 따라가면서 같은지 같지 않은지 판별만 해준다.

    static boolean check(int length) {
        //가장 최근에 추가한 숫자로 인해 중복이 발생하는지
        for(int len =1; len<=length/2; len++) {
            boolean flag = true;
            for(int i=0; i<len; i++) {
                if(res[length-len+i] != res[length-2*len+i]) {
                    flag = false;
                    break;
                }
            }
            if(flag) return false; //중복 발견
        }
        return true;
    }

 

 

전체 코드

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

public class Main {
    static StringTokenizer tokens;
    static boolean flag;
    static int n;
    static int res[];
    static int arr[] ={4,5,6};

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(input.readLine());
        res = new int [n];
        permu(0);
    }

    //중복순열만들기
    static void permu(int cnt) {
        if(cnt == n) {
                for(int r: res) {
                    System.out.print(r);
                }
                System.exit(0);
            }


        for(int i=0; i<3; i++) {
            res[cnt] = arr[i];
            if(check(cnt+1)) { //가능할 때만
                permu(cnt+1);
            }
        }
    }
    static boolean check(int length) {
        //가장 최근에 추가한 숫자로 인해 중복이 발생하는지
        for(int len =1; len<=length/2; len++) {
            boolean flag = true;
            for(int i=0; i<len; i++) {
                if(res[length-len+i] != res[length-2*len+i]) {
                    flag = false;
                    break;
                }
            }
            if(flag) return false; //중복 발견
        }
        return true;
    }

}

 

깨달은 점 & 배운 점

시간 복잡도 생각해서 코드짤 것. 결과를 만들고 확인하기보다는 중간에 확인해줄 것

 

 

 

Simulation: 벽 짚고 미로 탈출하기

 

문제 설명

격자 안에 공이 있다. 공의 시작 위치가 주어지고 이 공이 격자 밖으로 탈출 할때까지의 시간을 구하면 된다.

시뮬레이션 문제이다!

벽 짚고 미로 탈출하기

 

해결 방법

전형적인 시뮬레이션 문제다 

여기서 크게는 조건이 3가지가 나오고 안에 세부적인 조건은 각각 1,1,2가지가 나온다.

 

step1 바라보고 있는 방향으로 전진 불가능할 경우 -> 90도 반시계 회전

step 2 바라보도 있는 방향으로 전진이 가능할 경우
          case 1. 바로 앞이 격자 앞이라면 탈출

          case 2. 바로 앞이 격자 앞이 아닌 경우

                    2-1. 현재방향으로 이동했을 때 오른쪽 벽이 존재한다면 현재 방향으로 이동

                    2-2. 현재 방향으로 이동했을 때 오른쪽 벽이 없다면 현재 방향 이동 후 90도로 방향을 바꾸어준다.

 

이렇게 case를 나눠서 풀면 되고, 나는 오른쪽 벽을 어떻게 확인할지 여부가 매우매우 x100 헷갈렸다

근데 방향을 이동하지 말고 d+1을 해서 방향 전환 후 벽이 있는지의 여부를 확인하면 됐었다.

 

전체코드

package codeTree;

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

public class 벽짚고미로탈출하기 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static int n,r,c;
    static int[][] map;
    static boolean[][][] visited;
    static int [][] deltas={{0,1}, {1,0},{0,-1},{-1,0}}; //시계방향

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(input.readLine());
        tokens = new StringTokenizer(input.readLine());
        r = Integer.parseInt(tokens.nextToken())-1;
        c = Integer.parseInt(tokens.nextToken())-1;
        map = new int[n][n];
        visited = new boolean[n][n][4];
        for(int i=0; i<n; i++) {
            String str = input.readLine();
            for(int j=0; j<n; j++) {
                if(str.charAt(j) == '#') map[i][j]=1;
                else map[i][j]=0;
            }
        }
        int d =0;
        int time = 0;

        do{

            //현재 위치에 같은 방향으로 진행한 적이 이미 있었는지 확인
            //이미 한번 겪었던 상황이면, 탈출이 불가능하다는 의미
            if(visited[r][c][d]) { //불가능
                System.out.print(-1);
                System.exit(0);
            }

            //현재값 방문표시
            visited[r][c][d] = true;

            int nx = r + deltas[d][0];
            int ny = c + deltas[d][1];

            //step1
            //바라보고 있는 방향으로 이동하는 것이 가능하지 않은 경우
            // 90도 반시계 회전
            if(wall(nx,ny)) {
                d = (d-1 +4)%4;
            }

            //step2
            //바라보는 방향으로 이동한 것이 가능한 경우, 바로 앞이 격자 밖
            else if(!check(nx, ny)) {
                r = nx;
                c = ny;
                time ++;
            }

            //바라보는 방향으로 이동, 바로 앞이 격자가 아님
            else{
                
                //그 방향으로 이동했다고 가정할 때 오른쪽 벽이 존재하는지 여부
                int rx = nx +deltas[(d+1)%4][0];
                int ry = ny +deltas[(d+1)%4][1];

                //오른쪽에 벽이 있다면 해당 방향으로 이동 가능
                if(wall(rx,ry)) {
                    r = nx;
                    c = ny;
                    time ++;
                }
                //오른쪽에 벽이 없다면 2칸 이동 후 시계방향으로 바꿈
               else{
                    r = rx;
                    c = ry;
                    d = (d+1) %4;
                    time +=2;
                }

            }
        } while(check(r,c));

        System.out.print(time);

    }



    static boolean check(int x, int y) {

        return (x>=0 && x<n) && (y>=0 && y<n);
    }

    //벽이 있는지 없는지
    static boolean wall(int x, int y) {
        return check(x,y) && map[x][y] == 1;
    }

}