๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Programmers

[C++/PGS] Lv.5 : ๋ฐฉ์˜ ๊ฐœ์ˆ˜ (๊ทธ๋ž˜ํ”„)

728x90

https://school.programmers.co.kr/learn/courses/30/lessons/49190?language=cpp

 

๋ฌธ์ œ ์„ค๋ช…

์›์ (0,0)์—์„œ ์‹œ์ž‘ํ•ด์„œ ์•„๋ž˜์ฒ˜๋Ÿผ ์ˆซ์ž๊ฐ€ ์ ํžŒ ๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ•˜๋ฉฐ ์„ ์„ ๊ธ‹์Šต๋‹ˆ๋‹ค.

ex) 1์ผ๋•Œ๋Š” ์˜ค๋ฅธ์ชฝ ์œ„๋กœ ์ด๋™

๊ทธ๋ฆผ์„ ๊ทธ๋ฆด ๋•Œ, ์‚ฌ๋ฐฉ์ด ๋ง‰ํžˆ๋ฉด ๋ฐฉํ•˜๋‚˜๋กœ ์ƒ™๋‹ˆ๋‹ค.
์ด๋™ํ•˜๋Š” ๋ฐฉํ–ฅ์ด ๋‹ด๊ธด ๋ฐฐ์—ด arrows๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋ฐฉ์˜ ๊ฐฏ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•˜์„ธ์š”.

์ œํ•œ์‚ฌํ•ญ
  • ๋ฐฐ์—ด arrows์˜ ํฌ๊ธฐ๋Š” 1 ์ด์ƒ 100,000 ์ดํ•˜ ์ž…๋‹ˆ๋‹ค.
  • arrows์˜ ์›์†Œ๋Š” 0 ์ด์ƒ 7 ์ดํ•˜ ์ž…๋‹ˆ๋‹ค.
  • ๋ฐฉ์€ ๋‹ค๋ฅธ ๋ฐฉ์œผ๋กœ ๋‘˜๋Ÿฌ ์‹ธ์—ฌ์งˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 


 

๊ตฌํ˜„ ์ž์ฒด๋Š” ์–ด๋ ต์ง€ ์•Š๋‹ค.

 

๋‹ค๋งŒ ํ•œ๋ฒˆ ๋ฐฉ๋ฌธํ–ˆ๋˜ ๋…ธ๋“œ๋ฅผ ๋‹ค๋ฅธ ๊ฒฝ๋กœ์—์„œ ๋‹ค์‹œ ๋ฐฉ๋ฌธํ•˜๊ฒŒ ๋˜๋ฉด ๋ฐฉ์ด ๋งŒ๋“ค์–ด์ง€๋Š”๋ฐ,

map์„ ์‚ฌ์šฉํ•ด์„œ node, edge์˜ ๋ฐฉ๋ฌธ์„ ์ฒดํฌํ•˜๋Š” ๊ฑธ ๋– ์˜ฌ๋ฆฌ๋Š”๊ฒŒ ํž˜๋“ค์—ˆ์Œ

 

๋Œ€๊ฐ์„ ์œผ๋กœ ๊ฐ€๋กœ์ง€๋ฅด๋Š” X ๋ชจ์–‘์˜ ๋ฐฉ์ด ์ƒ๊ธธ ๊ฒฝ์šฐ๋ฅผ ์œ„ํ•ด

arrow ๊ฐ’์„ ๋‘๋ฒˆ ์ด๋™์‹œ์ผœ์ฃผ๋Š” ์•„์ด๋””์–ด๊ฐ€ ์ค‘์š”ํ•œ ๊ฒƒ ๊ฐ™๋‹ค.

์ด๊ฑด ๋‚˜๋„ ๊ตฌ๊ธ€๋งํ•ด์„œ ์•Œ์•„๋‚ธ๊ฑฐ....ใ…Ž

 

 

 

 ๋‚˜์˜ ํ’€์ด

#include <string>
#include <vector>
#include <map>
using namespace std;

int dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

int solution(vector<int> arrows) {
    map<pair<int, int>, bool> nodeVisited;
    map<pair<pair<int, int>, pair<int, int>>, bool> edgeVisited;
    int answer = 0;
    int x = 0;
    int y = 0;
    nodeVisited[{x,y}] = true;
    for (int i = 0; i < arrows.size(); i++){
        int dir = arrows[i];
        for (int j = 0; j < 2; j++){
            int nx = x+dx[dir];
            int ny = y+dy[dir];
            if(nodeVisited[{nx,ny}]==true && edgeVisited[{{x,y},{nx,ny}}]==false){
                answer++;
            }
            else {
                nodeVisited[{nx,ny}]=true;
            }
            edgeVisited[{{x,y},{nx,ny}}]=true;
            edgeVisited[{{nx,ny},{x,y}}]=true;
            x=nx;
            y=ny;
        }
    }
    return answer;
}

 

728x90