7. Implementation

 

7.1 Implementation

해커랭크3DSurface)

  공간지각력 싸움.

cpp

코드 펼치기

#pragma once

#include <vector>

using namespace std;

int surfaceArea(vector<vector<int>> A) {
    int H = A.size();
    int W = A[0].size();
    int ResultArea = 0;

    for (int i = 0; i < H; ++i) 
    {
        for (int j = 0; j < W; ++j) 
        {
            // 기본적으로 위쪽과 아래쪽의 표면적 (2를 더함)
            ResultArea += 2;

            // 현재 셀의 높이
            int CurrentDepth = A[i][j];

            // 왼쪽 셀과의 차이
            if (j == 0) 
            {
                ResultArea += CurrentDepth; // 왼쪽 면 노출
            }
            else {
                ResultArea += max(0, CurrentDepth - A[i][j - 1]);
            }

            // 오른쪽 셀과의 차이
            if (j == W - 1) 
            {
                ResultArea += CurrentDepth; // 오른쪽 면 노출
            }
            else 
            {
                ResultArea += max(0, CurrentDepth - A[i][j + 1]);
            }

            // 위쪽 셀과의 차이
            if (i == 0) 
            {
                ResultArea += CurrentDepth; // 위쪽 면 노출
            }
            else 
            {
                ResultArea += max(0, CurrentDepth - A[i - 1][j]);
            }

            // 아래쪽 셀과의 차이
            if (i == H - 1) 
            {
                ResultArea += CurrentDepth; // 아래쪽 면 노출
            }
            else 
            {
                ResultArea += max(0, CurrentDepth - A[i + 1][j]);
            }
        }
    }

    return ResultArea;
}

 

해커랭크ClimbingTheLeaderboard)
  순위를 구하는 문제. 단, 중복제거 로직이 필요한 문제.
  sort() -> unique() -> erase() 순서의 로직을 통해 중복 제거. 그리고 순서 비교.

cpp

코드 펼치기

#pragma once

#include <vector>
#include <algorithm>

std::vector<int> climbingLeaderboard(std::vector<int> ranked, std::vector<int> player) 
{
	std::sort(ranked.begin(), ranked.end(), [](int op1, int op2) -> bool { return op1 > op2; }); // 중복 제거 전 정렬 필수.
	ranked.erase(std::unique(ranked.begin(), ranked.end()), ranked.end());
	// unique() 함수는 자료구조 내의 중복 원소를 맨 뒤로 보내고, 중복 원소들의 시작 위치 iterator를 반환함.
	// erase() 함수는 전달 받은 iterator를 기준으로 원소 삭제.
	std::vector<int> ResultRank;
	int Count = ranked.size();

	int Rank = Count - 1;
	for (int CurrentPlayerScore : player)
	{
		while (0 <= Rank && ranked[Rank] <= CurrentPlayerScore)
		{
			--Rank;
		}

		ResultRank.push_back(Rank + 2);
		// ranked 벡터는 0부터 시작 하므로 +1, 만약 ranked 벡터가 비어있어서 자동으로 1위가 되는 경우에 n은 -1 이므로 보정을 위해 +1.
	}

	return ResultRank;
}

 

해커랭크FormingMagicSquare)
  미리 배열을 만들어두는 것도 문제푸는데에 중요할 수 있다.
  너무 머리를 굴려서 알고리듬화 하려기보다는 가끔은 그냥 배열로 만들어둬서 푸는게 중요할 수 있음.

cpp

코드 접기

#pragma once

#include <vector>
#include <algorithm> // sort()
#include <limits> // UINT64_MAX

bool CheckMagicSquare(std::vector<int> InDigits)
{
    static const int MagicConstant = 15;
    return (InDigits[0] + InDigits[1] + InDigits[2] == MagicConstant &&
        InDigits[3] + InDigits[4] + InDigits[5] == MagicConstant &&
        InDigits[6] + InDigits[7] + InDigits[8] == MagicConstant &&
        InDigits[0] + InDigits[3] + InDigits[6] == MagicConstant &&
        InDigits[1] + InDigits[4] + InDigits[7] == MagicConstant &&
        InDigits[2] + InDigits[5] + InDigits[8] == MagicConstant &&
        InDigits[0] + InDigits[4] + InDigits[8] == MagicConstant &&
        InDigits[2] + InDigits[4] + InDigits[6] == MagicConstant);
}

