메모장

park의 위치를 문자열로 준것을 보고 2차원 배열을 이용하자 생각했고

routes의 문자열로 방향과 이동거리를 주는것을보고 문자열을 쪼갤때 많이 쓰는 <sstream>헤더를 활용하자 생각을 하였다.

또한 각 방향에 따라 수치들이 변경되는게 많아 define을 사용하여 매크로 상수화 했다.

(enum 쓰는게 가독성이 올라가는데 문제라서 그냥 define으로 하였다.)

이동 할떄 사용한 정보(경로)를 기록할 필요가 없어 전부 for 반복문 안에 지역변수로 활용하였다.

이 문제의 제일 중요한 것은 '강아지 이동'을 시킬때 조건 2가지가 중요하다

조건 1. 경계선이 벗어나면 다음 명령을 실행하고, 경계선 안에 있으면

조건 2. 이동 범위 안에 장애물이 있는지 확인을 하고 장애물이 있으면 다음 명령을 실행하게 해놨다.

조건1,조건2를 전부 만족할경우 현재 강아지의 좌표를 변경해주는 식으로 진행하였다.

간략한 내용은 플로우차트에 적어놨다.

플로우 차트 밑에 기능적으로 함수화를 하면 가독성이 많이 올라간다.

<플로우 차트>

0. 사전 준비
0-1. Park 지도를 만들기 (2차원 배열화)
0-1-1. Park 지도를 만들면서 (시작지점과 , 장애물지점을 설치)
(// 0:길 1:장애물 2:로봇강아지 )

1.routes 리스트의 data를 사용할수 있는 형식으로 만들기
1-1.방향(E,W,N,S) 와 이동거리(Move) 형식으로 만들기

2.강아지 진행시키기
(조건 1: 최종 위치기 경계선을 벗어나면 , 명령 동작x)
(조건 2: 이동경로에 장애물이 있는경우, 명령 동작x)

#include <string>
#include <vector>
#include <sstream>

#define UP_OR_LEFT -1
#define DOWN_OR_RIGHT 1

#define MOVE_X 1
#define MOVE_Y -1

#define PARK_ROAD  0
#define PARK_OBJECT 1
#define PARK_DOG 2

using namespace std;

vector<int> solution(vector<string> park, vector<string> routes)
{
    vector<int> answer;

    int width = park[0].length();
    int height = park.size();

    int dog_x =0, dog_y =0; // 로봇강아지 현재좌표 

    //0-1. Park 지도를 만들기 (2차원 배열화)
    vector<vector<int>> Park_map(height,vector<int>(width,0));

    //0-1-1. Park 지도를 만들면서 (시작지점과 , 장애물지점을 설치)
    // (0:길 1:장애물 2:로봇강아지 )
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            //시작 지점 기록
            if (park[y][x] == 'S')
            {
                dog_x = x;
                dog_y = y;
                Park_map[y][x] = 2;
                
            }
            
            //장애물 위치 기록
            else if (park[y][x] == 'X')
            {
                Park_map[y][x] = 1;
            }
        }
    }

    int routes_roop = routes.size();

    for (int route_index = 0; route_index < routes_roop; route_index++)
    {
        //1.routes 리스트의 data를 사용할수 있는 형식으로 만들기
        // 1 - 1.방향(E, W, N, S) 와 이동거리(Move) 형식으로 만들기
        char dir;
        int move = 0;
        stringstream stream;
        stream.str(routes[route_index]);

        stream >> dir;
        stream >> move;
        //------------------------------------------------------------

        /* 2.강아지 진행시키기
        (조건 1: 최종 위치기 경계선을 벗어나면 , 명령 동작x)
        (조건 2: 이동경로에 장애물이 있는경우, 명령 동작x) */
        int dir_add = 0; // 방향 이동시 -,+ 결정 
        int move_axis = 0; // 이동하는 축 결정 
        bool move_check = true;

        switch (dir)
        {
        case 'E' :
            dir_add = DOWN_OR_RIGHT;
            move_axis = MOVE_X;
            break;
        case 'W':
            dir_add = UP_OR_LEFT;
            move_axis = MOVE_X;
            break;
        case 'S':
            dir_add = DOWN_OR_RIGHT;
            move_axis = MOVE_Y;
            break;
        case 'N':
            dir_add = UP_OR_LEFT;
            move_axis = MOVE_Y;
            break;
        }
        
        int move_result = move * dir_add; //이동거리 * 방향결정 = 강아지가 움질익 방향 

        int move_min, move_max,move_tmp; // 이동 범위
        
        switch (move_axis)
        {
        case  MOVE_X:
            //(조건 1: 최종 위치기 경계선을 벗어나면 , 명령 동작x)
            if (dog_x + move_result >= width || dog_x + move_result < 0)
            {
                break;
            }
   
            
            //이동 범위 계산
            move_min = dog_x;
            move_max = dog_x + move_result;

            if (move_min > move_max)
            {
                move_tmp = move_min;
                move_min = move_max;
                move_max = move_tmp;
            }

            //(조건 2: 이동경로에 장애물이 있는경우, 명령 동작x
            for (int i = 0; i < move_max - move_min; i++)
            {
                int move_x = dog_x + (dir_add * (i + 1));
                if (Park_map[dog_y][move_x] == PARK_OBJECT)
                {
                    move_check = false;
                    break;
                }
            }

            if (move_check)
            {
                Park_map[dog_y][dog_x] = PARK_ROAD;
                dog_x += move_result;
                Park_map[dog_y][dog_x] = PARK_DOG;
            }

            break;

        case  MOVE_Y:
            //(조건 1: 최종 위치기 경계선을 벗어나면 , 명령 동작x)
            if (dog_y + move_result >= height || dog_y + move_result < 0)
            {
                break;
            }

            //이동 범위 계산
            move_min = dog_y;
            move_max = dog_y + move_result;

            if (move_min > move_max)
            {
                move_tmp = move_min;
                move_min = move_max;
                move_max = move_tmp;
            }

            //(조건 2: 이동경로에 장애물이 있는경우, 명령 동작x
            for (int i = 0; i < move_max - move_min; i++)
            {
                int move_y = dog_y + (dir_add * (i + 1));
                if (Park_map[move_y][dog_x] == PARK_OBJECT)
                {
                    move_check = false;
                    break;
                }
            }

            if (move_check)
            {
                Park_map[dog_y][dog_x] = PARK_ROAD;
                dog_y += move_result;
                Park_map[dog_y][dog_x] = PARK_DOG;
            }

            break;
        }
    }

    answer.push_back(dog_y);
    answer.push_back(dog_x);
    return answer;
}

