[프로그래머스] 같은 숫자는 싫어, 최대 공약수와 최소 공배수

같은 숫자는 싫어

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

프로그래머스

 

문제 설명
배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다.
예를 들면,arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.
배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항
배열 arr의 크기 : 1,000,000 이하의 자연수배열
arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

 

배열을 탐색할때 이전 위치의 값과 현재 값을 비교하면 해결할 수 있는 문제다.

 

#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    
    answer.push_back(arr[0]);
    
    for(int i = 1; i < arr.size(); i++)
    {
        
        if(arr[i-1]!=arr[i])
        {
            answer.push_back(arr[i]);
        }
    }


    return answer;
}

---

최대 공약수와 최소 공배수

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

프로그래머스

 

문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 사항
두 수는 1이상 1000000이하의 자연수입니다.

 

최대 공약수와 최소 공배수의 공식을 알고 있어야 풀 수 있는 문제이다. 

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    int big = m;
    
    int small = n;
    
    int order = big%small;
    
    while(order!=0)
    {
        big = small;
        small = order;
        order = big%small;
    }
    
    answer.push_back(small);
    answer.push_back(m*n/small);
    
    return answer;
}

 

유클리드 호제법이라는 공식으로 값을 구할 수 있다.

 

    int big = m;
    
    int small = n;
    
    int order = big%small;
    
    while(order!=0)
    {
        big = small;
        small = order;
        order = big%small;
    }

최대 공약수를 구하는 식이다. 큰수에서 작은수를 나누었을때 나머지 값이 0 이면 그게 최소 공배수인데 만약 0으로 나누어 떨어지지 않는다면 작은수에서 나머지값을 게속 나누어 0이 될때까지 해주면 값이 나온다.

 

최소 공배수는 (큰수 *작은수) / (최소공배수)를 해주면 바로 알 수 있다.