C++ 코딩테스트 강좌, DDR을 해보자

문제 설명

DDR은 Dance Dance Revolution의 약자로, 플레이어는 화면에 나타나는 화살표에 맞춰서 발을 움직이며 춤을 춥니다.
이 자료구조 및 알고리즘 문제에서는 DDR에서 발생할 수 있는 특정한 상황을 시뮬레이션하고,
입력으로 주어진 화살표 패턴을 기반으로 적절한 움직임을 계산하는 프로그램을 작성해야 합니다.

문제: 주어진 문자열은 화살표 패턴을 나타냅니다. 배열의 각 원소는 화살표의 방향을 나타내며,
‘U’는 위, ‘D’는 아래, ‘L’은 왼쪽, ‘R’은 오른쪽을 의미합니다.
플레이어는 적어도 K개의 화살표를 처리해야 하며, 중복 화살표는 무시해야 합니다.
플레이어가 움직인 방향의 개수를 반환하는 프로그램을 작성하세요.

입력: 문자열과 정수 K (1 ≤ K ≤ 1000)

출력: 플레이어가 움직인 방향의 개수

문제 분석

주어진 문제를 잘 이해하기 위해서는 각 화살표가 어떤 방향으로 가리키는지를 명확히 알고 있어야 합니다.
우리는 중복된 화살표를 고려하지 않아야 하며, 따라서 문자열을 처리하면서 중복된 요소를 원래의 순서대로
고려할 수 있는 데이터 구조가 필요합니다.
화살표의 개수는 유한하며 대문자 ‘U’, ‘D’, ‘L’, ‘R’로만 이루어져 있기 때문에 이 문제는 간단한 문자열 처리로 해결할 수 있습니다.

접근 방법

문제에 접근하기 위해 다음의 단계를 고려할 수 있습니다:

주어진 문자열을 순회하여 각 화살표를 확인합니다.
각 화살표를 Set에 추가하여 중복된 화살표를 자동으로 제거합니다.
Set의 크기를 확인하여 플레이어가 실제로 움직인 방향의 개수를 계산합니다.

이 접근 방법은 시간 복잡도가 O(n)이며, n은 주어진 문자열의 길이입니다.
Set을 사용하면 중복을 처리하는 것이 용이하고, 최종적으로 Set의 크기를 얻는 것은 O(1)입니다.

C++ 코드 구현


#include 
#include 
#include 

int processArrows(const std::string &arrows, int K) {
    std::unordered_set uniqueArrows;
  
    // 각 화살표를 순회하면서 Set에 추가
    for (char arrow : arrows) {
        uniqueArrows.insert(arrow);
    }
  
    // K보다 적은 경우에도 상관 없이 Set의 사이즈를 리턴
    return uniqueArrows.size();
}

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

    std::cout << "화살표 패턴을 입력하세요: ";
    std::getline(std::cin, arrows);
    std::cout << "K 값을 입력하세요: ";
    std::cin >> K;

    int result = processArrows(arrows, K);
    std::cout << "플레이어가 움직인 방향의 개수: " << result << std::endl;

    return 0;
}

코드 설명

위의 C++ 코드는 문제 해결을 위한 간단한 시뮬레이션을 수행합니다.
processArrows 함수는 String과 K를 인자로 받아 화살표를 처리하는 역할을 합니다.
여기서는 unordered_set를 사용하여 중복을 자동으로 제거하고 있습니다.

먼저, 주어진 화살표 문자열을 한 글자씩 순회하면서 각 화살표를 Set에 추가합니다.
Set은 중복된 요소를 허용하지 않기 때문에, 최종적으로 Set의 크기를 통해 플레이어가 실제로
움직인 방향의 개수를 파악할 수 있습니다.

main 함수에서는 사용자로부터 화살표 패턴과 K 값을 입력받고,
그 값을 processArrows 함수에 넘겨 결과를 최종 출력합니다.

결론

본 포스팅에서는 C++를 활용하여 DDR 게임의 간단한 알고리즘 문제를 해결하는 과정을 설명하였습니다.
문제를 단계별로 분석하고 접근 방법을 논의한 후, 최종적으로
효과적인 코드 구현을 통해 문제를 해결할 수 있었습니다.
이러한 접근 방식은 코딩 테스트에서 다루어야 할 여러 알고리즘 문제를 해결하는 데 매우 유용합니다.

문제 설명

문제 분석

접근 방법

C++ 코드 구현

코드 설명

결론

관련