다른분이 풀은것을 보니 2차원 배열화를 할 필요가 없었다.

장애물때문에 2차원 배열하는게 좋을줄알았는데 그냥 park의 문자열 찾기로 x만 제외했으면 됬다.

 또한 나같은경우는 매번 roop를 돌때마다 switch문을 들어가서 각 해당되는값을 정의했는데

들어가기전 필요한 data들을 세팅하고 반복문을 돌리는 형식이다. 

<플로우 차트>

0. 사전 준비

0-1.dx,dy,mapping으로 각 방향시 이동하는 칸수 및 단일문자에 따른 인덱스값 설정

0-2. 시작 위치 좌표 알기 ( Park 반복문)

1. 강아지 이동경로 갯수만큼 roop

1-1. 강아지의 이동칸수 만큼 roop

1-1-1.강아지가 한칸 씩 이동하면서 장애물 체크 및 경계선 체크를 동시에 한다. 

2.반복문이 roop를 다 돌은경우 현재 좌표 갱신 

#include <string>
#include <vector>
#include <map>

using namespace std;
using pi = pair<int, int>;

//0 = S, 1 = N , 2 = E , 3 = W
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

map<char, int> mapping = {
    {'E', 0}, {'W', 1}, {'S', 2}, {'N', 3}
};

