C++ Coding Test Course, Let's Try DDR

Problem Description

DDR stands for Dance Dance Revolution, where players move their feet to the arrows appearing on the screen while dancing.
In this data structure and algorithm problem, we need to simulate specific situations that may occur in DDR and
write a program to calculate the appropriate movements based on the given arrow pattern.

Problem: The given string represents an arrow pattern. Each element of the array indicates the direction of an arrow,
where ‘U’ means up, ‘D’ means down, ‘L’ means left, and ‘R’ means right.
The player must process at least K arrows while ignoring duplicate arrows.
Write a program that returns the number of distinct directions the player has moved.

Input: A string and an integer K (1 ≤ K ≤ 1000)

Output: The number of distinct directions the player has moved.

Problem Analysis

To understand the given problem clearly, we need to know exactly what direction each arrow points to.
We should not consider duplicate arrows, so we need a data structure that can keep the original order of elements while processing the string and removes duplicates.
Since the number of arrows is finite and consists only of uppercase ‘U’, ‘D’, ‘L’, ‘R’, this problem can be solved with simple string processing.

Approach

To approach the problem, we can consider the following steps:

Traverse the given string to check each arrow.
Add each arrow to a Set to automatically remove duplicate arrows.
Check the size of the Set to calculate the number of distinct directions the player has actually moved.

This approach has a time complexity of O(n), where n is the length of the given string.
Using a Set makes it easy to handle duplicates, and obtaining the final size of the Set is O(1).

C++ Code Implementation


#include 
#include 
#include 

int processArrows(const std::string &arrows, int K) {
    std::unordered_set uniqueArrows;
  
    // Traverse each arrow and add to the Set
    for (char arrow : arrows) {
        uniqueArrows.insert(arrow);
    }
  
    // Return the size of the Set regardless of whether it is less than K
    return uniqueArrows.size();
}

int main() {
    std::string arrows;
    int K;

    std::cout << "Enter the arrow pattern: ";
    std::getline(std::cin, arrows);
    std::cout << "Enter the value of K: ";
    std::cin >> K;

    int result = processArrows(arrows, K);
    std::cout << "Number of distinct directions the player has moved: " << result << std::endl;

    return 0;
}

Code Explanation

The above C++ code performs a simple simulation to solve the problem.
The processArrows function takes a String and K as arguments and handles the arrows.
Here, we use unordered_set to automatically remove duplicates.

First, we traverse the given arrow string character by character and add each arrow to the Set.
Since the Set does not allow duplicate elements, we can determine the number of distinct directions the player has
actually moved by checking the final size of the Set.

The main function takes the arrow pattern and K value as input from the user,
passes these values to the processArrows function, and finally prints the result.

Conclusion

In this post, we explained the process of solving a simple algorithm problem related to the DDR game using C++.
We analyzed the problem step-by-step, discussed the approach, and ultimately
solved the problem through effective code implementation.
This approach is very useful for solving various algorithm problems that need to be addressed in coding tests.

C++ Coding Test Course, Let’s Try DDR