프로그래머 스 cout - peulogeulaemeo seu cout

Question

오늘도 친구가 풀어보라고 준 문제

목차 Show

emluy 개발 일기
C++ - vector<string> 복사 & cout 으로 출력
조합을 찾기 위해 STL의 next_permutation을 사용하지 않은 이유
코드 구현
사용한 Data structure

딱 보자마자 앞대가리만 따서 비교하면 될거라고 생각했는데... 생각보다 예외사항이 많아서 고생했다.

정말 쉬운 방법이 있으나 처음 풀던 방식을 고수하고 푸느라 쫌 고생

알고리즘 연습 - 가장 큰 수 | 프로그래머스

문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다...

programmers.co.kr

내가 푼 방법은 일단 숫자들을 문자열로 모두 분리하여 앞자리만 떼어 비교하는 방식

아래의 테스트 케이스들을 만들어 테스트 했다.

cout << solution({40,403 }) << endl; cout << solution({ 40,405 }) << endl; cout << solution({ 40,404 }) << endl; cout << solution({ 12,121 }) << endl; cout << solution({ 2,22,223 }) << endl; cout << solution({ 21,212 }) << endl; cout << solution({41,415}) << endl; cout << solution({ 2,22 }) << endl; cout << solution({ 70,0,0,0 }) << endl; cout << solution({0,0,0,0 }) << endl; // 0이 나와야함 cout << solution({0,0,0,1000}) << endl; cout << solution({12,1213}) << endl;//1000을 넘기지만 다양한 경우를 만족시키는걸 테스트하기위해

먼저 int 배열을 string 배열로 만들고 정렬

vector<string> numbers_str; for (int i : numbers) numbers_str.push_back(to_string(i)); sort(numbers_str.begin(), numbers_str.end(), cmp);

사실 a+b 문자열이 더 큰지 b+a 문자열이 더 큰지 비교하면 끝이지만

그건 문제를 한참 풀다가 깨닳은 부분이고...

bool cmp(string a, string b){ return (a+b) > (b+a); }

원래 풀려던 방식으로도 똥고집으로 풀어냈다.

12,1213 을 예로 한쪽이 더 짧을때 앞에 붙을지 뒤에 붙을지를 구별하는 것이 핵심이었다.

각각 첫째자리 비교. 1,1 같음

둘째자리 비교 2,2 같음

셋째자리를 비교해야하는데 12는 뒷 자리가 없으므로 로테이션하여 다시 1과 1비교 같음

2와 3을 비교. 3이 더크므로 1213이 먼저 오고 12 : 121312가 만들어진다.

bool cmp(string a, string b){ char af, bf; int len = a.size() > b.size() ? a.size() : b.size(); for(int ai=0,bi=0,i=0;i<=len;(++ai)%=a.size(), (++bi) %= b.size(),i++) { af = a[ai]; bf = b[bi]; if (af > bf ) return true; else if (af == bf) continue; else return false; } return false; }

#include <string> #include <vector> #include <iostream> #include <algorithm> using namespace std; bool cmp(string a, string b){ char af, bf; int len = a.size() > b.size() ? a.size() : b.size(); for(int ai=0,bi=0,i=0;i<=len;(++ai)%=a.size(), (++bi) %= b.size(),i++) { af = a[ai]; bf = b[bi]; if (af > bf ) return true; else if (af == bf) continue; else return false; } return false; } string solution(vector<int> numbers) { string answer; vector<string> numbers_str; for (int i : numbers) numbers_str.push_back(to_string(i)); int zero = 0; sort(numbers_str.begin(), numbers_str.end(), cmp); for (string i : numbers_str){ answer += i; if (i == "0") zero++; } if (zero == numbers_str.size()) return "0"; return answer; }

emluy 개발 일기

알고리즘/c, c++

C++ - vector<string> 복사 & cout 으로 출력

yulme 2020. 10. 16. 02:51

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