vector<int> solution(vector<string> park, vector<string> routes)
{
    int cx, cy;

    //시작 위치 좌표 알기 
    for (int i = 0; i < park.size(); ++i) {
        for (int j = 0; j < park[i].size(); ++j) {
            if (park[i][j] == 'S') 
            {
                //tie : pair,tuple으로 구성 되어있을때, 여러개읜 return값이 필요할때 사용하는 명령어
                tie(cx, cy) = { i, j };
                break;
            }
        }
    }

    //강아지 경로 갯수만큼 반복문 roop
    for (int i = 0; i < routes.size(); ++i) {
        int num = routes[i][2] - '0'; // 이동거리 확인 , 문자열의 2번재 인덱스(숫자) ,char 자료형이기떄문에 아스키코드(0,-48)을 해서 int로 변경
        int dir = mapping[routes[i][0]];//이동방향 단일문자 확인 , map에 키값을 넣고 int 값을 받아옴 

        int nx = cx, ny = cy;
        while (num--) {
            nx += dx[dir];
            ny += dy[dir];

            if (!(nx >= 0 && nx < park.size()) || !(ny >= 0 && ny < park[0].size())) break; // 경계선 체크
            if (park[nx][ny] == 'X') break; // 장애물 체크
        }

        //해당 i의 이동roop를 다 돌은경우 좌표 갱신
        if (num < 0) {
            cx = nx;
            cy = ny;
        }
    }
    return { cy, cx };
}

플로우차트

1.귤을 size 기준으로 오름차순 정렬

2.오름차순 정렬한 귤을 반복문을 돌려 사이즈별로 갯수를 체크( vector<int> tangerine_count 에 저장)
3.정렬되서 나온 벡터를 귤 갯수 기준으로 내림차순 정렬

4.상자에 k갯수만큼 담으면서 루프 ( k개를 초과할시 루프 탈출후 answer 반환)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, vector<int> tangerine) 
{
    int answer = 0, count = 0; //count : 상자에 들어가는 귤의 갯수 
    vector<int> tangerine_count; // 귤을 사이즈별로 나눠서 갯수를 알게하는 벡터
      
    sort(tangerine.begin(), tangerine.end()); //귤을 오름차순 순으로 정렬 

    int compare_tagerine = tangerine[0];//정렬한 귤 첫번째를 선택(기준)

	//루프를 시작 ( 사이즈별로 갯수 확인 루프 )
    for (int i = 1; i < tangerine.size(); i++)
    {
    	//기준 귤 사이즈 와 i번째 귤의 사이즈가 같으면 count++
        if (compare_tagerine == tangerine[i])
        {
            count++;
        }
        else // 기존 귤 사이즈와 i번째 귤이 다름
        {
            tangerine_count.push_back(++count); // 자기자신을 count하면서 벡터에 추가
            compare_tagerine = tangerine[i];//기준을 i번째 귤로 교체
            count = 0;//count 초기화 
        }
    }
    tangerine_count.push_back(++count); // 마지막 원소count 가 안된경우 추가 
	//마지막 루프를 탈출할때 count가 안되는 경우가 있기 때문에 따로 추가
    
    //사이즈 별로 나눠놓은 귤갯수 벡터를 정렬 후 내림차순 정렬로 전환 
    sort(tangerine_count.begin(), tangerine_count.end());
    reverse(tangerine_count.begin(), tangerine_count.end()); // 내림차순 정렬로 바꾸기 

    int count_sum = 0; // 상자에 들어간 귤 
    int i = 0;//인덱스
	
    //k갯수를 초과하지 않으면 계속 상자에 담음 
    while (k > count_sum)
    {
        //사이즈 별로 가장 많은 귤을 먼저 상자에 담음
        count_sum += tangerine_count[i++];
        answer++;
    }


    return answer;
}

귤벡터가 [ 1,3,2,5,4,5,2,3]인 경우

1.첫번재 루프

t = 귤 벡터의 첫번째인덱스의 데이터값
v[ 1 - 1 ] ++; 

v[0]은 1의 값을 가지고 있게 된다.
이 벡터의 의미는 Size가 1 인 귤을 count했다는 의미이다.

2.두번째 루프

t = 귤 벡터의 두번째인덱스의 데이터값

v[3-1]++; //v[2]은 Size가 3인 귤을 의미,count한다

...

루프를 계속 반복하면

결과:

v[0] = 1 // Size = 1 인 귤이 1개 있음,

