뚝딱뚝딱

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://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으로 선언해주었다.

https://www.acmicpc.net/problem/9935

💡 문자열 폭발

이 문제를 풀다가 내가 폭발하는 줄 알았다.

2시간동안 총 16번의 시도끝에 결국 해냈다.

세번의 서로 다른 시도가 있었다.

[첫번째 시도]. 자바의 String에서 제공하는 contains함수를 이용하는 것이다.

입력받은 전체 문자열에서 target문자열이 있는지를 contains()함수를 이용하였고, String의 replace함수를 사용해 target을 ""빈 문자열로 변경하도록 하였다.

뭐야 너무 간단하잖아? 하고 자신있게 제출했는데... 예상과는 다르게, "메모리 초과"라는 결과가 나왔다.

String의 경우 문자열이 const이기 때문에, 내용이 바뀌면 계속해서 새로운 문자열을 만들어 저장한다.

이 부분을 완전히 간과하고 있었던 것이다..

그래서 최대 100만 길이 문자열이라면, 굉장히 많은 메모리를 낭비하게 될 것이다.

따라서 String의 replace함수로는 해결할 수 없다!

[두번째 시도]. StringBuilder 클래스를 사용하였다

앞 시도에서 문자열이 계속해서 새로 생성되니까, 메모리 초과가 되는 걸 보고, 덧셈연산을 하지 않고 메모리 효율적인 StringBuilder를 사용하면 되겠다!! 싶어서 StringBuilder객체 sb를 생성하고 문자열을 저장해 주었다.

그리고 sb에서 indexOf()함수를 사용해서 target이 존재하는 위치를 찾고, delete함수를 통해 target을 지우도록 하였다.

그리고 sb를 toString함수를 통해 string으로 출력하도록 하였다.

이젠 되겠지..?? 했는데... 이번에 "시간초과"라는 결과가 나왔다. 

따라서 StringBuilder는 단순히 문자열을 받는 입장으로는 사용할 수 있겠구나라고 판단하였다!

[세번째 시도].

결국은 한번씩 순회를 하는 수밖에 없겠다는 생각을 하였고... 

결론적으로 스택을 활용하면 되는 문제였다!

다음 과정을 거친다.

• 문자열 길이만큼 순회하면서, 스택의 길이가 target 문자열길이 이상이면 끝에서부터 target길이만큼 비교 후, 동일하면 target길이 만큼 pop한다.
• 문자열 덧셈 연산을 안하기 위해 StringBuilder를 사용하고, stack에 있는 값을 그대로 옮겨준다.
• stringBuilder의 크기가 0이 아니면, toStirng으로 출력하도록 하고, 0이면 요구사항에 있는 문자열을 출력한다.

이렇게 하면, 딱 n번 순회하니 시간 초과 문제도 없고, 스택을 통해 push pop으로 문자열을 조정함으로써 새로운 문자열이 생기는 등 메모리 낭비가 발생하지 않을 수 있다.

전체 코드는 아래와같다.

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

public class Main {
    public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      String st=scanner.nextLine();
      String target=scanner.nextLine();
      scanner.close();
      
      Stack<Character> stack = new Stack<>();
     
      for(int i=0; i<st.length(); i++){
          stack.push(st.charAt(i));
          
          if(stack.size()>=target.length()){
              boolean flag = true;
              
              for(int j=0; j<target.length(); j++){
                  if(stack.get(stack.size()-target.length()+j)!=target.charAt(j)){
                      flag=false;
                      break;
                  }
              }
              if(flag){
                  for(int j=0; j<target.length(); j++){
                      stack.pop();
                  }
              }
          }
      }
      
      StringBuilder sb = new StringBuilder();
      
      for(Character c : stack){
          sb.append(c);
      }
      
      if(sb.length()!=0){
        System.out.print(sb.toString());
      }
      else System.out.print("FRULA");
    }
}

헷갈렷던 자바 개념은, stack에 있는 값을 sb에 옮기는 과정이었는데

stack을 뒤에서 부터 뺄 수 있다는 것과, 새로운 값을 sb에 넣을 때는 오른쪽 방향으로 넣는다는 생각때문에,

문자열이 뒤집어져서 sb에 들어가지 않을까? 했는데..

결론적으로 sb에 들어갈 때는 스택의 맨 뒤의 값을 넣고, 다음 값을 넣을 때 앞 방향으로 누적되도록 들어갈 수 있기 때문에, 결국 stack에 들어간 순으로 sb에도 누적할 수 있다고 한다.

알고나면 쉬운데, 생각해내기가 어려웠던 문제였다!

JAVA에서 입력을 받을 때 사용하는 클래스가 Scanner이다.

java.util에 정의되어 있다.

입력 시 다음과 같이 쓸 수 있다.

Scanner scanner = new Scanner(System.in);
String st = scanner.nextLine();

일단 scanner 객체를 하나 생성하고 자바의 표준 입력 스트림인 System.in으로 받은 입력 값을 scanner에 저장한다.

그리고 scanner의 nextLine()함수를 통해 입력받은 값을 st에 저장해 주는 것이다.

이어서 입력하고 싶다면?

scanner를 새로 생성하지않고, 바로 scanner.nextLine()을 호출하면 된다.

그리고 다 입력한 후에는 scanner.close()를 통해 입력스트림을 종료한다.

