[BOJ] 2659 : 십자카드 문제 - java

문제

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

---

문제풀이

1 이상 9 이하의 숫자 4개가 시계 방향으로 입력되므로 범위는 1111~9999가 된다.
'시계수'란 숫자들의 시작점을 시계방향으로 바꿔가며 나온 수 중에 가장 작은 수를 뜻한다.

시계방향이라는 규칙이 큐를 활용해도 된다고 판단하였다.
ex) 1 2 2 1 -> 2 2 1 1 -> 2 1 1 2 -> 1 1 1 2
와 같이 (큐의 길이 - 1) 반복하며 최소 숫자(시계수)를 구하는 메서드(findClockNum)를 생성했다.

예제와 같이 2 1 1 2 가 입력된다면 시계수는 1122가 되며
1111 ~ 1122까지의 숫자 중 0을 포함한 숫자와 1121(이 숫자의 시계수는 1112이다)과 같이 시계수가 아닌 수 를 제외하여 카운트를 센다.

---

소스코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;
 
public class _2659 {
 
    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());
        String N = "";
        for (int i = 0; i < 4; i++) {
            N += st.nextToken();
        }
 
        int inputNum = findClockNum(N);
 
        int cnt = 1;
        for (int k = 1111; k <= inputNum; k++) {
            if (k == inputNum) {
                bw.write(cnt + "");
                break;
            }
            // 숫자에 0이 포함되지 않고 해당 숫자가 시계수인경우 카운트 증가
            if (!String.valueOf(k).contains("0") && findClockNum(String.valueOf(k)) == k) {
                cnt++;
            }
        }
 
        br.close();
        bw.flush();
        bw.close();
    }
 
	// 시계수 구하기
    static int findClockNum(String s) {
        int min = Integer.parseInt(s);
 
        Queue<String> q = new LinkedList<>();
 
        for (int i = 0; i < s.length(); i++) {
            q.add(String.valueOf(s.charAt(i)));
        }
 
        for (int j = 1; j < q.size(); j++) {
            q.add(q.remove());
            int nowNum = Integer.parseInt(q.stream().collect(Collectors.joining("")));
            min = min > nowNum ? nowNum : min;
        }
 
        return min;
    }
}

        

        
      

---

소스코드 (메모리 사용량 줄인 ver)

import java.io.*;
import java.util.StringTokenizer;
 
public class _2659 {
    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());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 4; i++) {
            sb.append(st.nextToken());
        }
 
        int inputNum = findClockNum(sb.toString());
 
        int cnt = 1;
        for (int k = 1111; k < inputNum; k++) {
            if (containsZero(k)) continue;
            if (findClockNum(String.valueOf(k)) == k) {
                cnt++;
            }
        }
 
        bw.write(cnt + "");
        bw.flush();
        br.close();
        bw.close();
    }
 
    static boolean containsZero(int num) {
        while (num > 0) {
            if (num % 10 == 0) return true;
            num /= 10;
        }
        return false;
    }
 
    static int findClockNum(String s) {
        int min = Integer.parseInt(s);
        for (int i = 1; i < 4; i++) {
            s = s.substring(1) + s.charAt(0);
            int rotatedNum = Integer.parseInt(s);
            if (rotatedNum < min) {
                min = rotatedNum;
            }
        }
        return min;
    }
}

        

        
      

1. StringBuilder : StringBuilder입력 토큰을 연결하는 데 사용되며, 문자열을 직접 연결하는 것보다 더 효율적이다.
2. 회피된 큐 및 스트림 : 큐 및 스트림 작업을 하위 문자열 작업을 사용하는 문자열의 간단한 회전으로 대체. 여러 문자열이 생성되는 것을 방지할 수 있다.
3. 0 확인 포함 : '0' 이 포함된 숫자를 건너뛰는 메서드(containsZero) 추가. 문자열을 반복적으로 확인하는 것보다 효율적이다.
4. 회전 논리 : 하위 문자열 연산을 직접 사용하도록 회전 논리를 단순화하여 메모리 오버헤드 감소, 코드 단순화

 

아래와 같이 메모리 사용량, 시간, 코드 길이가 감소한 효과를 볼 수 있었다.

---

etc

알고리즘이 브루트포스 알고리즘, 정렬로 분류된 문제였다. 브루트포스 알고리즘(유사 완전 탐색)으로 분류된 문제인 만큼 풀이하면서 높은 시간 복잡도가 발생할 수 있다. 좀 더 효율적인 방법으로 수정할 예정이다.

https://djun95.tistory.com/12

브루트포스 탐색 알고리즘

https://djun95.tistory.com/14

Queue(큐) 클래스 - JAVA