뚝딱뚝딱

https://softeer.ai/practice/6284

💡 바이러스

• 단순한 수학문제였다.
• K에 P를 N번 곱한 후 그값을 1000000007로 나눈 값을 출력하는 문제인데, 그냥 곱할 경우에는 int나 long에 완전히 담을 수 없을 정도로 숫자가 커지기 때문에, 일정한 값으로 나누어 져야 한다.
• K에 P를 곱한 후 1000000007로 나눈 나머지를 K에 다시 저장한 후, 그 나머지에 P를 곱하고 또 1000000007로 나눈 나머지를 K에 저장하는 식으로 해결할 수 있다. 이를 N번 반복한다.
• 어떻게 그게 가능할까?
• 만약 K=3, P=5, N=3,D(나누는 값)=13이라고 해보자.
  1R : 3*5=15, 15%13=2
  2R : 2*5=10, 10%13=10
  3R : 10*5=50, 50%13=11
  답:11
  한번에 했을 때 : 3*5*5*5%13 = 375%13=11
  답 11
  
  결과는 동일하다.
  
  15*5%13==(13*5%13)+(2*5%13)
  위와 같이 15 는 13,2로 분배될 수 있기 때문이다. 어차피 13만큼의 몇배던 13의 배수이므로 그 나머지는 0이되기때문에, 2만큼에 몇 배수를 한 것의 13으로 나눈 나머지만 구하면 된다.
• 전체 코드는 아래와 같다.
  

  import java.io.*;
  import java.util.*;
  
  public class Main {
  
      public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long K = scanner.nextInt();
        int P = scanner.nextInt();
        int N = scanner.nextInt();
        int d = 1000000007;
  
        for(int i=0; i<N; i++){
          K=(K*P)%d;
        }
        
        System.out.println(K);
        
      }
  }​

• 참고로 입력 값인 K와 P를 곱했을 때의 최대값의 범위가 10^18~10^19까지 나올 수 있기 때문에 계속해서 갱신되어야 할 K는 long으로 선언해주었다.

여행 경로

💡문제

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.


주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

딱 보자마자 모든 경로를 탐색해야 하기 때문에, dfs를 사용해야 한다는 점은 알아야 한다.

그런데, 문제를 보면, 여러개의 경로가 나올 시 사전 순으로 앞서는 경로를 return해야 한다.

여러개의 경로를 구해두고 그 중에서 알파벳 순으로 먼저인 경로가 앞으로 오도록 정렬한 후 맨 앞에 있는 것을 선택해야한다.

따라서 이 문제는 BFS도 적용해야 한다.(위에서 말한 바와 같이 정렬만 하면 되긴 한다)

다음과 같은 단계로 진행할 수 있다.

1. 여러가지 경로 자체를 리스트 형태로 여러개 저장할 수 있는 이중 리스트를 생성하자.

static List<List<String>> answerList;

솔루션 함수 밖에서 생성해주었다.

2. 방문 여부를 위한 boolean타입 배열을 선언하자.

static boolean[] visited;

이 역시 솔루션 함수 밖에서 생성해주었다.

3. 이제 이중리스트에 ArrayList로 동적 할당해주고, 방문 배열 역시 tickets배열 크기만큼 동적 할당하자.

answerList = new ArrayList<>();
visited = new boolean[tickets.length];

솔루션 함수 내로 들어왔다.

4. 이제 tickets 배열을 순회하면서 출발지가 "ICN"인지 확인하자.