int CalculateCost(std::vector<std::vector<int>>& InSquare, std::vector<int>& InMagicSquare)
{
    int Cost = 0;
    for (size_t i = 0u; i < 3; ++i)
    {
        for (size_t j = 0u; j < 3; ++j)
        {
            Cost += std::abs(InSquare[i][j] - InMagicSquare[i * 3 + j]);
        }
    }

    return Cost;
}

int formingMagicSquare(std::vector<std::vector<int>> s) {
    std::vector<int> Digits = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    std::sort(Digits.begin(), Digits.end()); // 순열 전에 정렬하여 모든 경우의 수를 만들어 낼 수 있게끔 함.
    size_t MinCost = UINT64_MAX;

    do {

        if (CheckMagicSquare(Digits) == true)
        {
            int CalculatedCost = CalculateCost(s, Digits);
            MinCost = MinCost < CalculatedCost ? MinCost : CalculatedCost;
        }

    } while (std::next_permutation(Digits.begin(), Digits.end())); // 순열을 계속 생성

    return MinCost;
}

 

해커랭크TheTimeInWords)
  위 문제와 마찬가지로, 알고리듬을 찾는게 아니라 미리 정의된 배열을 이용해서 푸는 문제.

cpp

코드 펼치기

#pragma once

#include <string>
#include <vector>

using namespace std;

string timeInWords(int h, int m) {
    vector<string> numbers = { "", "one", "two", "three", "four", "five", "six",
                              "seven", "eight", "nine", "ten", "eleven", "twelve",
                              "thirteen", "fourteen", "quarter", "sixteen", "seventeen",
                              "eighteen", "nineteen", "twenty", "twenty one", "twenty two",
                              "twenty three", "twenty four", "twenty five", "twenty six",
                              "twenty seven", "twenty eight", "twenty nine", "half" };

    if (m == 0) 
    {
        return numbers[h] + " o' clock";
    }
    else if (m == 15 || m == 30) 
    {
        return numbers[m] + " past " + numbers[h];
    }
    else if (m < 30) 
    {
        return numbers[m] + (m == 1 ? " minute past " : " minutes past ") + numbers[h];
    }
    else if (m == 45) 
    {
        return numbers[60 - m] + " to " + numbers[h % 12 + 1];
    }
    else 
    {
        return numbers[60 - m] + ((60 - m) == 1 ? " minute to " : " minutes to ") + numbers[h % 12 + 1];
    }
}

 

해커랭크TheBombermanGame)
  규칙을 확인하고 패턴을 파악하는 문제.

cpp

코드 펼치기

#pragma once

#include <vector>
#include <string>

using namespace std;

// 폭발 후의 그리드 상태를 반환하는 함수
vector<string> detonate(const vector<string>& InGrid) 
{
    int RowCount = InGrid.size();
    int ColumnCount = InGrid[0].size();
    vector<string> ResultGrid(RowCount, string(ColumnCount, 'O'));

    for (int i = 0; i < RowCount; ++i) 
    {
        for (int j = 0; j < ColumnCount; ++j) 
        {
            if (InGrid[i][j] == 'O')
            {
                ResultGrid[i][j] = '.';

                if (0 <= i - 1)
                {
                    ResultGrid[i - 1][j] = '.';
                }

                if (i + 1 <= RowCount - 1)
                {
                    ResultGrid[i + 1][j] = '.';
                }

                if (0 <= j - 1)
                {
                    ResultGrid[i][j - 1] = '.';
                }

                if (j + 1 <= ColumnCount - 1)
                {
                    ResultGrid[i][j + 1] = '.';
                }
            }
        }
    }
    return ResultGrid;
}

