Programmers - 방문 길이

---

title: Programmers - 방문 길이
date: 2022-07-14
tags:

• Algorithm

---

https://school.programmers.co.kr/learn/courses/30/lessons/49994

문제 요약

0,0 기준으로 상하좌우로 5씩 경계가 있는 좌표평면에서 이동이 주어진다.
각 이동을 수행하며 처음 걸어본 길의 수를 count하고, 이를 return한다.

문제 풀이

최대 길이는 500, 좌표 평면이 좌표의 개수는 121개이다. 중복되는 진행이 많이 나올 것으로 예상이 되었다.
vector에 전부 때려넣어 마지막에 중복 제거 / unordered_map에 전부 넣어 순회하기. 라는 두 가지 방법을 생각하였다.
전자의 경우, 정렬 과정에서 O(nlogn)이지만, 후자의 경우 1번만 순회하면 되기에 O(n)이다. 고로 unordered_map을 사용하였다.

현재 위치와 이동한 위치를 저장한다. 음수를 없애면 0~10 사이의 범위이므로 각 4비트씩 할당하면 된다.
총 16비트에 위치 정보를 넣어 unordered_map에 저장한다.
또한 이 과정에서 문제가 있었다.

초기 알고리즘은 [ Former << ... , Current ] 순서이다.
하지만 길의 경우 양방향이기에, 추후 Current 위치에서 Former 위치로 이동하여도 같은 길로 인식하여야 한다.
효율적인 알고리즘을 고민하였고, 대소 비교 등을 이용하는 것 보다는 무식하게 때려넣는 것이 낫다고 판단하였다.
Former -> Current, Current -> Former 전부 count한다. 그러면 지난 길의 개수 * 2 만큼의 값이 나올 것이다.
그러므로 해당 값 / 2 가 정답이라는 것이다.
unordered_map을 순회하려고 하였으나, size 함수를 이용하면 되기에 쉽게 문제를 해결하였다.

프로그램

#include <string>
#include <unordered_map>

using std :: string ;
using std :: unordered_map ;

int solution ( string dirs )
{
    int answer = 0 ;
    unordered_map < int , int > umCoordinate ;
    int iX = 0 ;
    int iY = 0 ;
    const char * cpTemp = dirs.data () ;
    int iSize = dirs.size () ;



    for ( int i = 0 ; i < iSize ; ++i )
    {
        int iTempX = iX + 5 ;
        int iTempY = iY + 5 ;

        if ( 'U' == cpTemp [ i ] )
            ++ iY ;
        else if ( 'D' == cpTemp [ i ] )
            -- iY ;
        else if ( 'L' == cpTemp [ i ] )
            -- iX ;
        else if ( 'R' == cpTemp [ i ] )
            ++ iX ;

        if ( ( iY < -5 ) || ( iX < -5 ) || ( 5 < iY ) || ( 5 < iX ) )
        {
            iX = iTempX - 5 ;
            iY = iTempY - 5 ;

            continue ;
        }

        ++ umCoordinate [ ( iTempX << 12 ) + ( iTempY << 8 ) + ( ( iX + 5 ) << 4 ) + ( iY + 5 ) ] ;
        ++ umCoordinate [ ( ( iX + 5 ) << 12 ) + ( ( iY + 5 ) << 8 ) + ( iTempX << 4 ) + iTempY ] ;
    }


    return umCoordinate.size () >> 1 ;
}