[백준/Java] 2659번 : 십자카드 문제

🌵 문제 분석

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

시계수란 1~9 중 중복 포함 4개의 숫자가 주어졌을 때 그 숫자를 시계방향으로 읽어 만들 수 있는 가장 작은 값이다. 

주어진 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수인지 출력하라.

 

🌵 구현 아이디어

1️⃣ 1111~9999로 만들 수 있는 모든 시계수를 구한다.

1111부터 1씩 증가시키면서 9999까지 모든 네 자리 수에 대한 시계수를 구한 후 중복 없이 배열에 저장한다. 

예를 들어 4265이 주어지면 4265, 2654, 6542, 5426 중에서 가장 작은 2654를 시계수로 배열에 저장한다.

2️⃣ 구한 시계수들을 오름차순으로 정렬한다.

3️⃣ 주어진 시계수를 구하고, 그 시계수가 몇 번째 위치인지 구한다.

 

문제에서 2112가 주어졌다면 시계수는 2112, 1122, 1221, 2211 중 1122이다. 

배열을 앞에서부터 순회하면서 1122보다 작은지 확인한 후 몇 번째 위치인지 구한다.

 

🌵 시간 복잡도

1111~9999까지 모든 수를 N개, 시계수를 총 M개라고 하면

 

모든 시계수 찾기 : O(N)*O(1)

시계수를 오름차순 정렬 : O(MlogM)

시계수 위치 찾기 : O(M)

 

전체 시간 복잡도는 O(N)+O(MlogM)+O(M) N은 최대 8889, M은 최대 500개이므로

1초 안에 연산 가능하다.

🌵 알고리즘

구현

🌵 코드 설계

 

• 입력값 받기
  • a b c d를 받고 하나의 정수로 변환한다.
• 모든 가능한 시계수를 구하기
  • 1111부터 9999까지 모든 수에 대해 시계수인지 확인하고 Set<Integer>clockNumbers에 중복 없이 저장한다.
• 입력값의 시계수를 구하고 몇 번째인지 찾기
  • 입력값을 시계수로 변환한 뒤, 전체 시계수 목록에서 몇 번째인지 찾는다.
• 시계수를 구하는 함수 getClockNumber()
  • 네 자리 숫자를 회전하며 만들 수 있는 4개의 숫자 중 가장 작은 값을 찾는다.

 

🌵 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        //정수로 변환
        int targetNumber = a * 1000 + b * 100 + c * 10 + d;

        System.out.println(findClockNumberOrder(targetNumber));
    }
    //네 자리 수에서 시계수를 구하는 함수
    public static int getClockNumber(int num) {
        String numStr = String.valueOf(num);
        int minValue = num;

        // 숫자를 4번 회전하며 최소값 찾기
        for (int i = 0; i < 4; i++) {
            numStr = numStr.substring(1) + numStr.charAt(0); // 왼쪽으로 회전
            minValue = Math.min(minValue, Integer.parseInt(numStr));
        }
        return minValue; // 가장 작은 값이 시계수
    }

    // 입력된 숫자가 시계수 목록에서 몇 번째인지 찾는 함수
    public static int findClockNumberOrder(int target) {
        Set<Integer> clockNumbers = new HashSet<>();

        // 1111 ~ 9999까지 모든 숫자에 대해 시계수 찾기
        for (int i = 1111; i <= 9999; i++) {
            if (!String.valueOf(i).contains("0")) { // 숫자에 0이 포함되면 안 됨
                clockNumbers.add(getClockNumber(i));
            }
        }

        // 정렬 후 몇 번째인지 찾기
        List<Integer> sortedClockNumbers = new ArrayList<>(clockNumbers);
        Collections.sort(sortedClockNumbers);

        return sortedClockNumbers.indexOf(getClockNumber(target)) + 1;
    }


}