쌉쌀한 무화과의 개발로그

[문제]

N!의 값을 계산한 후에, 0이 아닌 가장 낮은 자리 수를 구하시오.

예를 들어, 4! = 24 이기 때문에, 0이 아닌 가장 낮은 자리 수는 4이다. 또, 5! = 120이기 때문에, 0이 아닌 가장 낮은 자리 수는 2 이다.

​

[입력]

첫째 줄에 N이 주어진다. N은 20,000보다 작거나 같은 자연수 이다.

​

[출력]

첫째 줄에 N!의 0이 아닌 마지막 자리수를 출력한다.

​

[예제]

>문제 풀이

예전에 틀렸던 문제를 다시 풀어보았습니다.

실버라더니 어려웠던 문제...

​

가끔 참고하는 블로그인데, 이번에도 도움을 받았습니다.

설명을 정말 잘 해놓으셨어요..bb

참고한 블로그 링크: https://steady-coding.tistory.com/322

위의 블로그에 너무 잘 정리되어있기 때문에 이번 포스팅은 제가 이해한 내용과 흐름을 위주로 추후에 다시 보기 위해 작성하겠습니다.

​

먼저 이 문제는 N!에 대해 0을 제외한 마지막 자릿수를 구하는 문제입니다.

입력되는 N의 범위가 무려 20,000 까지기 때문에 무작정 for문을 돌리면 시간초과가 일어납니다.

그래서 이 문제는 dp로 풀게 되었는데, 아래의 로직을 읽어보다 보면 왜 dp로 풀었는지 이해가 될 것입니다.

​

그래서 factorial의 계산에 대해 생각해 볼 필요가 있는데요.

먼저 끝자리에 0이 생기는 조건에 대해 생각해보면, 10의 제곱수를 곱하게 될 경우 끝자리에 0이 붙게 됩니다. 즉 2와 5의 조합에 따라 0이 생긴다고 보면되죠.

​

15!

= (1 x 2 x 3 x 4 x 5) x (6 x 7 x 8 x 9 x 10) x (11 x 12 x 13 x 14 x 15)

5의 배수를 앞으로 모아줍니다.

= (5 x 10 x 15) x (1 x 2 x 3 x 4) x (6 x 7 x 8 x 9) x (11 x 12 x 13 x 14)

​

뒤에 형광펜으로 색칠된 부분의 digit은 모두 4인것을 알 수 있습니다.

왜냐면 끝자리 기준으로

1 x 3 = 3, 2 x 4 = 8 >> digit= 4

7 x 9 =63, 6 x 8 =48 >> digit= 4

따라서 끝자리가 1, 2, 3, 4인 묶음이든, 6, 7, 8, 9인 묶음이든 0이 아닌 마지막 수는 4가 나옵니다.

​

= (5 x 10 x 15) x (1 x 2 x 3 x 4) x (6 x 7 x 8 x 9) x (11 x 12 x 13 x 14)

= 5^3 x 6 x 2^2 x 2^2 x 2^2

이제 0을 만들어내는 10을 없애주기 위해 2와 5를 조합해줍니다.

= 10^3 x 6 x 2^3 //10은 앞서 말했듯 끝자리 수에 영향 없는 0만 만들어주기 때문에

= 6 x 2^3

= 3! x 2^3

​

∴ N에 대해서 위의 방식대로 정리하게 되면

= A! x 2^p 의 구조가 나오게 됩니다.

우리는 이제 이 구조로 끝자리를 구할 수 있습니다.

​

이제 dp를 어떻게 적용시킬지 알아봅시다.

위의 식을 좀 더 정리해볼건데요.

각 숫자의 끝자리를 dp[] 배열에 담는다고 했을 때, 3!의 끝자리는 dp[3]에 담겨있겠죠?

그리고 2의 제곱수 같은 경우에는 끝자리가 2^1=2, 2^2=4, 2^3= 8, 2^4=6 이 반복됩니다.

즉, (dp[3] x 8)%10 이 15!의 0이 아닌 마지막 자릿수 입니다.

​

그렇다면 17!은 어떻게 구할 수 있을까요?

17!= dp[15] x 16 x 17

= dp[15] x 6 x 7

​

즉, N보다 작은 5의 배수의(=temp) dp값을 기준으로 temp+1~ N까지의 수를 곱해주면서 %10을 해주면 구할 수 있습니다.

​

​

* 팩토리얼 계산해주는 사이트 링크 입니다. 참고하세요~

https://ko.numberempire.com/factorialcalculator.php

>전체 코드

import java.util.Scanner;

public class Main {
	
	public static void main(String [] args) {
		int N, temp, dp[];
		
		Scanner scan= new Scanner(System.in);
		
		N= scan.nextInt();
		dp= new int[N+1];
		
		//2^n digit: 2 4 6 8
		dp[1]= 1;
		dp[2]= 2;
		dp[3]= 6;
		dp[4]= 4;
		
		for(int i=5; i<=N; i++) {
			if(i%5==0) {
				temp= i/5;
				dp[i]= (dp[temp]*(int)Math.pow(2, temp%4))%10;
			}else{
				temp= (i/5)*5;
				dp[i]=dp[temp];
				for(int j=temp+1; j<=i; j++) {
					dp[i]=dp[i]*j%10;
				}
			}
		}//end for
		
		System.out.println(dp[N]);
	}	
}

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

