[백준](2024) 행운의 바퀴 (설명/코드/정답)

 

문제 링크 : https://www.acmicpc.net/problem/2840

 

 

난이도		알고리즘
	실버4	구현, 시뮬레이션

 

 

1. 요구 사항 이해

시간, 메모리 제한 : 1초 / 128MB

 

돌린 횟수와 회전을 멈추었을 때 가리키던 글자를 통해 바퀴에 적힌 알파벳을 출력하라.

 

 

2. 설계/검증 

입력

- N : 칸수 (2 ≤ N ≤ 25)

- K : 반복 횟수 ( 1 ≤ K ≤ 100)

- S : 이동 횟수 

- A: 이동 완료 후 할당 값

 

설계 

 

행운의 바퀴

칸에 글자가 있는 상태

 

반복하며 1*N 배열에 값 입력

- 인덱스에 S%N 더한 값이 N보다 작으면 그냥 더한 값을 다음 인덱스로 하고

- 인덱스에 S%N 더한 값이 N보다 크면 그 값에 -N -1한 값을 다음 인덱스로 한다. 

 

행운의 바퀴 결정못함 vs 없음

- ? 결정 못 함 : 값이 한 번도 들어오지 않음 

 - ! 없음 : 다른 값이 들어옴

 

 

출력 

- 이동 완료 값부터 역순으로 나머지 값 모두 출력 

- ? : 어떤 글자인지 결정 못하는 칸 ? 

- ! : 행운의 바퀴 없음

시간 복잡도	최악의 경우	공간 복잡도
O(N)	40,320	O(N)

 

 

 

 

 

3. 정상 코드

import java.util.*;

public class Main {

        public static void main(String[] args) {

// 입력
            Scanner scan = new Scanner(System.in);

            int N = scan.nextInt(); // 바퀴의 칸 수
            int K = scan.nextInt(); // 회전 횟수

            char[] wheel = new char[N]; // 바퀴 배열 초기화
            Arrays.fill(wheel, '?'); // 모든 요소를 '?'로 초기화

// 설계
            int startIndex = 0; // 시작 인덱스 초기화
            // 회전 수행
            for (int i = 0; i < K; i++) {
                int S = scan.nextInt(); //회전 거리
                char A = scan.next().charAt(0); // 넣을 알파벳
                int currentIndex = (startIndex + S) % N; // 다음 인덱스 계산

                // 현재 인덱스가 '?'이거나 넣을 알파벳과 동일하면 삽입
                // 동일하지 않으면 '!'
                if (wheel[currentIndex] == '?' || wheel[currentIndex] == A)
                {
                    wheel[currentIndex] = A; }
                else {
                    wheel[currentIndex] = '!';
                }
                startIndex = currentIndex; // 시작 인덱스 업데이트
            }
// 출력

            // 결과 생성을 위한 Stringbuilder 사용
            StringBuilder result = new StringBuilder();

            // 올바른 순서로 재배열
            for (int i = 0; i < N; i++) {
                int index = (startIndex - i + N) % N; // 시작 인덱스에서 역순 계산
                result.append(wheel[index]); // 결과에 해당 인덱스의 알파벳 추가
            }

            // 결과에 '!'가 있으면 '!'출력, 없으면 결과 출력
            if (result.toString().contains("!")) {
                System.out.println("!");
            } else {
                System.out.println(result.toString());
            }
        }
    }

 

 

 

 

4. 처리 과정 추적 코드

import java.util.*;

public class Main {

    public static void main(String[] args) {

        // 입력
        Scanner scan = new Scanner(System.in);

        System.out.println("바퀴의 칸 수와 회전 횟수 입력: ");
        int N = scan.nextInt(); // 바퀴의 칸 수
        int K = scan.nextInt(); // 회전 횟수

        char[] wheel = new char[N]; // 바퀴 배열 초기화
        Arrays.fill(wheel, '?'); // 모든 요소를 '?'로 초기화

        // 설계
        int startIndex = 0; // 시작 인덱스 초기화

        // 회전 수행
        System.out.println("\n[회전 수행]----------------------------------");
        for (int i = 0; i < K; i++) {
            int S = scan.nextInt(); // 회전 거리
            char A = scan.next().charAt(0); // 넣을 알파벳
            int currentIndex = (startIndex + S) % N; // 다음 인덱스 계산

            System.out.println("회전 거리: " + S);
            System.out.println("넣을 알파벳: " + A);
            System.out.println("현재 인덱스: " + currentIndex);

            // 현재 인덱스가 '?'이거나 넣을 알파벳과 동일하면 삽입, 동일하지 않으면 '!'
            if (wheel[currentIndex] == '?' || wheel[currentIndex] == A) {
                wheel[currentIndex] = A;
            } else {
                wheel[currentIndex] = '!';
            }
            startIndex = currentIndex; // 시작 인덱스 업데이트

            // 현재 상태 출력
            System.out.println("현재 바퀴 상태: " + Arrays.toString(wheel));
        }

        // 출력
        System.out.println("\n[결과]----------------------------------");
        // 결과 생성을 위한 StringBuilder 사용
        StringBuilder result = new StringBuilder();

        // 올바른 순서로 재배열
        for (int i = 0; i < N; i++) {
            int index = (startIndex - i + N) % N; // 시작 인덱스에서 역순 계산
            result.append(wheel[index]); // 결과에 해당 인덱스의 알파벳 추가
        }

        // 결과에 '!'가 있으면 '!'출력, 없으면 결과 출력
        if (result.toString().contains("!")) {
            System.out.println("!");
        } else {
            System.out.println("결과: " + result.toString());
        }
    }
}

 

 

 

 

추가 정리

 

 

result.toString().contains("!")

문자열에 특정 문자열 또는 문자가 포함되어 있는지를 확인하는 데 사용

만약 포함되어 있다면 true를 반환하고, 그렇지 않으면 false를 반환