vector<string> bomberMan(int n, vector<string> grid) {
    if (n == 1)
    {
        return grid;
    }

    // 2초일 때 모든 셀이 폭탄으로 가득 찬 상태
    vector<string> FullBombGrid(grid.size(), string(grid[0].size(), 'O'));

    // 3초일 때 초기 폭탄이 폭발한 상태
    vector<string> StateAfterFirstDetonation = detonate(grid);

    // 5초일 때 첫 폭발 이후의 폭발 상태
    vector<string> StateAfterSecondDetonation = detonate(StateAfterFirstDetonation);

    // n이 2초 간격으로 반복되므로 n % 4에 따라 결과 결정
    if (n % 4 == 1) 
    {
        return StateAfterSecondDetonation;
    }
    else if (n % 4 == 3) 
    {
        return StateAfterFirstDetonation;
    }
    else 
    {
        return FullBombGrid;
    }
}

 

해커랭크TheGridSearch)
  3중 반복문 전용문제.

cpp

코드 펼치기

#pragma once

#include <string>
#include <vector>

using namespace std;

string gridSearch(vector<string> G, vector<string> P) {
    int GR = G.size(), GC = G[0].size();
    int PR = P.size(), PC = P[0].size();

    // 그리드의 각 위치에서 패턴이 시작하는지 확인
    for (int i = 0; i <= GR - PR; i++) 
    {
        for (int j = 0; j <= GC - PC; j++) 
        {
            bool bFound = true;

            // 현재 위치에서 패턴이 존재하는지 검사
            for (int x = 0; x < PR && bFound; x++) 
            {
                for (int y = 0; y < PC; y++) 
                {
                    if (G[i + x][j + y] != P[x][y]) 
                    {
                        bFound = false;
                        break;
                    }
                }
            }

            if (bFound == true) 
            {
                return "YES";
            }
        }
    }

    return "NO";
}

 

백준10709)

cpp

코드 펼치기

#pragma once

#include <iostream>
#include <string>

using namespace std;

int n, m, a[104][104];
string s;

int main() 
{
    cin >> n >> m;

    // 입력 받기
    for (int i = 0; i < n; i++) 
    {
        cin >> s;
        for (int j = 0; j < m; j++) 
        {
            if (s[j] == '.')
                a[i][j] = -1;
            else
                a[i][j] = 0;
        }
    }

    // 처리 로직
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < m; j++) 
        {
            if (a[i][j] == 0) 
            {
                int cnt = 1;
                while (a[i][j + 1] == -1) 
                {
                    a[i][j + 1] = cnt++;
                    j++;
                }
            }
        }
    }

    // 결과 출력
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < m; j++) 
        {
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

 

 

7.2 문자열
백준9996)
  substr() 함수가 핵심인 문제. 접두사와 접미사 문자열을 얻고 비교하면 끝.

cpp

코드 펼치기

#pragma once

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

using namespace std;

void Solve(int N, const string& pattern, const vector<string>& files) {
    size_t StarMarkIndex = pattern.find('*');
    std::string PrefixString = pattern.substr(0u, StarMarkIndex);
    std::string SuffixString = pattern.substr(StarMarkIndex + 1u); // 문자열에서 *를 찾아서 접두사와 접미사로 분리.

    for (const auto& FileName : files)
    {
        if (FileName.length() < PrefixString.length() + SuffixString.length()) // 파일 이름의 길이가 접두사 접미사를 합친 길이보다 짧으면 일단 실패.
        {
            std::cout << "NE" << std::endl;
        }
        else
        {
            if (FileName.substr(0, PrefixString.length()) == PrefixString &&
                FileName.substr(FileName.length() - SuffixString.length()) == SuffixString) // 접두사 접미사 확인.
            {
                std::cout << "DA" << std::endl;
            }
            else
            {
                std::cout << "NE" << std::endl;
            }
        }
    }
}

int main() {
    int N;
    cin >> N;
    string pattern;
    cin >> pattern;

    vector<string> files(N);
    for (int i = 0; i < N; ++i) {
        cin >> files[i];
    }

    Solve(N, pattern, files);

    return 0;
}

 