[문제 설명]

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 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

[문제 설명]

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.

ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

​

<제한 사항>

name은 알파벳 대문자로만 이루어져 있습니다.

name의 길이는 1 이상 20 이하입니다.

​

<입출력 예>

>문제 풀이

조이스틱을 상하 좌우로 움직여서 입력받은 String name을 최소로 몇 번 만에 만들 수 있는지 구해야합니다.

이 문제는 최소한의 좌우 조작 횟수를 어떻게 구할지가 관건이었습니다.

만약 "BBBAAB" 의 경우에 BBBAAB -> BBBAAB 이와 같은 순서로 움직일 때 최소 횟수가 나옵니다.

​

근데 이 문제가 테스트 케이스가 좀 부족하다고 느낀게 위에 제가 예시로 든 "BBBAAB"의 경우 답이 8이라고 생각되는데, 9로 출력되는 코드의 경우에도 채점을 통과합니다.

그래서 풀어놓고도 풀이하는데 오래 걸린 것 같습니다..ㅎㅎ.;;ㅜ

​

입력받은 name에 A가 포함되어 있다면 A가 가장 긴 부분을 기준으로 좌우 조작을 하는게 최소값이 나올 것으로 생각했는데, 이경우

1) 오른쪽으로 쭉 갔다가 "AA~A"를 만나면 다시 index=0으로 돌아오고, 뒤로 가서 "AA~A"를 만난다.

2) 뒤로 가서 "AA~A"를 만나면 다시 index=0로 돌아오고, 오른쪽으로 가서 "AA~A"를 만난다.

두가지 방법이 있습니다.

즉 name.length()-1 / 1번 / 2번 중에 최소값이 좌우조작의 최소횟수 인거죠.

*근데 문제의 테스트 케이스에는 1번 2번에 대해 처리가 달라도 정답이 되는 것 같습니다.

(제가 문제를 잘못 이해한 건가요.. 일단 내일 일어나서 다시 살펴봐야 할 것 같습니다.)

​

+수정하겠습니다.) 문제를 다시 읽어보니까 ◀:커서가 왼쪽으로 이동할 때, 첫번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서 라는 조건은 있지만, ▶:커서가 오른쪽으로 이동할 때, "마지막 위치에서 오른쪽으로 이동하면 첫번째 문자에 커서"라는 조건은 없습니다!

즉, "BBBAAB" 의 경우에 BBBAAB -> BBBAAB 이와 같은 순서로 움직일 때 최소 횟수가 나옵니다. (=9회)

​

◀ 왼쪽 화살표의 조건을 읽고 오른쪽도 같은 조건이라고 생각했었네요...(역시 정신이 똘망똘망 할 때 풀어야하나 봅니다..ㅎㅎ)

>전체 코드

import java.util.*;
class Solution {
    public int solution(String name) {
        int answer = 0;
        char d;
        
        for(int i=0; i<name.length(); i++){
            d= name.charAt(i);
            answer+=Math.min(d-'A', Math.abs('A'+26-d));
        }
        
        int minlen= name.length()-1;
        int end, cnt;
        for(int i=0; i<name.length(); i++){
            if(name.charAt(i)=='A') continue;
            end= i+1;
            while(end<name.length()&&name.charAt(end)=='A'){
                end++;
            }
            cnt=i*2+(name.length()-end);
            minlen= Math.min(minlen, cnt);
        }
        
        return answer+minlen;
    }
}

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

[문제 설명]

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

​

[제한 사항]

numbers의 길이는 1 이상 100,000 이하입니다.

numbers의 원소는 0 이상 1,000 이하입니다.

정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

​

<입출력 예>

>문제 풀이

문제의 숫자가 꼭 한자릿수만 나오는게 아니기 때문에 잘 생각해야합니다.

예를 들어 만약 10, 6 의 경우 610> 106 이기 때문에 마냥 배열을 오름차순으로 정렬할 수 없습니다.

그래서 숫자를 정렬할 때 comparator을 써서 10 과 6을 붙여본 결과를 비교하여 오름차순으로 정렬 했습니다. 106과 610을 비교한 결과로 정렬을 하는 것이죠.

        Arrays.sort(str, new Comparator<String>(){ //정렬하기
            public int compare(String o1, String o2){
                return -(o1+o2).compareTo(o2+o1);
            }
        });

>전체 코드

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        String[] str= new String[numbers.length];
        
        int j=0;
        for(int i: numbers){
            str[j++]= String.valueOf(i);
        }
        
        Arrays.sort(str, new Comparator<String>(){
            public int compare(String o1, String o2){
                return -(o1+o2).compareTo(o2+o1);
            }
        });
        
        for(String i: str){
            answer+=i;
        }
        
        for(int i=0; i<answer.length(); i++){
            if(answer.charAt(i)!='0'||i==answer.length()-1){
                answer= answer.substring(i);
                break;
            }
        }
        
        return answer;
    }
}

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