뚝딱뚝딱

https://softeer.ai/practice/6292

💡 슈퍼바이러스

• lv1의 "바이러스" 업그레이드 버전
• 입력받는 크기가 더 커지기 때문에, 단순히 for문으로 해결하려고 하면, 시간초과가 발생한다.
• 따라서 분할과 정복을 통해 해결해야 한다.
• 즉 입력받은 n을 절반씩 쪼개가면서 분할 하고, 다시 합해가면서 전체 문제를 해결하는 방식이다.
• 이를 위해 solve라는 함수를 생성할 것이고, solve안에서는 solve함수를 재귀적으로 호출하면서 절반씩 나누어 해결한다.
• 코드를 통해 살펴보자.
  
  

public static long solve(long P, long N){
      if(N==1) return P;

      long res = solve(P, N/2);
      if(N%2==0){
        return (res*res)%D;
      }
      else{
        res*=res;
        res%=D;
        return (res*P)%D;
      }
    }

• solve함수는 배수인 P와 거듭 수인 N을 입력으로 받는다.
• N이 1이면 P를 반환한다
• 그렇지 않다면, res를 선언하여 N의 절반만큼 P를 거듭 제곱한 값을 solve를 통해 구하고 저장한다.
• 만약 N이 짝수였다면, res를 두번 곱한 것에 1000000007을 나눈 나머지 값을 반환하면 된다.
• 만약 N이 홀수라면, res를 두번 곱한 것에 1000000007을 나눈 나머지에 P를 한번더 곱해주고 또 1000000007을 나눈 나머지를 반환하면 된다. 왜냐하면 홀수의 경우 나누었을 때 나머지 1이 있기 때문에, P를 한번더 곱해주어야 한다는 의미이다.

• 위의 solve함수를 통해 P의 n거듭제곱 하여 1000000007로 나눈 나머지를 구할 수 있으며, 최종적으로는 k에 곱했어야 했기 때문에, K에 곱한 값에 다시한번 1000000007로 나눈 나머지를 구하면, 답이 된다.
• 전체 코드는 아래와 같다.
   

import java.io.*;
import java.util.*;

public class Main {

    static long D = 1000000007; 
    public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      long K = scanner.nextLong();
      long P = scanner.nextLong();
      long N = scanner.nextLong();
      N*=10;
      long res = solve(P,N)*K;

      res%=D;
      
      System.out.println(res);
    }

    public static long solve(long P, long N){
      if(N==1) return P;

      long res = solve(P, N/2);
      if(N%2==0){
        return (res*res)%D;
      }
      else{
        res*=res;
        res%=D;
        return (res*P)%D;
      }
    }
}

이 문제를 풀면서 한가지 알게 된 사실은, long 타입을 입력받을 땐 nextLong으로 받아야 한다는 점이다.

주 언어였던 c++에서 코테를 위한 java를 병행하여 배우면서 입력을 사용한지 얼마 안되었는데, next~가 세부적으로 존재한다는 것을 알게되었다. nextInt로 받으니 long으로의 변환에서 데이터 손실이 있어 결과가 잘 나오지 않았었다.

https://school.programmers.co.kr/learn/courses/30/lessons/42862

💡 체육복

• 단순 구현 문제
• lost_num이라는 int형 변수에 lost배열의 크기를 저장해두고, 최대로 빌려준 후 남은 학생 수를 저장하도록 하여, n에서 lost_num을 빼 답을 구할 것이다.
• n+1 크기의 배열 arr을 생성해서, reserve를 참고해 여벌을 가진 번호에 1을, 아니면 0으로 초기화한다.
• 근데, 여벌을 가져온 학생 중 도난을 당할 경우 자신의 옷을 입어야 한다. 따라서 lost배열과 arr배열을 비교해서, lost에 있는 번호가 arr배열에서 값이 1이면 0으로 만들고, lost_num을 1 빼준다.
  만약 해당하지 않으면 stack에 lost값을 넣는다.
• stack이 비워질 때까지, 하나씩 빼가면서 arr배열에서, 현재 peek값+1 또는 peek값-1 번호가 1의 값을 가질 때 둘 중 하나 먼저 해당되는 것을 빌리도록 하고, 그 arr값을 0으로, lost_num을 1 빼준다. 그리고 pop한다.
• 최종 answer는 n에서 lost_num을 뺀 값이다.
• 여기서 주의할 점은, lost 배열을 사용하기 전에, 오름차순 정렬해야 한다는 점이다.
  로직은 동일했는데, 두 테케에서 자꾸 실패가 떠서 왜 그런가 하고, 정렬을 해봤더니 해결됐다.
  항상 입력 배열이 정렬되어 주어질 것이라 장담하지 말고, 정렬하고 시작하는 습관을 기르자.
• 그리고 나의 풀이 방식의 경우, lost를 오름차순 정렬한 후에, lost 크기만큼 순회하면서 stack에 넣었다.
  stack에 넣으면 작은 값부터 들어가고, 나올때는 큰 값부터 나오기 때문에, lost+1번호가 여벌이 있는지를 먼저 확인하도록 하였다.
  만약 작은 값부터 나오게 짰다면, lost-1번호가 여벌이 있는지를 먼저 확인하도록 해야, 최대의 값을 가질 수 있을 것이다.
• 전체 코드는 아래와 같다.
  
  

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        
        int[] arr = new int[n+1];
    
        Arrays.fill(arr,0);
        
        for(int i=0; i<reserve.length; i++){
            arr[reserve[i]]++;
        }
        
        int lost_num=lost.length;
        
        Stack<Integer> st = new Stack<>();
        
        Arrays.sort(lost);
        
        for(int i=0; i<lost.length; i++){
            if(arr[lost[i]]==1){
                arr[lost[i]]--;
                lost_num--;
            }else{
                st.push(lost[i]);
            }
        }
        
        while(!st.isEmpty()){
            if(st.peek()<n&&arr[st.peek()+1]==1){
                arr[st.peek()+1]--;
                lost_num--;
            }
            else if(st.peek()>1&&arr[st.peek()-1]==1){
                arr[st.peek()-1]--;
                lost_num--;
            }
            st.pop();
        }
        
        answer=n-lost_num;
        return answer;
    }
}