백준10988)
  펠린드롬 확인. reverse() 함수로 간단하게 가능.

cpp

코드 펼치기

#pragma once

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

void Solve(const string& str)
{
    std::string ReversedString = str;
    std::reverse(ReversedString.begin(), ReversedString.end());

    if (str == ReversedString)
    {
        std::cout << 1 << std::endl;
    }
    else
    {
        std::cout << 0 << std::endl;
    }
}

int main()
{
    string str;
    cin >> str;

    Solve(str);

    return 0;
}

 

백준11655)
  문자열을 특정 규칙에 따라 변환하는 문제. 아스키 인코딩과 문자열 append를 활용하면 끝.

cpp

코드 펼치기

#pragma once

#include <iostream>
#include <string>

using namespace std;

void Solve(const string& input)
{
    static const size_t MaxCharacterCount = 26u;
    static const size_t ROT13 = 13u;
    std::string ResultString = "";
    for (const char& Character : input)
    {
        if ('A' <= Character && Character <= 'Z')
        {
            ResultString += (Character - 'A' + ROT13) % MaxCharacterCount + 'A';
        }
        else if ('a' <= Character && Character <= 'z')
        {
            ResultString += (Character - 'a' + ROT13) % MaxCharacterCount + 'a';
        }
        else
        {
            ResultString += Character;
        }
    }

    std::cout << ResultString << std::endl;
}

int main() {
    string input;
    getline(cin, input);

    Solve(input);

    return 0;
}

 

해커랭크Encryption)
  1차원 문자열을 2차원으로 변환하는 문제. 특정 문자를 지워주는 erase() 함수도 활용 필요.
  중요한 부분은 열과 행을 구하는 로직임. sqrt()와 floor(), ceil() 함수를 활용함.

cpp

코드 펼치기

#pragma once

#include <string>
#include <cmath>


std::string encryption(std::string s) {
    s.erase(std::remove(s.begin(), s.end(), ' '), s.end());

    size_t StringLength = s.length();
    size_t RowCount = static_cast<size_t>(std::floor(std::sqrt(StringLength)));
    size_t ColumnCount = static_cast<size_t>(std::ceil(std::sqrt(StringLength)));
    if (RowCount * ColumnCount < StringLength)
    {
        RowCount = ColumnCount;
    }

    std::string Result;
    for (size_t j = 0; j < ColumnCount; ++j)
    {
        for (size_t i = 0; i < RowCount; ++i)
        {
            size_t D1Index = i * ColumnCount + j;
            if (D1Index < StringLength)
            {
                Result += s[D1Index];
            }
        }

        if (j < ColumnCount - 1)
        {
            Result += " ";
        }
    }

    return Result;
}

 

해커랭크HighestValuePalindrome)
  주어진 숫자형태 문자열으로 회문을 만들되, 가능한 최대값이 되게끔 만들어야하는 문제.

cpp

코드 펼치기

#pragma once

#include <string>
#include <vector>

std::string highestValuePalindrome(std::string s, int n, int k) {
    std::vector<bool> bModified(n, false);

    for (size_t i = 0; i < n / 2; ++i)
    {
        if (s[i] != s[n - i - 1]) 
        {
            s[i] = s[n - i - 1] = std::max(s[i], s[n - i - 1]);
            bModified[i] = true;
            --k;
        }
    }

    if (k < 0) 
    {
        return "-1";
    }

    for (size_t i = 0; i < n / 2 && 0 < k; ++i)
    {
        if (s[i] != '9') 
        {
            if (bModified[i] == true && 1 <= k) 
            {
                s[i] = s[n - i - 1] = '9';
                --k;
            }
            else if (bModified[i] == false && 2 <= k)
            {
                s[i] = s[n - i - 1] = '9';
                k -= 2;
            }
        }
    }

    if (n % 2 == 1 && 0 < k) 
    {
        s[n / 2] = '9';
    }

    return s;
}

 

 

7.3 개수 세기