v[1] = 2  // Size = 2 인 귤이 2개 있음,

v[2] = 2  // Size = 3 인 귤이 2개 있음,

v[3] = 1  // Size = 4 인 귤이 1개 있음,

v[4] = 1  // Size = 5 인 귤이 2개 있음,

이런식으로 나눌수 있다. 

#include <bits/stdc++.h>

using namespace std;

int solution(int k, vector<int> tangerine)
{
    int answer = 0;
    int m = *max_element(tangerine.begin(), tangerine.end()); //귤벡터중 제일 큰 원소(size)를 호출
    //m = 귤 최대 size를 입력 ,기준이 됨 
    vector<int> v(m, 0); // m범위 만큼 0(초기값)으로 초기화
    
    //위에 내용 참조
    for(auto& t : tangerine)
    {
        v[t - 1]++;
    }
    
    //사이즈별로 나눈 귤을 내림차순 정렬
    //rbegin,rend로 역으로 정렬
    //Stable Sorting은 같은 것이 있는 경우 정렬하기 전의 순서가 유지되는 정렬 알고리즘이다
    stable_sort(v.rbegin(), v.rend());
    
    //사이즈 별로 나눈 벡터 사이즈만큼 루프를 돌림
    for(int i = 0 ; i < v.size() ; i++)
    {
        answer++;
        k -= v[i]; // 현재 인덱스의 갯수만큼 상자에 담음
        if(k <= 0) return answer; // 상자에 k개 만큼 초과시 answer값을 반환
    }
    
    return answer;
}

정답처리 된 코드지만 , 가독성이 안좋게 구성이 되었다.

하나의 target을 정한뒤 keymap을 벡터를 탐색해서 해당 문자를 찾는것으로 설계를 하다보니 반복문 다중으로 많이 사용되었음. 

플로우차트는 

0.target의 문자열을 길이기준으로 오름차순 정렬

ex) ABCD,ABC,ABCDE -> ABC,ABCD,ABCDE

1.비교할 target 선정 

1-1.target의 char(단일문자)하나를 선정
2.target_Char 와 keymap과의 비교 시작

2-1.keymap_char_index 설정 ( keymap 리스트에 공통적으로 적용되는 인덱스)

2-2. keymap_list Roop 시작

2-3.비교 시작  

2-3-1.(같은 문자를 찾은경우) 2-1로 돌아감,roop한 횟수를 answer에 저장

2-3-2.(같은 문자를 못 찾은경우) 2-1로 돌아감,,다시 탐색

2-3-3.(roop를 다 돌렸지만 해당 target 문자를 못찾을경우) answer 벡터에 -1 대입후 반복문 탈출 및 1번으로 돌아감

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(string keymap1, string keymap2)
{
    //글자갯수로 오름차순 정렬
    return keymap1.length() < keymap2.length();
}

bool char_compare(char target_char,vector<string> keymap,int c)
{
    for (int d = 0; d < keymap.size(); d++)
    {
    	//해당 target의 문자 index가 문자열 길이 보다 크거나 같을경우, 그 반복문 본문 스킵
        //ex)ABC(문자열 길이 3) targer index (4) -> skip 
        if (keymap[d].length() <= c)
        {
            continue;
        }

        char key_char = keymap[d].at(c);

        //2-3.비교시작
        if (target_char == key_char)
        {
            //2-3-1.(같은 문자를 찾은경우) 2-1로 돌아감,roop한 횟수를 answer에 저장
            return true;
        }

    }

    return false;
}

