[코드포스 Practice16] D. Yet Another Walking Robot

이렇게 풀었는데 틀렸다ㅋㅋㅋ

내가 착각 했던 게 있었는데 난 중간에 종점이 겹치면 지워도 된다고 생각했다. 

근데 알고보니 중간에 한바퀴 도는 경우도 있었다. 

 

그래서 다시 코딩함...

 

 

하지만 시간 복잡도가 n^2이라 터졌다ㅋㅋㅋ

 

그래서 힌트 받아서 다시 구현했다. 

역좌표.. 신기하다.. 그리고 map.. 어렵다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
using namespace std;
using i64 = long long;
 
int main() 
{
    int t;
    scanf("%d", &t);
    
    for (int i = 0; i < t; i++)
    {
        int n;
        string s;
        cin >> n >> s;
        
        map<pair<int, int>, int> idx;
        int x = 0, y = 0;
        int l = n, r = n, len = n + 1;
        bool ischange = true;
        idx[{0, 0}] = 0;
        for (int j = 1; j <= n; j++)
        {
            if (s[j-1] == 'L')
                x--;
            else if (s[j-1] == 'R')
                x++;
            else if (s[j-1] == 'D')
                y--;
            else if (s[j-1] == 'U')
                y++;

            //없는 경우
            if (idx.find({x, y}) == idx.end())
            {
                idx[{x, y}] = j;
            }
            //있는 경우
            else
            {
                if (len > (j - idx[{x, y}]))
                {
                    len = j - idx[{x, y}];
                    l = idx[{x, y}] + 1;
                    r = j;
                    ischange = false;
                }
                idx[{x, y}] = j;
            }
            //cout << x << " " << y << endl;
        }
        
        if (ischange)
            printf("-1\n");
        else
            printf("%d %d\n", l, r);
    }
    
    return 0;
}

맞을 줄 알고 돌려봤는데 틀렸다ㅠㅠ 그것도 test6번에 668번 케이스에서.....

진짜 어디서 틀렸지 ???? 당황해서 막 문자열 오만거 다 돌려봤는데 못 찾았다. 

알고보니 로직에서 문제 있었다. 

똑같은 값이 나오면 len길이를 구한 다음 최소 길이를 갱신하기도 해야하지만

idx[]에 최근 인덱스로 갱신했어야 했다. 

이거 고쳤고 맞았음

후.... 어제오늘 D, E번만 몰아 풀고 있는데 DE 정말 어렵구나...