쌉쌀한 무화과의 개발로그

[문제 설명]

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.

아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

​

[제한사항]

maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.

n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.

maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.

처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

​

[입출력 예]

* 입출력 예 설명

입출력 예 #1

주어진 데이터는 다음과 같습니다.

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

입출력 예 #2

문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

>문제 풀이

최단거리를 구하기 위한 bfs 문제였습니다.

상하좌우로 갈 수 있게 하되, maps[][]==0인 곳은 못가고 이미 방문했던 곳은 못가도록 visited[][]를 체크해주며 카운트해나갑니다.

마지막 칸에 도달하지 못할수도 있으므로 bfs를 다 돌고나서 maps[n-1][m-1]==1이면 answer=-1;

​

>전체 코드

import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int n=maps.length, m=maps[0].length;
        int answer, x, y, nx, ny;
        int[] dx={-1, 0, 1, 0};
        int[] dy={0, -1, 0, 1};
        boolean[][] visited= new boolean[n][m];
        Queue<Integer> queue= new LinkedList<>();
        
        queue.offer(0);
        queue.offer(0);
        visited[0][0]= true;
        while(!queue.isEmpty()){
            x= queue.poll();
            y= queue.poll();
            
            for(int i=0; i<dx.length; i++){
                nx= x+dx[i];
                ny= y+dy[i];
                
                if(nx<0||nx>=n||ny<0||ny>=m) continue;
                if(maps[nx][ny]==0) continue;
                if(!visited[nx][ny]){
                    queue.offer(nx);
                    queue.offer(ny);
                    maps[nx][ny]=maps[x][y]+1;
                    visited[nx][ny]= true;
                }
            }
        }
        answer= maps[n-1][m-1];
        if(maps[n-1][m-1]==1) answer=-1;
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/1844

[문제 설명]

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

​

[제한사항]

N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)

A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

​

[입출력 예]

입출력 예 설명

입출력 예 #1

첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

>문제 풀이

level 2 중에도 쉬운 문제 였습니다.

문제에 a, b는 N이하의 자연수라고만 적혀있어서 Math.min, Math.max로 순서 정리를 해주고

한 step 씩 올라가는 과정을 cnt++로 카운트 해주면 됩니다.

​

홀수 일때 ex) b=7이면 8이랑 붙어서 올라가게 되며 다음 단계에서 index 4가 됩니다.

즉, a, b가 홀수일 경우 (a+1)/2가 다음 단계의 index가 됩니다.

짝수일 경우에는 a/2를 넘겨주면 됩니다.

​

이것만 알면 풀 수 있는 문제였습니다.

>전체 코드

class Solution
{
    public int solution(int n, int a, int b)
    {
        return round(Math.min(a, b), Math.max(a, b));
    }
    
    public int round(int a, int b){
        int cnt=1;
        
        while(true){
            if (b%2==0 && a+1==b) break;
            if(a%2!=0) a+=1;
            if(b%2!=0) b+=1;
            a/=2;
            b/=2;
            cnt++;
        }
        
        return cnt;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/12985

[문제 설명]

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

​

[제한사항]

numbers는 길이 1 이상 7 이하인 문자열입니다.

numbers는 0~9까지 숫자만으로 이루어져 있습니다.

"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

​

[입출력 예]

* 입출력 예 설명

예제 #1

[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2

[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

11과 011은 같은 숫자로 취급합니다.

>문제 풀이

찾은 소수를 중복없이 저장 및 카운트 하기 위해 자료구조로 hash set을 사용했습니다.

주어진 String numbers를 조합해서 만드는 건데, 주의점은 카드의 중복 사용이 안됩니다.

즉 사용했던 카드를 다시 사용할 수 없습니다. 그래서 boolean visited[]를 이용해서 이미 사용한 카드는 사용하지 못하도록 처리해주었습니다.

​

1) 완전탐색으로 만들 수 있는 숫자 조합 찾기

2) 숫자 조합이 0, 1이 아니면서 소수인지 판별한 후 true면 set에 저장

​

answer= set.size();

>전체 코드

import java.util.HashSet;
class Solution {
    static HashSet<Integer> set= new HashSet<>();
    static char[] arr;
    static boolean[] visited;
    
    public int solution(String numbers) {
        int answer = 0;
        arr= new char[numbers.length()];
        visited= new boolean[numbers.length()];
        
        for(int i=0; i<numbers.length(); i++){
            arr[i]=numbers.charAt(i);
        }
        recursion("", 0);
        
        answer= set.size();
        return answer;
    }
    
    //재귀: 가능한 숫자 조합을 찾고 소수여부에 따라 set에 추가
    public void recursion(String str, int idx){
        int num;
        if(str!="") {
            num= Integer.parseInt(str);
            if(isPrime(num)) set.add(num);
        }
        
        if(idx== arr.length) return;
        
        for(int i=0; i<arr.length; i++){
            if(visited[i]) continue;
            visited[i]= true;
            recursion(str+arr[i], idx+1);
            visited[i]= false;
        }
    }//rec
    
    public boolean isPrime(int num){ //소수 판별
        if(num==1||num==0) return false;
        for(int i=2; i<=Math.sqrt(num); i++){
            if(num%i==0) return false;
        }
        
        return true;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42839

[문제설명]

rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.

x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.

다음은 6 x 6 크기 행렬의 예시입니다.

이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.

행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

​

[제한사항]

rows는 2 이상 100 이하인 자연수입니다.

columns는 2 이상 100 이하인 자연수입니다.

처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.

즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.

queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.

queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.

x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.

1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.

모든 회전은 순서대로 이루어집니다.

예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.

​

[입출력 예시]

<입출력 예 설명>

입출력 예 #1

회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.

입출력 예 #2

회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.

입출력 예 #3

이 예시에서는 행렬의 테두리에 위치한 모든 칸들이 움직입니다. 따라서, 행렬의 테두리에 있는 수 중 가장 작은 숫자인 1이 바로 답이 됩니다.

>문제 풀이

1) 행렬에 대해 행의 개수와(rows) 열의 개수(columns), 그리고 실행해야할 쿼리가 들어옵니다.

rows와 columns에 따라 행렬을 만들어줍니다.

2) 이제 쿼리별로 행렬을 회전해줍니다.

회전을 하면서 회전되는 값들 중 최소값을 찾아 return 합니다.

​

2) return된 값을 answer[i]에 넣어서 최종적으로 return answer;

>전체 코드

class Solution {
    
