프로그래머 스 cout - peulogeulaemeo seu cout

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

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

​

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

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

문제 설명 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 가 출력됨

문제

//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을 넣었다.

References

//www.youtube.com/watch?v=22tBC3YXVPA&list=PL6YHvWRMtz7DhuPHdUZ0WLB5fNO729mbm&index=2&ab_channel=ezsw
//holicaz.tistory.com/5

만약 더 나은 풀이나 잘못된 로직이 있다면 댓글을 통해 알려주시면 감사하겠습니다 :)