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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

더보기 주의 , 코드에 관한 설명이 간략히 있지만 코드 내용 원문이 있으니 주의 할 것

 

<나의 풀이>

더보기

현재 index와 다음 index 값을 비교해서 다를경우,

answer에 현재 index값을 저장 후 roop를 진행한다.

index+1 했을때 arr의 size보다 크거나 같을경우 마지막 숫자를 answer에 추가하면서

반복문을 탈출한다.

#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
	
    //arr의 갯수만큼 roop
    for(int i = 0 ; i< arr.size() ; i++)
    {
    	//배열이 범위를 벗어나지 않게 하기위한 조건문
        if( i+1 >= arr.size())
        {
            answer.push_back(arr[i]);
            break;
        }
        
        //현재 index와 다음 index가 다를경우 값을 저장 
        if(arr[i] != arr[i+1])
        {
            answer.push_back(arr[i]);
        }
    }
    
    return answer;
}

<다른사람의 풀이>

더보기

algorithm헤더의 unique함수와 std::vector의 erase 함수 두개를 활용하면 해당 배열의 원소 중 중복값을 없앨수 있다.

 

unique 함수 : 배열에서 원소를  앞에서부터 채워나가며 채운 함수중에 중복이 있으면 뒤로 보내는 함수이다.

unique함수는 중복되지 않은 값들을 나열 한뒤 남은 중복 원소의 첫번째 iterator 값을 반환, 

unique함수를 사용하기전에 sort 함수를 하여 정렬할 필요가 있다.

 

(unique함수로부터 반환된 iterator , 배열의 끝  iterator) 범위를 eraser함수하면
함수 고유의 값들만 남아있다. 

 

하지만 이 문제는 함수의 순서를 바꾸지 말라고 하였기에 sort함수를 사용하지 않고 바로 unique함수를 활요한 것이다.

 

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<int> solution(vector<int> arr) 
{
	//vector 에서 중복되는 함수들을 한곳에 모아 삭제할때 쓰는 구조다.
    arr.erase(unique(arr.begin(), arr.end()),arr.end());

    vector<int> answer = arr;
    return answer;
}

 

'코딩테스트 > 프로그래머스' 카테고리의 다른 글

LV2.숫자 변환하기  (0) 2023.10.26
LV2.2개 이하로 다른 비트  (0) 2023.10.26
LV.2 최솟값 만들기  (0) 2023.06.09
LV.1 내적  (0) 2023.06.09
LV.1 없는 숫자 더하기  (0) 2023.06.09

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

더보기 주의 , 코드에 관한 설명이 간략히 있지만 코드 내용 원문이 있으니 주의 할 것

 

<나의 풀이>

더보기

2개의 벡터가 주어지는데 각 벡터의 원소들을 곱하고서 그 합의 최솟값을 구하는 문제이다.
즉, (첫번째 작은 값 * 첫번째 큰 값) + (두번째 작은 값 * 두번째 큰 값) + .... = 최솟값 이 나온다 

 

2개의 벡터에 하나는 오름차순으로 정렬 하나는 내림차순으로 정렬한뒤

반복문을 이용하여 작은값 * 큰값을 roop할 수 있게 해주면된다.

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;
    
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    reverse(B.begin(),B.end());

    
    //양쪽 벡터에서 가장 작은 숫자 하나와 가장큰숫자를 골라서 곱한다.
    
    for(int i=0; i< A.size(); i++)
    {
        answer += A[i] * B[i];
    }

    return answer;
}

<다른사람의 풀이>

더보기
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
int solution(vector<int> A, vector<int> B){
    sort(A.begin(),A.end());  sort(B.rbegin(),B.rend());
    return inner_product(A.begin(),A.end(),B.begin(),0);
}

 익숙하지 않은 명령어들이 있어서 정리하려고 가져왔다.


*inner_product();

numeric 헤더에 포함된 명령어이며, 내적을 구할때 사용하는 명령어이다.

inner_product(시작값A,마지막값A,시작값B,초기값) 으로 사용된다. 

예제 코드 및 추가적인 내용은 밑에 링크 확인

https://01149.tistory.com/14

 

STL 범용 수치 알고리즘 (accumulate , inner_product)

//accumulate 함수의 원문 #include template T accumulate (InputIterator first, InputIterator last, T init); template T accumulate (InputIterator first, InputIterator last, T init, BinaryOperation binary_op); accumulate(구간의 시작 값, 구간의

01149.tistory.com


*rbegin(),rend()

std::vector 자료형의 내림차순 정렬이 필요할때 , rbegin, rend 함수를 활용하면 가독성 좋은 코드를 짤 수 있다. 

예제 코드 및 추가적인 내용은 밑에 링크 확인

https://01149.tistory.com/15

 

std::vector (reverse_iterator,rbegin(),rend(),역방향반복자,내림차순정렬)

reverse_iterator(역방향 반복자) : 반복자(iterator)와는 정반대로 동작하는 반복자 ++,-- 연산자를 이용하여 iter를 변경하고 그랬는데 반대로 동작하게된다. std::vector에서 자주 사용해온 begin(), end() 명

01149.tistory.com

 

 

'코딩테스트 > 프로그래머스' 카테고리의 다른 글

LV2.2개 이하로 다른 비트  (0) 2023.10.26
LV.1 같은 숫자는 싫어  (0) 2023.06.09
LV.1 내적  (0) 2023.06.09
LV.1 없는 숫자 더하기  (0) 2023.06.09
LV.1 공원산책  (0) 2023.06.08

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