백준1213)
  각 알파벳의 등장 횟수를 배열에 저장. 홀수개 알파벳이 두 개 이상이면 실패.
  절반 문자열 + 홀수알파벳 + 역순 문자열로 펠린드롬 완성.

cpp

코드 펼치기

#pragma once

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <vector>

using namespace std;

void makePalindrome(const string& name) {
    static const size_t MaxAlphabetCount = 26u;
    std::vector<size_t> AlphabetCounts(MaxAlphabetCount, 0u);
    for (const char& Alphabet : name)
    {
        ++AlphabetCounts[Alphabet - 'A']; // 알파벳 개수 카운트.
    }

    size_t OddCount = 0u;
    char OddCountAlphabet = '\0';
    for (size_t i = 0u; i < MaxAlphabetCount; ++i)
    {
        if (AlphabetCounts[i] % 2u == 1) 
        {
            ++OddCount;
            OddCountAlphabet = static_cast<char>(i) + 'A'; // 홀수개인 알파벳의 개수와 홀수개 알파벳이 뭔지 기록.
        }
    }

    if (1u < OddCount) // 홀수개인 알파벳이 2개이상이라면 펠린드롬 불가.
    {
        std::cout << "I'm Sorry Hansoo" << std::endl;
        return;
    }

    std::string PrefixString = "";
    std::string SuffixString = "";
    for (size_t i = 0u; i < MaxAlphabetCount; ++i)
    {
        size_t HalfCount = AlphabetCounts[i] / 2u;
        PrefixString += std::string(HalfCount, static_cast<char>(i) + 'A');
    }

    SuffixString = PrefixString;
    std::reverse(SuffixString.begin(), SuffixString.end());

    if (1 == OddCount)
    {
        PrefixString += OddCountAlphabet;
    }

    std::cout << PrefixString + SuffixString << std::endl;
}

int main() {
    string name;
    cin >> name;
    makePalindrome(name);
    return 0;
}

 

백준9375)
  의상 종류의 개수를 세고, 곱의 경우의 수를 활용하여 전체 경우의 수를 구함.

cpp

코드 펼치기

#pragma once

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

void Solve(int n) {
    std::unordered_map<string, size_t> ClothTypeCounts; 
    string ClothName, ClothType;
    for (size_t i = 0u; i < n; ++i)
    {
        std::cin >> ClothName >> ClothType;
        ++ClothTypeCounts[ClothType]; // 각 의상의 종류를 키로 하는 맵을 통해 의상 종류의 개수를 구해둠.
    }

    size_t CaseCount = 1u;
    for (const auto& Type : ClothTypeCounts)
    {
        CaseCount *= (Type.second + 1u); // 선택하지 않는 경우의 수 포함하여 모든 경우의 수를 구함.
    }

    std::cout << CaseCount - 1u << std::endl; // 알몸 상태는 제외.
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        Solve(n);
    }
    return 0;
}

 

해커랭크SherlockAndTheValidString)
  map을 이용하여 문자의 개수를 세고, 빈도 수도 세야하는 문제.
  등장하는 빈도수가 1회인지 아닌지가 중요.

cpp

코드 펼치기

#pragma once

#include <string>
#include <unordered_map>

std::string isValid(std::string s) {
    std::unordered_map<char, size_t> FrequencyMap;

    for (char c : s) 
    {
        ++FrequencyMap[c];
    }
    //'a' 'b' 'c' 'd'
    // 2   2   1   1

    std::unordered_map<size_t, size_t> FrequencyCountMap;
    for (auto& entry : FrequencyMap) 
    {
        ++FrequencyCountMap[entry.second];
    }
    // 1   2
    // 2   2

    if (FrequencyCountMap.size() == 1) 
    {
        return "YES";
    }
    else if (FrequencyCountMap.size() == 2) 
    {
        auto it = FrequencyCountMap.begin();
        int LeftFrequency = it->first;
        int LeftCount = it->second;
        it++;
        int RightFrequency = it->first;
        int RightCount = it->second;

        if ((LeftFrequency == 1 && LeftCount == 1) || (RightFrequency == 1 && RightCount == 1)) 
        {
            // 둘 중 한 종류의 문자가 등장하는 횟수가 1회인 경우.
            return "YES";
        }
        if ((abs(LeftFrequency - RightFrequency) == 1) && (LeftCount == 1 || RightCount == 1)) 
        {
            // 두 문자의 등장 횟수 차이가 1인데, 둘 중 하나의 개수가 1개 일때.
            return "YES";
        }
    }

    return "NO";
}

 

 

