쌉쌀한 무화과의 개발로그

[문제설명]

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

[문제]

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

<제한사항>

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

<입출력 예>

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

※ 공지 - 2020년 6월 8일 테스트케이스가 추가되었습니다.

>문제 풀이

 문자열을 입력받고 나서, 문자열 내에 같은 글자 두개가 연속하면 삭제하고 앞 뒤의 문자열을 붙입니다.

이렇게 반복해서, 수행이 끝났을 때 문자열이 전부 없어지면 1출력, 없어지지 않으면 0출력

처음에는 자료구조를 쓰지않고 문자열 내의 붙어있는 문자들을 자르는 걸 반복하는 방향으로 구현하려고 했는데, 생각해보니 stack을 쓰면 더 쉽게 구현이 가능할 것 같더라고요.

그래서 Stack<Character>을 이용해서 구현했습니다.

문자를 하나씩 떼어 스택에 넣으면서 다음 들어오는 문자가 stack.peek()과 같으면 stack.pop()

반복 수행을 다 하고 나서 stack이 비어있으면 1출력, 남아있으면 0출력

>전체 코드

import java.util.*;
class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        Stack<Character> stk= new Stack<>();
        
        stk.push(s.charAt(0));
        for(int i=1; i<s.length(); i++){
            if(!stk.isEmpty()&&stk.peek()==s.charAt(i)){
                stk.pop();
            }else{
                stk.push(s.charAt(i));
            }
        }
        if(stk.isEmpty()) answer=1;

        return answer;
    }
}

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

[문제 설명]

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

<입출력 예>

numberstargetreturn

<입출력 예 설명>

문제에 나온 예와 같습니다.

>문제 풀이

 재귀를 이용해서 풀었습니다.

>전체 코드

class Solution {
    static int answer=0;
    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, 0, target);
        return answer;
    }
    
    public void dfs(int[] num, int index, int value, int t){
        if(index==num.length){
            if(value==t) answer++;
        }else{
            int minus= value-num[index];
        	int plus= value+num[index];
            dfs(num, index+1, minus, t);
            dfs(num, index+1, plus, t);
        }
    }
}

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

[문제 설명]

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

<제한 사항>

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

scovilleKreturn

<입출력 예 설명>

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

>문제 풀이

변화하는 값에 따라 계속 오름차순을 해야하기 때문에 우선순위 큐를 이용하는게 좋다고 생각해서 Priority Queue를 사용했습니다.

<로직>

PriorityQueue<Integer> pq;

int scoville[]=[1, 2, 3, 9, 10, 12];

int K=7;

1. scoville[]을 pq에 넣어줍니다.
   pq: [1, 2, 3, 9, 10, 12]
2. 작은값+두번째 작은값 * 2
   1, 2를 pq에서 빼서, 1+ 2*2=5 ->pq.offer(5)
   answer++; //카운팅 해줍니다.
   [5, 3, 9, 10, 12] =>> [3, 5, 9, 10, 12]
   
3. pq.poll()>=K 일때까지 반복해줍니다.
4. 단, 할 수 있는 연산을 다 했는데도 모든 값의 수치를 K이상으로 만들 수 없는 경우에는 answer=-1;

>전체 코드

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0, value=0;
        PriorityQueue<Integer> pq= new PriorityQueue<>();
        
        for(int i: scoville){
            pq.offer(i);
        }
        
        while(pq.size()>1){
            if(pq.peek()>=K) break;
            pq.offer(pq.poll()+pq.poll()*2);
            answer++;
        }
        if(pq.poll()<K) answer=-1;
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/42626#