[LeetCode] 1496. Path Crossing

https://leetcode.com/problems/path-crossing/description/

Path Crossing - LeetCode

leetcode - Path Crossing

문제 유형 : 수학, 구현

문제 난이도 : Easy

 

문제

Given a string path, where path[i] = 'N', 'S', 'E' or 'W', each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.

Return true if the path crosses itself at any point, that is, if at any time you are on a location you have previously visited. Return false otherwise.

 

N, E, S, W로 구성되는 path문자열이 있다. 각 방향의 이니셜이고, 각 방향으로 한 칸씩 움직인다.

당신은 0,0에서 출발한다. 

길이 기존 길과 교차한다면 true, 아니면 false를 반환하라.

 

풀이

실제로 코드를 구현하면 된다.

명령어대로 좌표이동을 구현하고, 방문 정보를 set을 이용하여 저장하고 찾는다.

문자열을 순회하면서 좌표이동을 하고, 기존에 방문했다면 true, 아니라면 false를 반환하라.

 

코드

C++

class Solution {
public:
    void move(char cmd, pair<int, int> &pos) {
        switch(cmd) {
            case 'N':
                pos.second++;
                return;
            case 'S':
                pos.second--;
                return;
            case 'E':
                pos.first++;
                return;
            case 'W':
                pos.first--;
                return;
        }
    }

    bool isPathCrossing(string path) {
        pair<int, int> pos = {0, 0};
        set<pair<int, int>> s;
        s.insert(pos);
        for(const auto &cmd : path) {
            move(cmd, pos);
            if(s.find(pos) != s.end()) return true;
            s.insert(pos);
        }
        return false;
    }
};