코드메모장

(1) Next_permutation 함수란?

범위의 요소를 [first,last]다음 사전 식으로더 큰 순열로 다시 정렬합니다. 

 ex) 1,2,3 -> 1,3,2 -> 2,1,3 -> 2,3,1 -> 3,1,2 -> 3,2,1

단, 1,3,2 에서 시작 시 1,2,3의 경우는 돌아가지 않는다.

(2) Next_permutation 함수 구조

• 필요 헤더  

#include <algorithm>

• 템플릿

//default
template <class BidirectionalIterator>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);

//custom(비교문을 넣을 수 있음)                         
template <class BidirectionalIterator, class Compare>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);
                         
 <------------------------예제------------------------>
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main () {
  int myints[] = {1,2,3};

  std::sort (myints,myints+3);

  std::cout << "The 3! possible permutations with 3 elements:\n";
  do {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while ( std::next_permutation(myints,myints+3) );

  std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';

  return 0;
}

(3) Next_permutation 사용법

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> v;

	v.push_back(2);
	v.push_back(1);
	v.push_back(3);

//모든 경우의 수를 확인하기 위해 최초 벡터를 오름차순으로 정렬
	sort(v.begin(), v.end());
	
	do {
		for (int i = 0; i < v.size(); i++)
		{
			cout << v.at(i);
		}
		cout << endl;
	} while (next_permutation(v.begin(), v.end()));

	return 0;
}

아래 링크를 통해 Next_permutation 함수를 사용한 완전탐색예제를 확인하실수 있습니다.

2020/11/27 - [Programmers/C++] - [프로그래머스] 코딩테스트 연습 > 완전탐색 > 소수 찾기(C++)

(1) 문제

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

(2) 제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

(3) 코드

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

using namespace std;

bool isPrime(int n);

int solution(string numbers) {
    int answer = 0;
    vector<int> number;
    string str_temp = "";

    sort(numbers.begin(), numbers.end());

    do
    {
        for (int i = 0; i < numbers.size(); i++)
        {
            for (int j = 0; j < numbers.size() - i; j++)
            {
                str_temp += numbers.at(j);
            }
            number.push_back(stoi(str_temp));
            str_temp = "";
        }
    } while (next_permutation(numbers.begin(), numbers.end()));

    sort(number.begin(), number.end());
    number.erase(unique(number.begin(), number.end()), number.end());

    for (int i = 0; i < number.size(); i++)
    {
        if (!isPrime(number.at(i)))
        {
            number.erase(number.begin() + i);
            i--;
        }
    }

    answer = number.size();

    return answer;
}

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }

    for (int i = 2; i <= sqrt(n); i++) {
        if ((n % i) == 0) {
            return false;
        }
    }

    return true;
}

(4) 실행결과

(1) 문제

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

(2) 제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

(3) 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    vector<int> factor;
    int square_size = brown + yellow;
    int square_width = 0;
    int square_height = 0;

    for (int i = 3; i < square_size; i++)
    {
        if (square_size % i == 0)
        {
            factor.push_back(i);
        }        
    }

    for (int i = 0; i < factor.size(); i++)
    {
        square_height = factor.at(i);
        square_width = square_size / square_height;

        if (square_width * 2 + square_height * 2 - 4 == brown)
        {
            answer.push_back(square_width);
            answer.push_back(square_height);

            return answer;
        }

    }
}

(4) 실행결과