for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals("ICN")) {

5. 조건에 만족한다면, 경로를 저장하기 위한 list를 생성하고 동적할당한다. 그리고 출발지인 "ICN"을 담는다.

현재 노드를 방문한 것이므로 visited[i]를 true로 하고, 리스트에는 해당 노드의 도착지를 저장한다.

List<String> list = new ArrayList<>();
list.add("ICN");
visited[i] = true;
list.add(tickets[i][1]);

6. 도착지인 tickets[i][1]이 다시 출발지가 되어 다음 노드를 방문해야 한다. 따라서 아직 방문하지 않은 노드들 중 출발지가 tickets[i][1]인 노드를 찾아 위의 과정을 반복하자. 이를 dfs함수에 구현하자.

public void dfs(String[][] tickets, int begin, List<String> list) {
        if (list.size() == tickets.length + 1) {
            answerList.add(new ArrayList<>(list));
            return;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(tickets[begin][1])) {
                visited[i] = true;
                list.add(tickets[i][1]);
                dfs(tickets, i, list);
                visited[i] = false;
                list.remove(list.size() - 1); // 백트래킹
            }
        }
    }

   - dfs함수는 tickets와 출발지 인덱스, 진행중이던 경로 list에 대한 정보를 받는다.

   - 만약 현재 list의 크기가 tickets의 길이보다 1 큰 것과 같다면, 모든 tickets를 고려한 것이기 때문에, 이중 리스트인 answerList에 list를 넣는다. = 경로 모음집에 경로를 하나 추가한 것이다.

   - 아직 tickets를 다 방문하지 않았다면, 모든 노드에 대해서, 아직 방문하지 않았고, 인자로 받은 출발지를 갖는 노드를 방문한다.

   - 역시 list에 방문한 노드의 도착지를 넣어준다 (출발지는 이전 단계에서의 도착지로, 이미 넣어졌기 때문이다)

   - 그리고 그 도착지를 기점으로 다시 dfs를 호출해서 반복되도록 해준다.

   - 다 돌고 나서 다시 다른 경로를 순회하기 위해 다시 visited[i]를 false로 바꾸어주는 단계를 잊어선 안된다.

   - 동일한 원리로 list에서도 제거해준다.

7. 다시 solution함수로 돌아오자. 방금 전까지 dfs가 어떻게 돌아가는지를 확인하였다. 이 dfs를 최초로 불러주자.

dfs(tickets, i, list);
visited[i] = false;

   - 여기에서도 dfs를 돌고난 후 혹시 다른 경로를 먼저 방문했을 시를 고려해서 visited[i]를 false로 바꿔주는 것을 잊지 말자.

8. 이렇게 가능한 경로를 다 구했으면, List에 들어있는 경로들을 알파벳 순으로 정렬해주자.

Collections.sort(answerList, (a, b) -> {
            for (int i = 0; i < a.size(); i++) {
                int compare = a.get(i).compareTo(b.get(i));
                if (compare != 0) {
                    return compare;
                }
            }
            return 0;
});

   - Collections의 sort함수를 사용할건데, 람다식을 이용해서 모든 경로에 대해 각각의 첫번째부터 끝번째 노드까지 알파벳 순을 비교해서 빠른것이 앞으로 오도록 설계한다.

9. 이제 answerList의 맨 첫번째 경로가 asnwer가 될 것이다. 이 경로 하나를 가져오기 위해 answer를 list로 선언하고 answerList의 0번째 리스트를 가져와 할당한다. 그리고 list의 toArray함수를 통해 answer를 배열 형태로 반환하도록 한다.

List<String> answer = answerList.get(0);

return answer.toArray(new String[answer.size()]);

이렇게 해서 모든 경로를 탐색하고, 정렬을 통해 알파벳 순으로 가장 빠른 경로를 찾아낼 수 있었다.

전체 코드는 아래와 같다.

import java.util.*;

class Solution {
    static List<List<String>> answerList;
    static boolean[] visited;
    
    public String[] solution(String[][] tickets) {
        answerList = new ArrayList<>();
        visited = new boolean[tickets.length];
        
        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals("ICN")) {
                List<String> list = new ArrayList<>();
                list.add("ICN");
                visited[i] = true;
                list.add(tickets[i][1]);
                dfs(tickets, i, list);
                visited[i] = false;
            }
        }
        
        // 결과로 반환할 경로 선택 (알파벳 순서가 앞서는 경로)
        Collections.sort(answerList, (a, b) -> {
            for (int i = 0; i < a.size(); i++) {
                int compare = a.get(i).compareTo(b.get(i));
                if (compare != 0) {
                    return compare;
                }
            }
            return 0;
        });

        List<String> answer = answerList.get(0);

        return answer.toArray(new String[answer.size()]);
    }
    
    public void dfs(String[][] tickets, int begin, List<String> list) {
        if (list.size() == tickets.length + 1) {
            answerList.add(new ArrayList<>(list));
            return;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(tickets[begin][1])) {
                visited[i] = true;
                list.add(tickets[i][1]);
                dfs(tickets, i, list);
                visited[i] = false;
                list.remove(list.size() - 1); // 백트래킹
            }
        }
    }
}

이제 DFS문제를 3-4번 풀어보니, 어느정도 감이오고, 문제를 읽어보면 DFS로 풀어야하는지 알 수 있게 되었다.

확실히 BFS보다 DFS의 비중이 더 많은 것 같기도 하다.

그리고 자바 문법은 더 꼼꼼히 살펴보아야겠다!!

