24001. 로봇 언어

문제 출처 :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AZVqPrHaAy_HBIOy

[문제 설명]

'L', 'R', '?' 3가지 명령이 있다.

'L'은 왼쪽, 'R'은 오른쪽, '?'는 양쪽 다 가능하며 사용자가 지정해야 된다.

'?'를 정하는 기준은 원점에서 가장 먼 거리를 이동하는 경우를 정해야 한다.

참고로 최종 도착지가 최대 거리가 아니다.

예를 들어, LLLRR이면 -3 ~ 0 사이를 이동한다.

이 경우에 최종 도착점은 -1이다. 최대 거리는 도착점이 -3일 때 거리인 3이다.

 

[접근 방법]

1. 그리디

만약, 최종 도착점이 최대 거리인 경우라면 그리디로 풀 수 있다. 'L'과 'R' 둘 중에서 가장 많이 나온 명령어를 사용하면 된다.

예를 들어, 'LLLR'이면 L이 3개 R이 1개이므로 L을 1개 추가한다. 최종적으로 L이 4개 R이 1개로 개수 차이인 3이 된다.

최종 위치를 구하는 거라면 경로는 고려할 필요가 없다. 단순히 큰 쪽을 더 크게 만들면 된다.

그러나, 문제에선 최종 도착지가 아닌 모든 경로 중에서 가장 먼 거리를 구해야 한다.

 

2. 완전탐색

?가 나온다면 'L'인 경우와 'R'인 경우 모두 구하면 된다. 그러나, 이 방법의 시간복잡도는 O(2^문자열의 길이)가 된다.

문자열은 최대 50자이므로 2^50이다. 50 * log2 === 50 * 0.3010.. = 15.xx => 16자리수가 된다. 즉, 10^16에 가까운 연산 횟수가 발생한다. 따라서, 해당 방법으론 주어진 시간 내 해결이 불가능하다.

 

3. 완전탐색 + 동적프로그래밍

언뜻 보면 완전 탐색은 불가능해 보이지만 발상을 전환하면 충분히 가능하다. 경로가 아닌 도착 지점을 기준으로 두는 방법이다.

문자열의 길이는 최대 50이므로 도착할 수 있는 지점은 -50에서 50 사이다.

따라서, dp 배열로 해결이 가능하다.

dp[현재까지 확인한 문자의 개수][현 시점에서 갈 수 있는 위치의 인덱스]가 된다.

 

L?R을 예로 들겠다.

우선, 첫 시작인 dp[0]은 모두 동일하다. 문자열을 확인하지 않았으므로 원점에서 로봇이 출발한다.

따라서, dp[0]은 [0]으로 이뤄진다. 이제 다음 문자열인 'L'을 확인하겠다.

'L'은 왼쪽으로 이동하므로 dp[1]은 [-1]이 된다. 다음 문자열인 '?'를 확인하겠다.

'?'는 'L'이나 'R'과 달리 양쪽으로 모두 이동이 가능하다. 따라서, -1을 기준으로 왼쪽인 -2와 오른쪽인 0이 들어간다.

마지막으로 'R'은 오른쪽이므로 -2 기준 오른쪽인 -1과 0 기준 오른쪽인 1이 들어간다.

 

dp[x]에 중복된 원소는 들어갈 필요가 없다. 현재까지 오는 과정에서 왼쪽 끝으로 갔든 오른쪽으로 갔든 현재 위치가 'y'라면 'y'인 것이다. L?R?를 보면 이해가 가능하다.

dp[3]에선 -1과 1에 위치했으며 다음 문자열은 ?이므로 모두 좌우 이동이 가능하다.

기존 완전탐색 방법에 의하면 두 가지 모든 경우를 넣는다. 그러므로 -1 기준 좌우인 [-2, 0]과 1 기준 좌우인 [0, 2]가 모두 들어가서 최종적으로 dp[4]는 [-2, 0, 0, 2]가 들어간다.그러나, 딱 봐도 중복은 의미가 없다. 몇 번을 뽑았든 현재 위치가 거기라면 탐색을 나눠서 할 필요가 없다.

즉, 중복을 허용하지 않으므로 [-2, 0, 2]가 된다. 중복 여부 파악은 set 자료구조를 사용하여 O(1)로 간단히 해결 가능하다. (리스트나 배열을 사용한다면 시간복잡도가 더 커진다.)

 

T = int(input())
for test_case in range(1, T + 1):
    str = input()
    dp = [set() for _ in range(len(str) + 1)]
    dp[0].add(0)
    
    for idx in range(len(dp) - 1):
        set_of_cur_positions = dp[idx]
        for cur_position in set_of_cur_positions:
            if str[idx] == 'L':
                dp[idx + 1].add(cur_position - 1)
            elif str[idx] == 'R':
                dp[idx + 1].add(cur_position + 1)
            elif str[idx] == '?':
                dp[idx + 1].add(cur_position -1)
                dp[idx + 1].add(cur_position + 1)
                
    answer = 0
    for set_of_cur_positions in dp:
        for distance in set_of_cur_positions:
            if answer < abs(distance):
                answer = abs(distance)
    print(f"{answer}")