프로그래머스 방문 길이 c++

https://www.geeksforgeeks.org/unordered_set-in-cpp-stl/

Unordered Sets in C++ Standard Template Library - GeeksforGeeks

 

중복을 허용하지 않고, 순서가 없으며, 속도가 O(1) ~ O(n), 해시 테이블 기반으로 구현되어 있다.

 

https://namu.wiki/w/%ED%95%B4%EC%8B%9C

해시

 

long long path1,path2에 저런 식으로 값을 저장하는 것은 고유한 값을 할당해 경로 구분 및 중복 방지를 하려고 한 것이다.

로직에 1,000을 곱했을 때는 모든 테스트 케이스를 통과하지 못해서 100,000 || 10,000으로 바꿔 테스트를 통과했다.

 

"ULURRDLLU"

U	L	...
x=0, y=0 nx=0, ny=1 path1=1 path2=1000 visited {1,1000}	x=0, y=1 nx=-1, ny=1 path1=901 path2=-8999	...

이런 식으로 값을 저장하고 x,y를 nx,ny(움직인 좌표)로 다시 설정해 주는 코드이다.

 

path1은 (x,y)->(nx,ny) / path2는 (nx,ny)->(x,y)

문제에서 "처음 지나본 길만" 이라는 문장이 있기에 양방향으로 카운팅을 해줘 중복을 제거

양방향으로 길이 저장되어 있기에 마지막에 2로 나눠준다.

#include <unordered_set>
#include <string>
using namespace std;

int solution(string dirs) {
    unordered_set<long long> visited;
    int x = 0, y = 0;

    for (char dir : dirs) {
        int nx = x, ny = y;
        if (dir == 'U' && y < 5) ny++;
        else if (dir == 'D' && y > -5) ny--;
        else if (dir == 'R' && x < 5) nx++;
        else if (dir == 'L' && x > -5) nx--;

        if (nx != x || ny != y) {
            long long path1 = (long long)x * 10000 + y * 1000 + nx * 100 + ny;
            long long path2 = (long long)nx * 10000 + ny * 1000 + x * 100 + y;

            visited.insert(path1);
            visited.insert(path2);

            x = nx;
            y = ny;
        }
    }

    return visited.size() / 2;
}