문제 자체가 힙을 구현하는 카테고리에 있는 걸 보고 접근한 거라, priorityqueue로 풀 수 있다는 걸 알고 풀어서 쉽게 풀어버린 케이스이다. 그래도 오랜만에 heap을 다루는 것이기도 하고, java에 있는 pq를 쓰는 건 처음이라 메소드도 익힐 수 있었다.

💡 Min Heap (PriorityQueue)

Heap?
- 완전 이진 트리의 일종, 우선순위 큐를 위하여 만들어진 자료구조.
- 힙에서는 중복된 값을 허용.
- max heap은 가장 큰 값이 부모노드에, min heap은 가장 작은 값이 부모노드에 있다.
- 부모노드는 자식노드보다 크거나 같고(max heap), 작거나 같아야(min heap) 한다.

- 힙은 배열을 통해 구현할 수 있다.
- 구현을 쉽게 하기 위해 0번 인덱스는 사용하지 않는다.
- 루트 노드가 1번 인덱스이다.
- 왼쪽 자식 노드 인덱스 : (부모노드 인덱스)*2
- 오른쪽 자식 노드 인덱스 : (부모노드 인덱스)*2+1
- 부모 노드 인덱스 : (자식노드 인덱스)/2

자바에서 힙은 java.util에 있는 PriorityQueue를 사용할 수 있고, 기본적으로 min heap을 구현한다.

💡 java.util.PriorityQueue

- 기본적으로 mean heap을 구현한다.
- 요소 삽입 : offer()
- 가장 작은 요소 반환 및 삭제 : poll()
- 가장 작은 요소 반환 : peek()
- 힙의 크기 반환 : size()

이 정도로 정리해 두면 문제는 충분히 풀 수 있다.

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


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


모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

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

모든 음식의 스코빌 지수가 K이상이 된다는 것은, min heap에서 가장 우선 순위에 있는 노드의 값이 K이상인 것과 같고, 그렇게 되면 그 아래 모든 노드는 K이상이 되기 때문에, min heap을 이용해서 아주 쉽게 이 문제를 해결할 수 있다.

알고리즘은 다음과 같다.

1. PriorityQueue 객체를 Integer 타입으로 생성한다.
2. 스코빌 배열에 있는 모든 값을 우선순위 큐에 삽입한다.
3. while문을 통해 다음의 조건을 만족하는 경우에만 반복실행한다
   "우선순위 큐의 가장 작은 값=가장 먼저 나오는 값이 K보다 작고, 우선순위 큐에 있는 요소가 2개이상인 경우"
   다음을 실행한다
   우선순위 큐에서 가장 작은 값 두개 꺼내고 위의 식을 통해 섞은 음식의 스코빌 지수를 구한 후 이를 다시 큐에 삽입한다. 그리고 answer 값을 1 올린다.
   위 과정을 조건을 만족할 경우에 반복한다
4. 위 과정을 마치고 나면 큐는 스코빌 지수가 모두 K이상이거나, 큐에 있는 요소가 2개 미만인 상태일 수 있다.
5. 전자의 경우라면 answer를 그대로 반환하면 되고, 후자의 경우라면 모든 음식을 섞어도 K이상이 안된다는 것이므로 문제에서 주어진 조건에 따라 -1을 반환하면 된다.

전체 코드는 아래와 같다.

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int item : scoville){
            pq.offer(item);
        }
        
        while(pq.peek()<K && pq.size()>=2){
            int temp1 = pq.poll();
            int temp2 = pq.poll();
            pq.offer(temp1+(temp2*2));
            answer++;
        }
        
        if(pq.size()==1 && pq.peek()<K) return -1;
        
        return answer;
    }
}

*** while문을 실행하고 나면 어차피 pq.peek()<K라는 것은 pq.size()==1인 것과 동시에 일어나기 때문에, 마지막 if문에서는 pq.peek()K만 만족하면 -1을 반환하도록 코드를 줄여도 된다.

해결한 방식을 사용하기 전 생각 했던 접근 방식은 다음과 같았다.

1. 맨 앞 수만 가지고 정렬 한다음, 가장 큰 수를 포함하는 숫자를 answer에 저장한다
-> 이렇게 할 경우 가장 큰수에 해당하는 숫자들에 대해서는 언제까지 비교할 것인가? 이게 문제

2. 숫자를 앞 글자부터 버킷에 넣어가는 식으로 비교한다.