7.4 Two-Pointer

백준1940)
  투포인터를 이용해서 두 숫자의 합이 조건에 만족하는지 확인하고 푸는 문제

cpp

코드 펼치기

#pragma once

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

using namespace std;

void Solve(int M, const vector<int>& materials)
{
    std::vector<int> SortedMaterials = materials;
    std::sort(SortedMaterials.begin(), SortedMaterials.end(), std::less<int>()); // 투포인터를 위한 정렬

    size_t Left = 0u;
    size_t Right = SortedMaterials.size() - 1u;
    size_t WeaponCount = 0u;

    while (Left < Right)
    {
        int Sum = SortedMaterials[Left] + SortedMaterials[Right];
        if (Sum < M)
        {
            ++Left;
        }
        else if (Sum == M)
        {
            ++Left;
            --Right;
            ++WeaponCount;
        }
        else if (M < Sum)
        {
            --Right;
        }
    }

    std::cout << WeaponCount << std::endl;
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> materials(N);
    for (int i = 0; i < N; ++i) {
        cin >> materials[i];
    }

    Solve(M, materials);

    return 0;
}

 

 

7.5 Sliding-Window
백준2559)
  연속적인 K일의 합을 슬라이딩 윈도우로 구하고, max() 함수로 최대값 구하면 끝.

cpp

코드 펼치기

#pragma once

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

using namespace std;

void Solve(int K, const vector<int>& temperatures)
{
    static const size_t MaxTemperatureCount = temperatures.size();
    long long CurrentSum = 0;
    for (size_t i = 0u; i < K; ++i)
    {
        CurrentSum += temperatures[i];
    }

    long long MaxSum = CurrentSum;
    for (size_t i = K; i < MaxTemperatureCount; ++i)
    {
        CurrentSum = CurrentSum - temperatures[i - K] + temperatures[i];
        MaxSum = std::max(CurrentSum, MaxSum);
    }

    std::cout << MaxSum << endl;
}

int main() {
    int N, K;
    cin >> N >> K;

    vector<int> temperatures(N);
    for (int i = 0; i < N; ++i) {
        cin >> temperatures[i];
    }

    Solve(K, temperatures);

    return 0;
}

 

해커랭크BearAndSteadyGene)
  A, C, G, T의 이상적인 개수가 뭔지 이해하고, map을 이용해서 각 문자의 개수를 구함.
  map에 있는 A, C, G, T 개수를 슬라이딩 윈도우를 통해 조정하는 식.

cpp

코드 펼치기

#pragma once

#include <string>
#include <unordered_map>

int steadyGene(std::string gene) {
    int GeneStringLength = gene.length();
    int IdealCount = GeneStringLength / 4;
    std::unordered_map<char, int> GeneCountMap;

    for (char c : gene) 
    {
        ++GeneCountMap[c];
    }

    int MinGeneStringLength = GeneStringLength;
    int left = 0, right = 0;

    // 슬라이딩 윈도우를 사용하여 유전자 문자열 내의 최소 부분 문자열을 찾는다
    while (right < GeneStringLength) 
    {
        --GeneCountMap[gene[right]];
        ++right;

        // 모든 문자의 개수가 이상적으로 만족될 때까지 왼쪽 포인터를 이동한다
        while (GeneCountMap['A'] <= IdealCount && GeneCountMap['C'] <= IdealCount &&
               GeneCountMap['G'] <= IdealCount && GeneCountMap['T'] <= IdealCount) 
        {
            MinGeneStringLength = std::min(MinGeneStringLength, right - left);
            ++GeneCountMap[gene[left]];
            ++left;
        }
    }

    return MinGeneStringLength;
}

 

