섹션1. 시뮬레이션 & 구현 - (2)

🎈섹션1. 시뮬레이션 & 구현 - (2)

🟦 1-3. 잃어버린 강아지 | 현수, 강아지 동시 이동

문제

현수는 농사지을 땅을 찾아 강아지를 데리고 산으로 들로 땅을 찾아 다니고 있었다. 숲속에서 낮잠을 자던 현수는 강아지가 도망가버려 강아지를 잃게 되었다. 강아지가 어디로 갔는지 모르는 현수는 강아지를 찾아 나섰다. 다행히 강아지에게 위치 추적기가 달려 있어 핸드폰 실시간 위성지도로 현수의 위치와 강아지의 위치, 그리고 근처의 지도를 현수는 알 수 있습니다.
지도의 크기는 항상 10_10이며, 각각의 칸에는 각각 나무, 빈칸, 강아지, 그리고 현수가 있을 수 있습니다. 지도는 다음과 같이 주어진다.
0 - 빈칸, 1 - 나무, 2 - 현수, 3 - 강아지
강아지와 현수는 항상 고정된 방법으로 지도를 다닌다. 먼저 북쪽(지도에서 위쪽)으로 출발하되, 계속 한쪽방향으로 가다가 나무나 지도의 끝에 이르면 90도 시계방향으로 회전하게 된다.
한 칸을 이동하거나, 방향을 회전할 때에는 1분이 소요된다.
만약 이동, 또는 회전을 한 후 현수와 강아지가 같은 칸에 있게 되면 현수가 강아지를 찾게 된다. *_현수와 강아지가 있는 숲의 지도정보가 board에 주어지면 몇 분 후에 현수가 강아지를 찾을 수 있는지 구하는 프로그램을 작성하세요.** 10,000분 후에도 찾을 수 없으면 0을 반환합니다.

내 첫 시도 코드

