[JAVA] 2659번 - 십자카드 문제

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

문제를 2개로 나눠서 생각했다.

① 십자카드에서 시계수를 구한다

② 1111부터 9999까지 중에서 해당 시계수가 몇번째로 오는지 구한다

 

 

 

① 시계수 구하기

시계방향으로 한칸씩 밀면서 나오는 숫자들 중에서 가장 작은 수가 시계수이다.

반복문을 돌리면서 한칸씩 밀면서 숫자들을 비교해서 제일 작은 값을 구하면 된다.

 

 

② 몇 번째로 작은 시계수인지 구하기

<처음 했던 생각- 1111부터 9999까지 모든 숫자 탐색>

1111부터 9999까지 반복문을 돌려서 모든 4자리수의 조합을 구한다(0제외)

그리고 제일 작은 수부터 반복문을 돌려 해당 시계수가 나올때까지 카운트한다.

<두번째 생각 - 주어진 시계수보다 작은 시계수 바로 찾기>

1111부터 입력으로부터 구한 시계수까지 반복문을 돌린다.

1111부터 몇 개의 시계수가 있는지 카운트, 시계수가 자기 자신과 같은지 여부만 체크한다.

 

 

 

시간복잡도

① 시계수 구하기

4번 반복하니까 상수 시간 O(1)

 

② 몇 번째로 작은 시계수인지 구하기

1111부터 최대 9999까지이다. O(N)이다.

 

최대 O(8889)이라서 시간내에 충분히 가능하다. 

 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. 시계수 구하기

반복문을 통해 배열을 오른쪽(시계방향)으로 한칸씩 밀면서 그때 숫자를 sb에 넣는다.

sb를 int로 바꿔 숫자를 구할때 마다 min함수로 비교해서 시계수를 찾는다.

static int getClockNum(int[] arr) {
    	 int num = 10000;      
         StringBuilder sb;
         for(int i=0; i<4; i++) {
         	sb = new StringBuilder();
         	for(int j=0; j<4; j++) {
         		sb.append(arr[(i + j) % 4]);    		
         	}
         	int cur = Integer.parseInt(sb.toString());
     		num = Math.min(cur, num);
         } 
         return num;
    }

 

 

2. 가장 작은 시계수 찾기 

1111부터 9999까지 탐색하지 않고, 내 시계수까지만 탐색했다. 어차피 그 이상은 답이 될 수 없기때문

1) 1111부터 내 시계수까지 탐색한다

2) 0인경우는 패스

3) 4자리수를 1의자리부터 반복문을 통해 채워서 4자리수를 만든다.

4) 해당 숫자의 조합에서 생성된 시계수가 자기 자신과 같으면 카운트

static void findSmallClockNum() {
    	//전체 4자리 숫자들중에서 몇번째에 해당하는지 찾기
        for(int i=1111; i<=clockNum; i++) {
        	if(String.valueOf(i).contains("0")) continue;
        	
        	//4자리수 1111부터 9999까지 
        	int[] digit = new int[4];
        	int k = i;
        	for(int j=3; j>=0; j--) {
        		digit[j] = k%10;
        		k/=10;
        	}
        	 if (getClockNum(digit) == i) ans++; 
        }   	
    }

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	static int clockNum;
	static int ans = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int []arr = new int[4];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<4; i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        
         clockNum = getClockNum(arr);
         findSmallClockNum();
         System.out.println(ans);
        
    }	
    
    //시계수 구하기 
    static int getClockNum(int[] arr) {
    	 int num = 10000;      
         StringBuilder sb;
         for(int i=0; i<4; i++) {
         	sb = new StringBuilder();
         	for(int j=0; j<4; j++) {
         		sb.append(arr[(i + j) % 4]);    		
         	}
         	int cur = Integer.parseInt(sb.toString());
     		num = Math.min(cur, num);
         } 
         return num;
    }
    
    
    //시계수보다 작은 
    static void findSmallClockNum() {
    	//전체 4자리 숫자들중에서 몇번째에 해당하는지 찾기
        for(int i=1111; i<=clockNum; i++) {
        	if(String.valueOf(i).contains("0")) continue;
        	
        	//4자리수 1111부터 9999까지 
        	int[] digit = new int[4];
        	int k = i;
        	for(int j=3; j>=0; j--) {
        		digit[j] = k%10;
        		k/=10;
        	}
        	 if (getClockNum(digit) == i) ans++; 
        	

        }
    	
    }
}