[백준 Java] 2659번 십자카드 문제 (중복순열, 구현, 브루트포스)

 

[Silver III] 십자카드 문제 - 2659

문제 링크

성능 요약

메모리: 15096 KB, 시간: 100 ms

분류

브루트포스 알고리즘, 구현, 정렬

문제 설명

위와 같은 십자모양의 한 장의 카드에서, 네 모서리에 1 이상 9 이하의 숫자가 하나씩 씌여 있다. 이 네 개의 숫자 중에는 같은 숫자도 있을 수 있다.

모든 가능한 십자 카드가 주어질 때, 각각의 카드는 다음과 같은 '시계수'라는 번호를 가진다. 시계수는 카드의 숫자들을 시계 방향으로 읽어서 만들어지는 네 자리 수들 중에서 가장 작은 수이다. 위 그림의 카드는 시계방향으로 3227, 2273, 2732, 7322로 읽을 수 있으므로, 이 카드의 시계수는 가장 작은 수인 2273이다.

입력으로 주어진 카드의 시계수를 계산하여, 그 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수인지를 알아내는 프로그램을 작성하시오.

예를 들어서, 다음과 같은 십자 카드의 시계수는 1122이며, 이 시계수보다 작은 시계수들은 1111, 1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119 뿐이므로 1122는 10번째로 작은 시계수다. (여기서 십자카드는 0 이 나타날 수 없으므로 1120은 시계수가 될 수 없다. 또한 1121 이 적혀있는 카드의 시계수는 1112이므로, 1121은 시계수가 될 수 없다.

입력

입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다.

출력

입력된 카드의 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수인지를 출력한다.

 

 

💡 나의 접근

이 문제의 분류에 왜 정렬이 있는지 잘 모르겠다.

정렬하지 않은 상태 즉, 문제에서 주어진 입력 상태 그대로 시계수를 찾아야 한다.

이유는 3 1 3 1의 시계수는 1313이다. 만약 입력을 정렬한다면 1 1 3 3 이 되고 이것의 시계수는 1133이 되기 때문에 잘못된 시계수를 찾게된다.

 

나의 풀이는 

먼저 주어진 입력의 시계수를 찾은 후 

1111 ~ 9999 까지의 모든 경우에서 시계수를 찾고

주어진 시계수보다 작다면 중복을 허용하지 않기 위해 HashSet에 넣어주었다. 

그리고 나서 set의 크기를 출력하였다.

 

 

💡 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	static int num[] = new int [4];
	static int clockNum;
	static int minNum;
	static HashSet<Integer> set = new HashSet<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < 4; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		//------입력
		
		clockNum = 	getClockNum(num);
		
		num = new int[]{ 1, 1, 1, 1};
		
		findSmallColockNum(0); 
		
		System.out.println(set.size());
	}
	
	//주어진 시계수보다 작은 시계수 찾는 함수
	static void findSmallColockNum(int cnt) {
		if(cnt >= 4) {
			int minNum = getClockNum(num);
			if(minNum <= clockNum) {
				set.add(minNum);
			}
			return;
		}
		
		for (int i = 1; i <= 9; i++) {
			num[cnt] = i;
			findSmallColockNum(cnt+1);
		}
		
		
	}

	//-----시계수 구하기
	static int getClockNum(int[] num) {
		int cNum = Integer.MAX_VALUE; // 시계수 초기화
		for (int i = 0; i < 4; i++) {
			int tempNum = 0;
			
			int idx = i;
			
			for (int j = 3; j >= 0; j--) {
				if(idx > 3) {
					idx= 0;
				}
				tempNum += num[idx++] * Math.pow(10, j);
			}
			if(cNum > tempNum) {
				cNum = tempNum;
			}
		}
		return cNum;
	}

}