BOJ 2659 십자카드 문제 (Java)

문제 탐색하기

• 십자모양의 한 장의 카드에서, 네 모서리에 1 이상 9 이하의 숫자가 하나씩 씌여 있다.
  • 네 개의 숫자 중에는 같은 숫자도 있을 수 있다.
• 시계수는 카드의 숫자들을 시계 방향으로 읽어서 만들어지는 네 자리 수들 중에서 가장 작은 수이다.
• 주어진 카드의 시계수를 계산하여, 그 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수를 출력하라.

코드 설계하기

구현 방법

1. 입력받은 카드에 의해 가능한 시계수의 최솟값을 찾는다.
   • 시계수 계산 로직 : 회전에 해당하는 4가지 정수 값의 경우의 수를 모두 대입해, 그 중 최솟값을 찾으면 된다.
2. 1111부터 9999까지 0이 포함되지 않은 수에 대해 시계수를 구한다.
   • 이미 나온 시계수인지(중복인지)를 체크한다.
   • 처음 나오는 시계수면 카운트를 1 증가시킨다.
   • 만약 그 시계수가 ‘입력으로부터 구한 시계수’와 같다면 그때의 카운트를 출력하고 종료한다.

1111 ~ 9999까지 전부 탐색해 봐야 한다. ( = Brute Force)

시간 복잡도

• 시계값 계산을 위해 순회하는 횟수만큼, O(N) = 9999 - 1111 = 8889 이다.
  • 시간 내에 충분히 연산이 가능하다.

정답 코드 (Java)

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

public class Main {
    private static int cnt = 0;
    private static int number;
    private static boolean[] visited = new boolean[10000];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int w = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        int z = Integer.parseInt(st.nextToken());

        number = calcNumber(w, x, y, z);

        for (int i = 1111; i <= number; i++) {
            String tmp = Integer.toString(i);
            int tmpNum = calcNumber(tmp.charAt(0) - '0', tmp.charAt(1) - '0', tmp.charAt(2) - '0', tmp.charAt(3) - '0');
            // 이미 앞에서 나온 시계수이거나 0을 포함하는 경우
            if (tmp.contains("0") || visited[tmpNum]) continue;

            visited[tmpNum] = true;  // 중복 확인 체크
            cnt++;                   // 새로운 시계수이므로 카운트 증가
            if (tmpNum == number) {  // 입력 시계수와 같으면 break
                break;
            }

        }
        bw.write(cnt + "\n");
        bw.flush();
        br.close();
        bw.close();
    }

    // 시계수 계산 로직
    private static int calcNumber(int a, int b, int c, int d) {
        int res = Integer.MAX_VALUE;
        res = Math.min(res, a * 1000 + b * 100 + c * 10 + d);
        res = Math.min(res, b * 1000 + c * 100 + d * 10 + a);
        res = Math.min(res, c * 1000 + d * 100 + a * 10 + b);
        res = Math.min(res, d * 1000 + a * 100 + b * 10 + c);

        return res;
    }
}