자바 문법 정도만 레퍼런스를 받고, 알고리즘 자체는 직접 구현한 풀이 방법이다.

set을 활용한 부분에 있어서는 다른 사람들의 코드를 살펴보니 대부분 사용하는 편인 것 같았다.

전체적인 진행 방향은 다음과 같다.

1. 문자열에 들어 있는 0~9 숫자들을 INT 타입으로 바꾸어 int배열에 저장한다.
2. 배열에 저장된 수를 가지고, 직접 짠 조합 알고리즘을 통해 가능한 모든 숫자 조합을 찾아 SET 자료구조에 저장한다.
3. SET에 저장된 숫자가 소수인지 판별하여, 소수인 경우에만 카운트를 한다.

SET 자료구조

- 중복된 값을 저장하지 않아서 유니크한 값으로만 구성된다.
- Set 자료구조는 인터페이스라서 HashSet로 Integer를 명시해서 생성해야 한다.

• 문자열에 들어있는 숫자를 조합해 나올 수 있는 모든 수를 구해야 한다.
• permutation 함수를 이용할 수 있었는데, 존재를 까먹고 조합 알고리즘을 직접 구현함.
• 문자열의 각 숫자를 INT 형식으로 바꾸어 INT타입의 배열에 저장해줌.
• 그 INT배열을 가지고 숫자를 조합하는데, 중복된 숫자 값이 생성될 수 있으므로 Set 자료구조를 사용해서 중복된 값이 들어가지 않도록 하였음.
• 일단, 자리수 하나의 숫자들을 set에 저장.
• 그리고 각각의 저장된 숫자를 제외한 배열 값을 갖는 새로운 배열을 만들어서 재귀적으로 가능한 조합을 만들 수 있도록 하는 함수의 인자로 넣어줌.
• 그 함수가 makePrime인데, 함수이름만 makePrime이고, 사실상 조합을 만드는 함수임. 나의 실수.
• makePrime함수에서는 주어진 배열과, set, 이전에 이미 방문?했던 앞자리 수를 인자로 받음.
• 그리고 앞자리수가 하나 제외되어있는 주어진 배열에 있는 값을 하나씩 앞자리 수에 더하여 수를 만들고 set에 집어 넣음.
• 이때 앞자리 수에 10을 곱하고 배열에 있는 값 중 현재 가리키는 값을 더함으로써 새로운 수를 만들 수 있음.
• 그리고 makePrime함수를 재귀호출함으로써 위의 과정을 반복하다 보면, set에는 모든 가능한 숫자 조합이 만들어져 있음.
• 이 set을 가지고, 순회하면서, 만약 값이 0,1이라면 소수로 포함하지 않고, 2,3,5,7이라면 소수로 카운팅 함.
• 그리고 2의 배수라면 소수로 포함하지 않고, 2의 배수가 아니라면 해당 값을 3부터 (해당값/3)을 한 값까지로 나누었을 때 나머지가 0이면 => 1과 자기 자신 말고도 나눠지는 값이 있다는 것이므로 소수가 아니고, 카운팅 하지 않는다. 만약 그런 값이 하나도 없었다면(=>불리언 값으로 판단함) 소수로 카운팅한다.
• 위의 과정을 거침으로써 소수의 개수를 찾을 수 있다.
• 다소 복잡하게 보이지만, 스스로 짰다는 것에 의의를 둔다.
• 메소드를 익히는 것도 중요해 보인다.

전체 코드이다.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] removeValue(int[] arr, int remove){
        int[] newarr = new int[arr.length-1];
        int first = 0;
        int index = 0;
        for(int i : arr){
            if(i==remove && first==0){
                first = 1;
            }else{
                newarr[index]=i;
                index++;
            }
        }
        
        return newarr;
    }
    
    public void makePrime(int[] arr, Set<Integer> set, int prev){
        for(int i=0; i<arr.length; i++){
            set.add(prev*10+arr[i]);
            int[] newarr = removeValue(arr, arr[i]);
            makePrime(newarr, set, prev*10+arr[i]);
        }
    }
    
    public int solution(String numbers) {
        int answer = 0;//count
        
        int[] nums = new int[numbers.length()];
        Set<Integer> set = new HashSet<>();
        
        for(int i=0; i<numbers.length(); i++){
            nums[i] = Character.getNumericValue(numbers.charAt(i));
        }
        
        for(int i=0; i<nums.length; i++){
            set.add(nums[i]);
            int[] newarr = removeValue(nums, nums[i]);
            makePrime(newarr, set, nums[i]);
        }
        
        //set에는 가능한 모든 값들이 생성된다.
        
        for(int i : set){
            if(i==0 || i==1){//0이거나 1이면 패스
                continue;
            }
            if(i==2 || i==3 || i==5 || i==7){//2,3,5,7이면 count
                answer++;
                continue;
            }
            if(i%2==0){//2의 배수이므로 패스
                continue;
            }else{
                int isPrime = 1;
                for(int j=3; j<=(i/3); j++){
                    if(i%j==0){
                        isPrime=0;
                        break;
                    }
                }
                if(isPrime==1) answer++;
            }
        }
        
        return answer;
    }
}

이 문제를 푸는데만 1시간 반이 걸렸지만, 성공한게 뿌듯했다.