쌉쌀한 무화과의 개발로그

[문제 설명]

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

[제한사항]

n은 1 이상 1,000 이하입니다.

​

[입출력 예]

>문제 풀이

삼각형 모양을 배열에 왼쪽 정렬로 담는다고 생각합니다.

그럼 아래 그림의 우측 그림처럼 값이 들어가야겠죠.

이렇게 되면, 3가지 동작으로 이동하면서 idx++값이 들어가게 됩니다.

이동 횟수는 dx[0][0]~dx[5][0]까지 6번 아래로, 5칸 오른쪽, 대각선 4칸, 아래 3칸, 오른쪽 2칸, 대각선 1칸으로 n--로 반복하게 됩니다.

>전체 코드

class Solution {
    public int[] solution(int n) {
        int[] answer = new int[n*(n+1)/2];
        int[][] mat= new int[n][n];
        
        int x=-1, y=0, idx=1;
        for(int i=0; i<n; i++){
            for(int j=i; j<n; j++){
                if(i%3==0){ //아래로
                    x++;
                }else if(i%3==1){//오른쪽으로
                    y++;
                }else{//대각선으로
                    x--;
                    y--;
                }
                mat[x][y]= idx++;
            }
        }
        
        idx=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(mat[i][j]==0) break;
                answer[idx++]= mat[i][j];
            }
        }
        
        return answer;
    }
}

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

*참고한 블로그

https://minhamina.tistory.com/58

[문제설명]

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

• (a1, a2, a3, ..., an)

​

튜플은 다음과 같은 성질을 가지고 있습니다.

1. 중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)

2. 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)

3. 튜플의 원소 개수는 유한합니다.

​

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

• {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}

​

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

와 같이 표현할 수 있습니다.

​

이때, 집합은 원소의 순서가 바뀌어도 상관없으므로

• {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

• {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}

• {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

​

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

​

[제한사항]

s의 길이는 5 이상 1,000,000 이하입니다.

s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.

숫자가 0으로 시작하는 경우는 없습니다.

s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.

s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.

return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.

​

[입출력 예]

* 입출력 예에 대한 설명

입출력 예 #1

문제 예시와 같습니다.

​

입출력 예 #2

문제 예시와 같습니다.

​

입출력 예 #3

(111, 20)을 집합 기호를 이용해 표현하면 {{111}, {111,20}}이 되며, 이는 {{20,111},{111}}과 같습니다.

​

입출력 예 #4

(123)을 집합 기호를 이용해 표현하면 {{123}} 입니다.

​

입출력 예 #5

(3, 2, 4, 1)을 집합 기호를 이용해 표현하면 {{3},{3,2},{3,2,4},{3,2,4,1}}이 되며, 이는 {{4,2,3},{3},{2,3,4,1},{2,3}}과 같습니다.

>문제 풀이

s= {{2, 1, 3}, {2}, {2, 1}, {2, 1, 3, 4}};

​

1. 주어진 문자열을 쪼갠다.

arr[0]= "{2, 1, 3}"

arr[1]= "{2}"

arr[2]= "{2, 1}"

arr[3]= "{2, 1, 3, 4}"

​

2. arr를 문자열의 길이에 따라 정렬합니다.

arr[0]= "{2}"

arr[1]= "{2, 1}"

arr[2]= "{2, 1, 3}"

arr[3]= "{2, 1, 3, 4}"

​

3. 중복체크를 하면서 LinkedList에 넣어주고 다시 answer에 넣어줍니다.

list= 2, 1, 3, 4

answer[]={2, 1, 3, 4};

​

코드 개선

* 얼마전 코테 를 보면서,,

값의 들어온 순서대로 출력을 해야할 때 LinkedList를 써야한다는 것을 깨달았었다.

그래서 이번에도 LinkedList를 사용했는데, 다른분의 코드를 보고 리스트를 안써도 set을 사용해서 중복 체크만 하고 바로 answer[]에 넣어도 된다는 걸 알았다.

​

그래서 위에서는 1)s.split 및 정렬 // 2)중복체크 해서 list만들기 // 3)list를 다시 answer로 옮겨주기 3단계로 구현했지만, 아래의 로직이면 3)번 과정을 없앨 수 있다.

HashSet<Integer> set= new HashSet<>();
//String s를 split하고//
answer= new int[arr.length];

for(int i=0; i<arr.length; i++){
    String[] tuple= arr[i].split(",");
    for(int j=0; j<tuple.length; j++){
        if(!set.contains(Integer.parseInt(tuple[j])))
            answer[idx++]= Integer.parseInt(tuple[j]);
    }
}

근데 나는 s를 split해서 arr에 넣을때 "" 값이 들어가 있었기 때문에, 위의 방법으로 answer의 크기를 미리 지정해주려면 split 코드를 약간 수정해서 넣어야 할 것 같다.

+) 정렬 코드도 이런식으로 개선 할 수 있다.

Arrays.sort(arr, new Comparator<String>(){
    public int compare(String s1, String s2){
        return s1.length()-s2.length();
    }
});

//위의 코드를 아래처럼 수정 가능
Arrays.sort(arr, (s1, s2)->{return s1.length()-s2.length();});

>전체 코드

import java.util.*;
class Solution {
    public int[] solution(String s) {
        int idx=0;
        int[] answer = {};
        LinkedList<Integer> list= new LinkedList<>();
        
        String[] arr= s.split("\\{|\\},\\{|\\}");
        
        Arrays.sort(arr, new Comparator<String>(){
            public int compare(String s1, String s2){
                return s1.length()-s2.length();
            }
        });
        
        for(int i=0; i<arr.length; i++){
            if(arr[i].equals("")) continue;
            String[] tuple= arr[i].split(",");
            for(int j=0; j<tuple.length; j++){
                if(!list.contains(Integer.parseInt(tuple[j])))
                    list.add(Integer.parseInt(tuple[j]));
            }
        }
        
        answer= new int[list.size()];
        for(int i=0; i<list.size(); i++){
            answer[i]= list.get(i);
        }
        
        return answer;
    }
}

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

[문제 설명]

△△ 게임대회가 개최되었습니다. 이 대회는 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