int main() {
    vector<string> s1{ "hello","hi" };
    vector<string> s2 = s1;
    cout << *s2.begin();
}

또는

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


int main() {
    vector<string> s1{ "hello","hi" };
    vector<string> s2 = s1;
    vector<string>::iterator iter;
    iter = s2.begin();
    cout << *iter;
}

또는

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

int main() {
	vector<string> s1{ "hello","hi" };
	vector<string> s2 = s1;
	cout << s2.at(0);
}

=> hello 가 출력됨

문제

https://programmers.co.kr/learn/courses/30/lessons/72411

문제와 제한 사항이 조금 복잡해서 직접 읽는 것이 더 편할 것이다

접근

이번 문제 역시 직접 값들을 하나하나 찾아야 한다.

문제 해결을 2파트로 나눌 수 있다.
1. orders 배열에 있는 각 주문들이 만들 수 있는 조합을 저장하고, 총 몇번이 나오는지 기록하는 부분.
2. course 배열을 만족하는 주문 조합을 출력하는 부분.

조합을 찾기 위해 STL의 next_permutation을 사용하지 않은 이유

저번에 올린 소수 찾기 문제에서는 algorithm 라이브러리에 있는 next_permutation과 substr() 메소드를 이용해서 간단하게 조합을 찾고 set에 저장했다.

하지만 이번엔 주문의 조합 뿐 아니라 조합이 등장한 횟수까지 정확히 count해야하기에 이 방법은 불가능하다

string a = "ABCDE";
do {
	for(int i = 1; i < a.length(); i++) {
    	a.substr(0,i);
    }
    cout << a << endl;
} while (next_permutation(a.begin(),a.end()));

위의 예시처럼 next_permutation을 사용하면 ABCDE에서 나올 수 있는 모든 조합을 출력할 순 있겠지만 중복되어 등장하는 수가 생긴다
(e.g. "ABCDE"에서 "ABC"를 가져오고 "ABCED"에서 "ABC"를 또 가져오기)

따라서 unordered_map과 DFS를 사용해서 각 조합을 한번만 등장시키기 위한 코드를 짤 것이다.

코드 구현

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

using namespace std;
unordered_map<string, int> combination[11];
int maxMenu[11] = {0,};

void dfs(string order, string partial, int index) {
    if(index >= order.length()) 
        return;

    dfs(order, partial, index+1);

    partial += order[index];
    combination[partial.length()][partial]++;

    if (combination[partial.length()][partial] > maxMenu[partial.length()]) {
        maxMenu[partial.length()] = combination[partial.length()][partial];
    }

    dfs(order, partial, index+1);
}


vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;

    // 각 주문마다 dfs를 한번씩 돌리면서 조합과 횟수를 찾아낸다.
    for(string order : orders) {
        sort(order.begin(), order.end());
        //정렬된 주문의 첫번째 메뉴로 init한다.
        
        dfs(order, "", 0);
    }

    for (int num : course) {
        for(auto comb : combination[num]) {
            if (maxMenu[num] >= 2 && comb.second == maxMenu[num]) {
                answer.push_back(comb.first);
            }   
        }
    }
    
    sort(answer.begin(), answer.end());

    return answer;
}

사용한 Data structure

unordered_map<string, int> combination[MAX_MENU]
map의 key에는 메뉴조합, value에는 등장한 횟수를 저장한다 (e.g. {"ABC", 3} => 메뉴 A, B, C가 주문 목록에 3번 등장했다)
메뉴조합의 길이 (i.e. 조합된 주문의 요리 갯수) 에 따라 다른 배열에 저장한다 (e.g. "AB"는 길이가 2니 combination[2]에 저장. "BDE"는 combination[3]에 저장)
int maxMenu[MAX_MENU]
각 메뉴조합의 길이가 최대로 등장한 횟수를 저장하는 배열
문제에서 각 사람의 주문량은 최대 10개라고 했으니 MAX_MENU에 11을 넣었다.