Java Coding Test Course, Let's Try DDR

Recently, algorithm problems have become one of the important factors in the job market. Understanding algorithms and data structures is essential, especially for software engineering positions. In this course, we will address algorithm problems under the topic “DDR (Dance Dance Revolution)”. DDR is a dance game where you need to step on the designated panels within a given time. We will transform this into a programming problem to study algorithms.

Problem Description

You have participated in the DDR challenge. Given the order of the panels that appear on the screen, you must step on them accurately. The panels are indicated by integers from 1 to 9, where 1 is the bottom left, 2 is the bottom center, 3 is the bottom right, 4 is the middle left, 5 is the center, 6 is the middle right, 7 is the top left, 8 is the top center, and 9 is the top right.

The time and distance to step on the panels may vary depending on where you currently have your feet. Therefore, you need to find the optimal path.

Input Format

The first line contains the number of panels N (1 ≤ N ≤ 1000). The second line provides N panels, with each panel represented by an integer between 1 and 9.

Output Format

Output the minimum time required to step on all the panels.

Example Problem

    
    Input:
    5
    1 3 5 7 9

    Output:
    8

Problem Solving Process

Step 1: Define Panel Coordinates

First, we need to define the positions of the panels. We can calculate the distances between the panels using a 2D array as follows.

    
    // Define the positions of the panels as (row, column)
    int[][] position = {
        {3, 1}, // 1
        {2, 1}, // 2
        {1, 1}, // 3
        {3, 2}, // 4
        {2, 2}, // 5
        {1, 2}, // 6
        {3, 3}, // 7
        {2, 3}, // 8
        {1, 3}  // 9
    };

Step 2: Implement Distance Calculation Function

We will use the Manhattan distance for the distance calculation. The Manhattan distance between two points (x1, y1) and (x2, y2) is defined as |x1 – x2| + |y1 – y2|. Let’s implement this as a Java function.

    
    public int calculateDistance(int a, int b) {
        int x1 = position[a - 1][0];
        int y1 = position[a - 1][1];
        int x2 = position[b - 1][0];
        int y2 = position[b - 1][1];
        
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }

Step 3: Implement Main Logic

Now, we will implement the main logic to calculate the optimal path to step on each panel once. We will calculate the distance between the current position and the target panel, then accumulate the minimum distance.

    
    public int minTime(int[] steps) {
        int totalTime = 0;
        int currentPosition = 5; // Initial panel is at position 5 (center)

        for (int step : steps) {
            totalTime += calculateDistance(currentPosition, step);
            currentPosition = step; // Update current position
        }
        return totalTime;
    }

Step 4: Full Code

Finally, we will write the complete code to receive panel information and calculate the minimum time.

    
    import java.util.Scanner;

    public class Main {
        static int[][] position = {
            {3, 1}, // 1
            {2, 1}, // 2
            {1, 1}, // 3
            {3, 2}, // 4
            {2, 2}, // 5
            {1, 2}, // 6
            {3, 3}, // 7
            {2, 3}, // 8
            {1, 3}  // 9
        };

        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int N = scanner.nextInt();
            int[] steps = new int[N];

            for (int i = 0; i < N; i++) {
                steps[i] = scanner.nextInt();
            }

            System.out.println(minTime(steps));
        }

        public static int minTime(int[] steps) {
            int totalTime = 0;
            int currentPosition = 5; // Initial panel is at position 5 (center)

            for (int step : steps) {
                totalTime += calculateDistance(currentPosition, step);
                currentPosition = step; // Update current position
            }
            return totalTime;
        }

        public static int calculateDistance(int a, int b) {
            int x1 = position[a - 1][0];
            int y1 = position[a - 1][1];
            int x2 = position[b - 1][0];
            int y2 = position[b - 1][1];
            
            return Math.abs(x1 - x2) + Math.abs(y1 - y2);
        }
    }

Conclusion

In this course, we learned about the positions of the panels and distance calculations through a simple algorithm problem. This type of problem often appears in actual coding tests. By solving various algorithm problems, you can naturally enhance your understanding of data structures and algorithms. We hope you continue to solve many problems and gain experience!

Java Coding Test Course, Let’s Try DDR