    public int[] solution(int rows, int columns, int[][] queries) {
        int[] answer = new int[queries.length];
        int[][] arr= new int[rows+1][columns+1];
        int idx=1;
        
        //배열에 숫자 넣기
        for(int i=1; i<=rows; i++){
            for(int j=1; j<=columns; j++){
                arr[i][j]= idx++;
            }
        }
        
        for(int i=0; i<queries.length; i++){ //쿼리별로 회전하기
            answer[i]= rotation(arr, queries[i][0], queries[i][1], queries[i][2], queries[i][3]);
        }
        
        return answer;
    }
    
    static int[] dx= {0, 1, 0, -1};
    static int[] dy= {1, 0, -1, 0};
    public int rotation(int[][]arr, int x1, int y1, int x2, int y2){
        int N= x2-x1; //가로
        int M= y2-y1; //세로
        int[] size= {M, N, M, N};
        int x=x1, y=y1, nx, ny;
        int before=arr[x][y], after, min=arr[x1][y1];
        
        for(int i=0; i<4; i++){
            for(int j=0; j<size[i]; j++){
                nx= x+dx[i];
                ny= y+dy[i];
                min= min<arr[nx][ny]? min:arr[nx][ny];
                after= arr[nx][ny];
                arr[nx][ny]= before;
                before=after;
                x= nx;
                y= ny;
            }
        }//for
        return min;
    }//rot
}

https://programmers.co.kr/learn/courses/30/lessons/77485

[문제 설명]

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.

ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

​

<제한 사항>

name은 알파벳 대문자로만 이루어져 있습니다.

name의 길이는 1 이상 20 이하입니다.

​

<입출력 예>

>문제 풀이

조이스틱을 상하 좌우로 움직여서 입력받은 String name을 최소로 몇 번 만에 만들 수 있는지 구해야합니다.

이 문제는 최소한의 좌우 조작 횟수를 어떻게 구할지가 관건이었습니다.

만약 "BBBAAB" 의 경우에 BBBAAB -> BBBAAB 이와 같은 순서로 움직일 때 최소 횟수가 나옵니다.

​

근데 이 문제가 테스트 케이스가 좀 부족하다고 느낀게 위에 제가 예시로 든 "BBBAAB"의 경우 답이 8이라고 생각되는데, 9로 출력되는 코드의 경우에도 채점을 통과합니다.

그래서 풀어놓고도 풀이하는데 오래 걸린 것 같습니다..ㅎㅎ.;;ㅜ

​

입력받은 name에 A가 포함되어 있다면 A가 가장 긴 부분을 기준으로 좌우 조작을 하는게 최소값이 나올 것으로 생각했는데, 이경우

1) 오른쪽으로 쭉 갔다가 "AA~A"를 만나면 다시 index=0으로 돌아오고, 뒤로 가서 "AA~A"를 만난다.

2) 뒤로 가서 "AA~A"를 만나면 다시 index=0로 돌아오고, 오른쪽으로 가서 "AA~A"를 만난다.

두가지 방법이 있습니다.

즉 name.length()-1 / 1번 / 2번 중에 최소값이 좌우조작의 최소횟수 인거죠.

*근데 문제의 테스트 케이스에는 1번 2번에 대해 처리가 달라도 정답이 되는 것 같습니다.

(제가 문제를 잘못 이해한 건가요.. 일단 내일 일어나서 다시 살펴봐야 할 것 같습니다.)

​

+수정하겠습니다.) 문제를 다시 읽어보니까 ◀:커서가 왼쪽으로 이동할 때, 첫번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서 라는 조건은 있지만, ▶:커서가 오른쪽으로 이동할 때, "마지막 위치에서 오른쪽으로 이동하면 첫번째 문자에 커서"라는 조건은 없습니다!

즉, "BBBAAB" 의 경우에 BBBAAB -> BBBAAB 이와 같은 순서로 움직일 때 최소 횟수가 나옵니다. (=9회)

​

◀ 왼쪽 화살표의 조건을 읽고 오른쪽도 같은 조건이라고 생각했었네요...(역시 정신이 똘망똘망 할 때 풀어야하나 봅니다..ㅎㅎ)

>전체 코드

import java.util.*;
class Solution {
    public int solution(String name) {
        int answer = 0;
        char d;
        
        for(int i=0; i<name.length(); i++){
            d= name.charAt(i);
            answer+=Math.min(d-'A', Math.abs('A'+26-d));
        }
        
        int minlen= name.length()-1;
        int end, cnt;
        for(int i=0; i<name.length(); i++){
            if(name.charAt(i)=='A') continue;
            end= i+1;
            while(end<name.length()&&name.charAt(end)=='A'){
                end++;
            }
            cnt=i*2+(name.length()-end);
            minlen= Math.min(minlen, cnt);
        }
        
        return answer+minlen;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42860