-> 그 개수를 모르기 때문에 언제까지 비교? 어디에 넣을것인가? 마땅히 생각나는 자료구조가 없어서 실패

여러가지로 짱구를 돌려봤지만, 모두 복잡한 풀이가 이어질 것으로 예상되어서(2시간 붙잡음..) 힌트를 확인했다.

사실 문제에서는 힌트를 줬다.

"문자열로 출력하세요."

우리가 숫자 그 자체로 두고 비교를 하려니 해결되지 않았던 것이다.

지난 포스팅에서도, 문자 형태의 숫자를 sort하면 숫자 자체가 아닌, 숫자 자체가 사전식으로 큰지를 판단해서 정렬함을 배웠다.(이래서 복습이 중요하다!!!!!!)

1. 그러므로 먼저 배열을 string형태로 변환하는 과정이 필요하다.
2. 하지만 여기서 끝이 아니다. string의 정렬에서는 30,3 과 같은 경우 더 긴 쪽을 크다고 판단한다.
   이런 경우를 대비해서 sort함수의 정렬 기준을 바꾸어 주어야 한다.
   두 문자열을 받았을 때 문자열을 303으로 붙였을 때와 330으로 붙였을 때 어느 쪽이 더 큰가? 
   후자가 더 크다.
   따라서 그렇게 정렬해주면 자동으로 숫자가 큰쪽으로 정렬이 된다.
   이를 위해서 Arrays.sort함수 인자안에서 람다식을 이용해 기준을 설정해 주었다.
3. Arrays.sort(nums, (o1, o2)->(o2+o1).compareTo(o1+o2));
   두번째 인자가 람다식을 통해 기준을 설정해준 것인데, 인자로 받은 string o1, o2에 대해서 o2+o1 순으로 더했을 때의 값과 o1+o2순으로 더했을 때의 값을 비교한 결과가 양수이면 정렬을 결과가 큰 쪽으로 하겠다는 의미이다.
4. 위의 간단한 람다식을 통해 정렬을 했으면, 이제 정렬 결과에 대해 예외를 생각해야 한다.
   만약 숫자 배열에 0밖에 없었다면?
   당연히 결과는 0이어야 한다. 000....은 0이기 때문이다.
   따라서 이런경우에는 "0"을 바로 return 하도록 하였다.
5. 0이 아닌 경우에는 nums에 정렬된 대로 순서대로 string을 붙여서 출력하면 되는데, 이때 string에 + 형식 말고, StringBuilder 클래스를 사용하여 붙였다.
   answer라는 이름으로 해당 객체를 생성해 준 다음에 nums에 있는 값들을 차근차근 append하여 넣어준뒤, 마지막에 return할 때는 answer.toString()으로 반환해주었다.

💡 StringBuilder?

• Java에서 문자열을 효율적으로 생성 및 조작하기 위한 클래스이다.
• + 연산자를 이용해서 반복적으로 연산하는 것보다 append()함수를 통해 문자열을 연결하는 것이 성능을 높일 수 있다.
• 문자열을 연결하거나 수정하는 작업을 수행할 때 많은 문자열 객체가 생성되는 것을 방지하기 때문에, 성능이 향상되고 메모리 사용량을 줄일 수 있다.
• StringBuilder 클래스는 문자열을 연결하고 수정하는 역할을 하는 것이기 때문에, 연결 작업을 끝낸 후 문자열을 반환하려면 클래스 이름 자체가 아니라, 반환 함수인 toString()함수를 이용해서 반환해야 한다.

최종 코드는 다음과 같다.

import java.util.Arrays;

class Solution {
    public String solution(int[] numbers) {
        
        String[] nums = new String[numbers.length];
        
        for(int i=0; i<numbers.length; i++){
            nums[i] = Integer.toString(numbers[i]);
        }
        
        Arrays.sort(nums, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        
        if(nums[0].equals("0")) return "0";
        
        StringBuilder answer = new StringBuilder();
        
        for(int i=0; i<nums.length; i++){
                answer.append(nums[i]);
        }
    
        
        //문자로 표현된 숫자의 경우.. 숫자가 더 크냐가 아니라, 사전식으로 어떤게 더 앞에 있냐를 따지니까.. 문자로 바꿔서 정렬하면 바로 해결됨.
        
        
        return answer.toString();
    }
}

<자바 문법>

**sort함수는 java.util.Arrays에 있다.

**문자열 비교는 .equals("")로 한다.

**int->string으로 변환하는 함수는 Integer.toString(변수)