/*1-3. 잃어버린 강아지 (나의 첫 시도) */
import java.util.*;
class Solution1 {
    public int solution(int[][] board){
        int answer = 0;
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        int d1 = 0, d2 = 0, x=0, y =0, a = 0, b=0;
        //현수, 강아지의 최초 출발 위치를 우선 세팅 
        for(int i=0; i<10; i++) {
            for(int j =0; j<10; j++) {
                if(board[i][j] == 2) {
                    x = i;
                    y = j;
                }else if(board[i][j]==3) {
                    a = i;
                    b = j;
                }
            }
        }

        boolean ok = true;

        while(!ok) {
            answer++;
            //현수 이동 
            int nx = x + dx[d1];
            int ny = y + dx[d1];

            if(nx <0 || nx >= 10 || ny <0 || ny >= 10 ||  board[nx][ny] == 1) {
                d1 = (d1+1) % 4 ;
            }
            //강아지 이동
            int na = a + dx[d2];
            int nb = b + dy[d2];

            if(na <0 || na >= 10 || nb <0 || nb >= 10 || board[na][nb] ==1) {
                d2 = (d2+1) % 4;
            }
            //현수 이동 위치 세팅 
            x = nx;
            y = ny;
            //강아지 이동 위치 세팅
            a = na;
            b = nb;

            //만약 이동 중 강아지 위치와 같아지면
            if(board[x][y] == board[a][b]) {
                ok = false;
            }
        }
        return answer;        
    }
    //실행 메인 
    public static void main(String[] args){
        Solution1 T = new Solution1();
        int[][] arr1 = {{0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, 
            {0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 1, 0, 0, 0, 1, 0, 0}, 
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 1, 0, 0, 0, 2, 0, 0}, 
            {1, 0, 0, 0, 0, 0, 1, 0, 0, 0}, 
            {0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 0, 0, 3, 0, 0, 0, 1}, 
            {0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, 
            {0, 1, 0, 1, 0, 0, 0, 0, 0, 0}}; 
        System.out.println(T.solution(arr1));
        int[][] arr2 = {{1, 0, 0, 0, 1, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, 
            {0, 0, 1, 1, 0, 0, 0, 1, 0, 0}, 
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, 
            {1, 0, 0, 0, 0, 0, 1, 0, 1, 0}, 
            {0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, 
            {0, 0, 1, 0, 0, 0, 0, 0, 2, 1}, 
            {0, 0, 0, 1, 0, 1, 0, 0, 0, 1}, 
            {0, 1, 0, 1, 0, 0, 0, 0, 0, 3}}; 
        System.out.println(T.solution(arr2));
    }
}

문제 풀이

• 우선 현수와 강아지의 이동은 별개의 사건으로 생각해야 한다.
• ex. 현수가 회전할 때 강아지는 회전할 수도 있고 안할수도 있다
• 또한, 회전 시에는 이동을 안한다. 회전과 이동도 별개의 사건으로 생각해야 한다.
• 청소 로봇의 이동은 continue로 지속했지만, 이 문제의 경우 continue 할 경우, 그 밑의 코드를 모두 건너뛰므로. flag1, flag2 를 걸어주어야 한다.
• flag의 경우 true이면 기본적으로 이동 O, false이면 회전하느라 이동X
• 마지막에 시간 10000 넘을 경우 0을 리턴하는 조건도 기입해야 한다.

완성 코드

/*1-3. 잃어버린 강아지 (나의 첫 시도) */
import java.util.*;
class Solution1 {
    public int solution(int[][] board){
        int n = board.length;

        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        int x1 = 0, y1 = 0, x2 = 0, y2 =0;
        //현수, 강아지의 최초 출발 위치를 우선 세팅 
        for(int i=0; i<n; i++) {
            for(int j =0; j<n; j++) {
                if(board[i][j] == 2) {
                    x1 = i;
                    y1 = j;
                }else if(board[i][j]==3) {
                    x2 = i;
                    y2 = j;
                }
            }
        }
        // 현수, 강아지 방향 좌표, 시간 변수
        int d1 = 0, d2 = 0, count = 0;

        while(count < 10000) {
            count++;
            //현수 이동 
            int nx1 = x1 + dx[d1];
            int ny1 = y1 + dy[d1];
            //강아지 이동
            int nx2 = x2 + dx[d2];
            int ny2 = y2 + dy[d2];
            //flag - 현수 회전과 강아지 회전을 별개의 사건으로 두어야 하고
            // 회전 시에는 이동X 이므로 flag 별도로 걸어둘 것 
            //[flag == true 기본 이동 O, flag == false 이면 회전만.]    
            boolean flag1 = true, flag2 = true;
            if(nx1 < 0 || nx1 >= n || ny1 < 0 || ny1 >= n || board[nx1][ny1] == 1){
                d1 = (d1+1) % 4;
                flag1 = false; //이동 못하고 제자리에 있고 회전만 하도록 
            }

            if(nx2 < 0 || nx2 >=n || ny2 <0 || ny2 >= n || board[nx2][ny2] == 1) {
                d2 = (d2+1) % 4;
                flag2 = false;
            }

            //이동한 좌표를 세팅 - 회전 없이 여전히 true인 경우에만 
            if(flag1 == true) {
                x1 = nx1;
                y1 = ny1;
            }
            if(flag2 == true) {
                x2 = nx2;
                y2 = ny2;
            }

            //이제 현수와 강아지가 만난 경우 break 걸어주기
            if(x1 == x2 && y1 == y2) break;
        }
        if(count >= 10000 ) return 0;

        return count;        
    }
    //실행 메인 
    public static void main(String[] args){
        Solution1 T = new Solution1();
        int[][] arr1 = {{0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, 
            {0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 1, 0, 0, 0, 1, 0, 0}, 
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 1, 0, 0, 0, 2, 0, 0}, 
            {1, 0, 0, 0, 0, 0, 1, 0, 0, 0}, 
            {0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 0, 0, 3, 0, 0, 0, 1}, 
            {0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, 
            {0, 1, 0, 1, 0, 0, 0, 0, 0, 0}}; 
        System.out.println(T.solution(arr1));
        int[][] arr2 = {{1, 0, 0, 0, 1, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, 
            {0, 0, 1, 1, 0, 0, 0, 1, 0, 0}, 
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, 
            {1, 0, 0, 0, 0, 0, 1, 0, 1, 0}, 
            {0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, 
            {0, 0, 1, 0, 0, 0, 0, 0, 2, 1}, 
            {0, 0, 0, 1, 0, 1, 0, 0, 0, 1}, 
            {0, 1, 0, 1, 0, 0, 0, 0, 0, 3}}; 
        System.out.println(T.solution(arr2));
    }
}

---

🟦 1-4. 좌석 번호

문제

세계 최고의 알고리즘 전문가인 현수의 강연을 보기위해 많은 사람들이 찾아왔습니다.
강연장에는 가로로 c개, 세로로 r개의 좌석이 c×r격자형태로 배치되어 있다. 각 좌석의 번호는
해당 격자의 좌표 (x,y)로 표시된다.
아래 그림은 가로 6개, 세로 5개 좌석으로 구성된 6×5격자형 좌석배치입니다.

각 격자에 표시된 (x,y)는 해당 좌석의 번호를 말합니다. 가장 왼쪽 아래의 좌석번호는 (1,1)이며, 가장 오른쪽 위 좌석의 번호는 (6, 5)이다.

사람들은 온 순서대로 (1,1)위치 좌석부터 시작하여 시계방향으로 돌아 들어가면서 빈 좌석에
앉습니다.

만약 5번째로 온 사람은 (1, 5)좌석에 앉고, 8번째로 온 사람은 (4, 5)좌석에 앉으며, 12번째 온 사람은 (6, 3)좌석에, 20번째 온 사람은 (2, 3) 좌석에 앉게됩니다.
매개변수 c와 r에 강연장의 크기가 주어지면, k번째로 온 사람이 앉을 좌석번호를 반환하는 프로그램을 작성하세요.
만일 모든 좌석이 배정되어 k번째 온 사람이 앉을 좌석이 없을 경우 [0, 0]을 반환합니다.

문제 풀이

• 이 문제는 최초로 주어진 격자파을 90도 회전해서 생각해야 한다.
• 90도 회전했으므로 최초에는 12시방향을 보도록 되어있던 방향 변수 세팅은 3시방향을 보도록 해야하며 , 마지막 k번쨰 사람이 앉는 좌표의 경우 각 x,y 좌표에 +1 한 값이 정답이 된다.
• 마지막으로 모든 좌석이 배정되었다는 것은 k > c*r 이 되어 그 이상의 값을 가지면 격자판 이내에 속할 k번쨰 자리가 없다는 것이므로 이 경우 0,0 을 반환하도록 조건을 걸어둔다.

완성 코드

• 내가 첫 시도했을 때는 격자판을 90도로 회전할 생각을 못했기 때문에 c+1, r+1 크기의 board[][]배열 내부를 0으로 초기화 한 뒤, 이곳에 1로 방문한 곳을 체크하면 된다고 생각했다. → 잘못 접근했다.
• 더 쉽게 접근할 방법을 강구하고 적용하는 것이 중요하다.

/* 1- 4. 좌석 번호 )*/
import java.util.*;
class Solution2 {
    // c=강연장 열. r =강연장 행. k번쨰 사람의 좌표
    public int[] solution(int c, int r, int k){
        int[] answer = new int[2];
        //k번쨰 사람의 카운팅을 값으로 담는 용도임 
        int[][] seat = new int[c][r];//행열 담고  -> 90도 회전했다고 생각해라 

        //이미 k번째 수 > c*r 인 경우면. 그 칸에 담을 자리가 어차피 없다는 거니까 0,0, 반환함
        if(k > c*r) return new int[] {0,0};
        //방향 좌표 초기화
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        int d = 1; //90도 회전 후 12시아니고 3시 방향으로 시작함
        int x=0, y=0, count = 1;// 좌표 +1 해야 함

        while(count <k ) {
            //다음으로 갈 지점 지칭용
            int nx = x+dx[d];
            int ny = y+dy[d];
            //경계 밖이거나 이미 방문해서 내용물 담겨있으면 회전 해야 함 
            if(nx<0 || nx>=c || ny<0 || ny>=r|| seat[nx][ny] > 0) {
                d = (d+1) % 4;
                continue; //회전만 하고 지나가야 다음 차례에 +1 처리됨
            }
            seat[x][y] = count; //내용물 담기 (몇 번째)
            count++;
            x = nx;
            y = ny; //자리 이동시킴
        }
        //최종 답 세팅
        answer[0] = x+1;
        answer[1] = y+1;
        return answer;
    }
    //실행 메인 
    public static void main(String[] args){
        Solution2 T = new Solution2();
        System.out.println(Arrays.toString(T.solution(6, 5, 12)));    
        System.out.println(Arrays.toString(T.solution(6, 5, 20)));
        System.out.println(Arrays.toString(T.solution(6, 5, 30)));
        System.out.println(Arrays.toString(T.solution(6, 5, 31)));
    }
}

---

🟦 1-5. 최대길이 바이토닉 수열 | '봉우리 찾기'가 핵심 

문제

바이토닉 수열이란 수열이 증가했다가 감소하는 수열을 의미합니다.
예를 들어 1, 2, 3, 2, 1과 같이 증가했다가 감소하면 바이토닉 수열이라고 합니다. 하지만 1, 2, 3, 4, 5와 같이 증가만 하거나, 5, 4, 3, 2, 1처럼 감소만 하면 바이토닉 수열이라 하지 않습니다. 또 1, 2, 2, 3, 2, 1처럼 같은 값이 이웃해도 바이토닉 수열이라 하지 않습니다.
매개변수 nums에 길이가 n인 수열이 주어지면 이 수열의 연속부분수열 중 가장 긴 바이토닉 수열을 찾아 그 길이를 반환하는 프로그램을 작성하세요.
만약 [1, 3, 2, 5, 7, 4, 2, 5, 1]수열이 주어지면 이 수열의 연속부분수열 중 가장 긴 바이토닉 수열은 [2, 5, 7, 4, 2]이고, 답은 5입니다.

문제 풀이

• 바이토닉 수열이 안되는 것은 (계속 증가or 감소 , 동일값 연속)
• 최초 시도 때는 ‘바이토닉’ 수열을 판별할 조건을 어떻게 줘야 할 지 몰라서 헤맸다.

[풀이 방법]

• 1) 우선 봉우리 값을 찾는다. (최고점)
• 2) 봉우리 인덱스값을 새로운 ArrayList에 담아둔다,
• 3) 봉우리인덱스[] 배열 차례로 순회하며
• 4) 그 내부에서 while() 문으로 봉우리 좌측 부분과 우측 부분을 감소하는 동안만 순회하며 cnt++ 처리
• 5) 최종 Max값을 재세팅하면 된다.

완성 코드

package to_0414;
/* 1-5. 최대길이 바이토닉 수열 */
import java.util.*;

class Solution3 {
    public int solution(int[] nums){
        int answer = 0;
        int n = nums.length;
        ArrayList<Integer> peaks = new ArrayList<>();
        //봉우리 인덱스값 담기
        //맨끝(양쪾) 부분은 어차피 봉우리 못되므로 탐색 구간에서 제외
        //-> 즉, 0과 n은 제외 
        for(int i=1; i< n-1; i++) {
            //현재의 i지점의 좌우 값이 모두 작으면 현재 i는 봉우리임 
            if(nums[i-1] < nums[i] && nums[i] > nums[i+1]) {
                peaks.add(i);
            }
        }

        //각 봉우리 지점별 순회하면서
        for(int x : peaks) {
            int left = x;
            int right = x;
            int cnt = 1; //봉우리 지점 길이 카운팅하고  
            //현 x의 왼쪽 구간 차례로 감소 수열인지 확인 
            while(left-1>=0 && nums[left-1] <nums[left]) {
                left--;
                cnt++;
            }
            //현 x의 오르쪽 구간 차례로 감소 수열인지 확인
            while(right+1 < n && nums[right]> nums[right+1]) {
                right++;
                cnt++;
            }
            answer = Math.max(answer, cnt);//기존 answer보다 더 큰 cnt 나타나면 세팅
        }
        return answer;    
    }
    //실행 메인 
    public static void main(String[] args){
        Solution3 T = new Solution3();
        System.out.println(T.solution(new int[]{1, 2, 1, 2, 3, 2, 1}));
        System.out.println(T.solution(new int[]{1, 1, 2, 3, 5, 7, 4, 3, 1, 2}));
        System.out.println(T.solution(new int[]{3, 2, 1, 3, 2, 4, 6, 7, 3, 1}));
        System.out.println(T.solution(new int[]{1, 3, 1, 2, 1, 5, 3, 2, 1, 1}));
    }
}

---