더보기 주의 , 코드에 관한 설명이 간략히 있지만 코드 내용 원문이 있으니 주의 할 것

 

<나의 풀이>

더보기
문제가 각 좌표의 내적을 구하는 것이기 때문에 그냥 내적 구하는 식에 반복문만 추가하면 쉽게 풀 수 있다. 
#include <string>
#include <vector>

using namespace std;

int solution(vector<int> a, vector<int> b) {
    int answer = 0;
    
    for(int i=0; i < a.size() ; i++)
    {
        answer += a[i] * b[i];
    }
    
    return answer;
}

'코딩테스트 > 프로그래머스' 카테고리의 다른 글

LV.1 같은 숫자는 싫어  (0) 2023.06.09
LV.2 최솟값 만들기  (0) 2023.06.09
LV.1 없는 숫자 더하기  (0) 2023.06.09
LV.1 공원산책  (0) 2023.06.08
[LV2] 귤 고르기  (0) 2023.05.31

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

더보기 주의 , 코드에 관한 설명이 간략히 있지만 코드 내용 원문이 있으니 주의 할 것

 

<나의 풀이 (비추천)>

더보기

0~9 까지의 숫자중 nuebers vector에 없는 원소를 다 더하는 문제다.

 

0.사전준비

0-1. 0~9의 list 만들기

0-2.numbers를 오름차순으로 정렬하기

 

1.list와 nubers의 원소를 비교하여 없는 원소 합 구하기

1-1.list와 number의 원소값이 다른경우 list의 현재 index값을 answer에 더한다.

1-2.list의 index만 증가시키고 다시 비교 후 원소값이 같지 않으면 1-1 반복, 같은경우 반복문을 진행

1-3.numbers의 index가 사이즈와 같거나 큰 경우 list와 비교하지 않은 원소들을 전부 answer에 더한다.

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

using namespace std;

int solution(vector<int> numbers) {
    int answer = 0;
    vector<int> list = {0,1,2,3,4,5,6,7,8,9};
    
    sort(numbers.begin(),numbers.end());
    
    for(int i=0 , j=0; i< list.size() ; i++,j++)
    {
        if(j >= numbers.size())
        {
           answer += list[i];
            continue;
        }
        
        while(list[i] != numbers[j])
        {
            answer += list[i];
            i++;
        }
    }
    
    return answer;
}

<다른사람의 풀이>

더보기

숫자의 범위는 0~9까지 변동이 없기 때문에 총합은 45로 고정되어있다.
numbers에서 총합45를 하나씩 빼면 남는 숫자는 numbers의 제외된 숫자의 총합이기 때문에 이렇게 간단히 쓸수있다.

나의 풀이는 각 어떤 원소가 남이있는지에 중점을 두다 보니 이렇게 코드를 짯다. 하지만 원하는건 제외된 숫자의 총합이기 떄문이다. 다음에 문제를 풀때는 원하는 값이 무엇인지 더욱 생각해야될듯하다. 

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> numbers) {

    int answer = 45;

    for (int i = 0 ; i < numbers.size() ; i++)
        answer -= numbers[i];

    return answer;
}

 

 

'코딩테스트 > 프로그래머스' 카테고리의 다른 글

LV.2 최솟값 만들기  (0) 2023.06.09
LV.1 내적  (0) 2023.06.09
LV.1 공원산책  (0) 2023.06.08
[LV2] 귤 고르기  (0) 2023.05.31
[LV1] 대충 만든 자판  (0) 2023.05.28

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

더보기 주의 , 코드에 관한 설명이 간략히 있지만 코드 내용 원문이 있으니 주의 할 것

 

<나의 풀이 (비추천)>

더보기

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 };
}

 

 

'코딩테스트 > 프로그래머스' 카테고리의 다른 글

LV.2 최솟값 만들기  (0) 2023.06.09
LV.1 내적  (0) 2023.06.09
LV.1 없는 숫자 더하기  (0) 2023.06.09
[LV2] 귤 고르기  (0) 2023.05.31
[LV1] 대충 만든 자판  (0) 2023.05.28

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

더보기 주의 , 코드에 관한 설명이 간략히 있지만 코드 내용 원문이 있으니 주의 할 것 

 

<나의 풀이(비추천)>

더보기

플로우차트

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;
}

 

 

'코딩테스트 > 프로그래머스' 카테고리의 다른 글

LV.2 최솟값 만들기  (0) 2023.06.09
LV.1 내적  (0) 2023.06.09
LV.1 없는 숫자 더하기  (0) 2023.06.09
LV.1 공원산책  (0) 2023.06.08
[LV1] 대충 만든 자판  (0) 2023.05.28

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

더보기 주의 , 코드에 관한 설명이 간략히 있지만 코드 내용 원문이 있으니 주의 할 것 

 

<나의 풀이 (비추천)>

더보기

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

하나의 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;
}

 

 

'코딩테스트 > 프로그래머스' 카테고리의 다른 글

LV.2 최솟값 만들기  (0) 2023.06.09
LV.1 내적  (0) 2023.06.09
LV.1 없는 숫자 더하기  (0) 2023.06.09
LV.1 공원산책  (0) 2023.06.08
[LV2] 귤 고르기  (0) 2023.05.31

+ Recent posts