vector<int> solution(vector<string> keymap, vector<string> targets)
{
    //keymap 문자열 길이기준으로 오름차순 정렬 
    sort(keymap.begin(), keymap.end(), compare);
    int roop_count = keymap.back().length(); // target중 제일 긴문자를 roop횟수로 설정
	
	//answer를 target벡터 갯수만큼 초기화
    vector<int> answer;
    for (int i = 0; i < targets.size(); i++)
    {
        answer.push_back(0);
    }
    bool fail_check = false;

    for (int a = 0; a < targets.size(); a++)
    {
        //1.비교할 target 선정
        string target_str = targets[a];// targets 문자열 정의
        int target_length = target_str.length();

        for (int b = 0; b < target_length; b++)
        {
            //1-1.target Char 설정
            char target_char = target_str.at(b);

            //2.target_Char vs keymap_list (비교)
            //2-1.keymap_char_index 설정( 리스트에 공통)
            
            //c : target_char_index
            for (int c = 0; c < roop_count; c++)
            {
                //2-2.keymap_list_index 루프 시작
                if (char_compare(target_char, keymap, c))
                { 
                    answer[a] += c + 1;
                    break;
                }
                
          	   //해당되는 글자를 못찾을경우 -1과 bool값 변경
                if (c == roop_count - 1)
                {
                    answer[a] = -1;
                    fail_check = true;
                }
            }
			
			//해당 문자열은 출력 못하므로 문자열 반복문 탈출 
            if (fail_check)
            {
                fail_check = false;
                break;
            }

        }
    }

    return  answer;
}

이 풀이는 target을 먼저 탐색하기 전에 , keymap을 루프를 돌려 해당 문자를 출력하기 위한 최소의 횟수를 미리 리스트화 한뒤 target에 접근 하는 방식이다.

플로우차트는

1.26개(알파벳갯수)의 사이즈의 벡터를 100000(MARKER)로 전부 초기화

1-1.keymap을 기준으로 루프를 돌려 table에 해당 문자열을 찾기위해 최소 횟수 탐색
ex) 

target = { ABACD , BECFD }

첫번째 루프 (ABACD)

table[0] = 1 // 1=min(100000 , 1) 알파벳 A

table[1] = 2 // 1=min(100000 , 2) 알파벳 B

table[0] = 1 // 1=min(1 , 1) 알파벳 A

table[2] = 4 // 4=min(100000 , 4) 알파벳 C

table[3] = 5 // 5=min(100000 , 5) 알파벳 D

두번째 루프 (BCEFD)

table[1] = 1 // 1=min(2 , 1) 알파벳 B

table[2] = 2 // 2=min(4 , 2) 알파벳 C

table[4] = 3 // 1=min(100000 , 3) 알파벳 E

table[5] = 4 // 4=min(100000 , 4) 알파벳 F

table[3] = 5 // 5=min(5 , 5) 알파벳 D

최종 결과물
table[0] = 1  // 알파벳 A를 출력하기 위한 최소 횟수

table[1] = 1 // 알파벳 B를 출력하기 위한 최소 횟수

table[2] = 2 // 알파벳 C를 출력하기 위한 최소 횟수

table[3] = 5 // 알파벳 D를 출력하기 위한 최소 횟수

table[4] = 3 // 알파벳 E를 출력하기 위한 최소 횟수

table[5] = 4 // 알파벳 F를 출력하기 위한 최소 횟수

table[6] = 100000 // 알파벳 G를 출력하지 못함
... 

 이런식의 roop를 통해 미리 알파벳의 최소 루트를 구해놓은뒤 작업을 한다 .

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;

    const int MARKER = 1000000; //  MARKER : 사용하지않는것을 표시
    vector<int> table(26, MARKER);  //26개(알파벳 갯수)의 벡터 사이즈 설정 , MARKER(100000)으로 초기화
   
   //keymap를 루프 둘려 각 단일문자를 최소의 횟수로 찾아가는지 탐색 
    for (const auto& v : keymap)
    {
        for (int i = 0; i < v.size(); ++i)
        {
            table[v[i] - 'A'] = min(table[v[i] - 'A'], i + 1);
        }
    }

    for (const auto& str : targets)
    {
        int total = 0;
        for (const auto c : str)
        {
            //MARKER와 같으면 이 문자는 출력할수 없다는 뜻
            if (table[c - 'A'] == MARKER)
            {
                //결과값 -1과 해당 문자열 탈출 
                total = -1;
                break;
            }
            else
            {
				//위에서 구한 해당 문자의 최소 출력횟수를 total에 더함
                total += table[c - 'A'];
            }
        }
		
        //push_back과 같은 의미지만 자료형이 같을경우 사용할수 있는 push_back
        answer.emplace_back(total);
    }

    return answer;
}