(TIL) 20210529

1.Facts(한 것)

---

• C++, 자바스크립트로 프로그래머스 문제 풀기
• 알고리즘 수업 듣기
• 자료구조 정리 및 포스팅

2.Findings(배운 것)

---

"문제를 잘 읽어라"(제발)

프로그래머스 문제 중 '가장 큰 수'라는 문제가 있다.

이 문제는 이전에도 풀었지만, 다시 한번 풀어보고 싶어 한번 더 풀게 되었고, 그때와는 다른 방식으로 접근하고 싶었다.

문제에서 요구하는 것은 숫자가 든 배열에서 숫자를 정렬하여 가장 큰 수를 리턴하는 것이었다.

가장 쉽게 생각할 수 있는 풀이방법은 문자열로 바꾸어 배열에 넣은 후

비교 함수를 만들어 기준에 따라 정렬한 후 max값을 반환하는 것이다.

이번에는 C++ 내장함수인 next_element를 사용해 보고 싶어서 아래와 같은 코드를 짜봤다.

 

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

using namespace std;

vector<int> arr;

string solution(vector<int> numbers) {
    string answer = "";
    sort(numbers.begin(), numbers.end());
    do {
        string s = "";
        for(int i = 0; i < numbers.size(); i++) {
            s += to_string(numbers[i]);
        }
        arr.push_back(stoi(s));
    } while(next_permutation(numbers.begin(), numbers.end()));
    answer += to_string(*max_element(arr.begin(), arr.end()));
    return answer;
}

 

테스트 케이스를 정상적으로 통과했다는 문구와 함께 설렘도 잠시, 코드를 실행하니, 케이스 10개중 9개가 터졌다.(뭐지?)

그리고 왜 그런걸까 생각해보니....시간복잡도 때문이었다.(문제를 잘 읽자)

조건에서 numbers의 길이가 10만 이하였기 때문에 next_permutation의 시간복잡도가 O(n)이었고,

이를 while문으로 돌리다 보니 시간복잡도는 1초를 초과했다.

시도는 좋았기 때문에 만족하며,

문제를 잘 읽어야 한다는 교훈을 초등학교때부터 매번 머릿속에 다시 새기는 나를 발견하고는 조금 씁쓸했다.

 

 

3.Feeling(느낀 점)

---

기수정렬에서 배열 접근이 11N+4R인 이유를 이제야 알았다.

그리고 Best running time은 2N, Worst running time은 2NW인 것도 머리에 다시 한번 새겼다.

 

4.Affirmation(자기 선언)

---

• 나는 매일 성장하는 개발자이다.
• 나는 배우는 것을 즐기는 사람이다.