해커랭크LarryArray)
  3개 숫자를 잡고 정렬되어있는지 체크하는 문제.
  rotate() 함수를 통해 오른쪽 회전, is_sorted() 함수를 통해 정렬되어 있는지를 체크하는 식.

cpp

코드 펼치기

#pragma once

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

using namespace std;

// Larry's Array 정렬 가능 여부 판별 함수
string larrysArray(vector<int> A) {
    int Length = A.size();

    // 가능한 모든 회전 작업을 수행하여 정렬 시도
    for (int i = 0; i <= Length - 3; i++) 
    {
        while (A[i + 1] < A[i] || A[i + 2] < A[i + 1]) // i, i+1, i+2의 세 숫자가 정렬되지 않았다면
        {
            // 오른쪽으로 회전
            rotate(A.begin() + i, A.begin() + i + 1, A.begin() + i + 3);
            if (is_sorted(A.begin(), A.end()) == true) 
            {
                return "YES";
            }
            // 더 이상 회전이 불가능할 경우 break
            if (A[i] <= A[i + 1] && A[i + 1] <= A[i + 2]) 
            {
                break;
            }
        }
    }

    // 배열이 완전히 정렬되었는지 확인
    if (is_sorted(A.begin(), A.end()) == true)
    {
        return "YES";
    }
    else 
    {
        return "NO";
    }
}

 

 

7.6 Line-Sweeping
백준2979)
  라인스위핑으로 각 시간대에 몇 대의 차가 있는지 체크 후 Switch-Case문으로 해결.

cpp

코드 펼치기

#pragma once

#include <iostream>
#include <vector>

void Solve(int A, int B, int C, std::vector<std::pair<int, int>> trucks)
{
    static const size_t MaxTimeLimit = 100u;
    std::vector<size_t> CarCounts(MaxTimeLimit, 0u);
    for (const auto& Interval : trucks)
    {
        size_t BeginTime = Interval.first;
        size_t EndTime = Interval.second;
        for (size_t i = BeginTime; i < EndTime; ++i)
        {
            ++CarCounts[i];
        }
    }

    size_t Fee = 0u;
    for (size_t i = 0u; i < MaxTimeLimit; ++i)
    {
        switch (CarCounts[i])
        {
        case 1:
            Fee += A * 1;
            break;

        case 2:
            Fee += B * 2;
            break;

        case 3:
            Fee += C * 3;
            break;

        default:
            break;
        }
    }

    std::cout << Fee << std::endl;
}

int main() {
    int A, B, C;
    std::cin >> A >> B >> C;

    std::vector<std::pair<int, int>> trucks(3);
    for (int i = 0; i < 3; ++i) {
        std::cin >> trucks[i].first >> trucks[i].second;
    }

    Solve(A, B, C, trucks);

    return 0;
}

 

 

7.7 Greedy

코드업3301)
  거스름돈을 최소로 주는 문제라 Greedy를 떠올림. 일단 정렬하여 개수를 구하는 것이 중요.

cpp

코드 펼치기

// 16_Greedy

#include <iostream>

using namespace std;

enum { SIZE = 8 };

int main(void)
{
    int n, cnt = 0;
    cin >> n;

    int MoneyUnits[SIZE] = {50000, 10000, 5000, 1000, 500, 100, 50, 10};

    for (int i = 0; i < SIZE; ++i)
    {
        cnt += n / MoneyUnits[i];
        n = n % MoneyUnits[i];
    }

    cout << cnt;

    return 0;
}

 

프로그래머스Level01예산)

cpp

코드 펼치기

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> d, int budget) {
    int answer = 0;
    
    sort(d.begin(), d.end());
    
    size_t uSize = d.size();
    for (size_t i = 0; i < uSize; ++i)
    {
        budget -= d[i];
        if (budget < 0)
        {
            break;
        }
        ++answer;
    }
    
    return answer;
}