[SWEA] 5658. 보물상자 비밀번호 python, c++

SW Expert Academy 5658. [모의 SW 역량테스트] 보물상자 비밀번호

SW Expert Academy

삼성 기출을 대비한 문제. 문자열을 사용하는 문제이고 쉬운 문제이다.

문자열을 회전시켜가며 k번째 큰 수를 출력하면된다. 문자열을 회전시킬때 조금 쉽게 하기위해 받은 문자열의 맨 처음글자부터 N//4까지의 글자를 복사해서 뒤에 넣어주었고 반복문을 사용해서 특정 길이까지 잘라서 set에 넣어주었다. set은 중복값이 제거되므로 넣어주기만 하면 된다.

모든 문자열을 순회한 이후엔 정렬을 한뒤 찾는 자리의 값을 반환했다.

def find_number(string, string_size, split_size, order):
    # string: modify string
    # string_size: real string length
    # split size
    ret = set()
    for i in range(split_size):
        for j in range(i, i + string_size, split_size):
            ret.add(int(string[j:j + split_size], 16))
    ret = sorted(ret)
    ret = ret[len(ret) - order]

    return ret

def main():
    T = int(input())
    for tc in range(1, T + 1):
        # 0 initiate
        N, K = map(int, input().split())
        s = input().rstrip()
        s += s[:N//4]

        answer = find_number(s, N, N//4, K)
        # 2 output
        print(f"#{tc} {answer}")


if __name__ == "__main__":
    main()

 

C++도 알고리즘은 크게 다르지 않다. c++의 set 은 정렬도 같이 되므로 원하는 정렬을 위해 연산자 오버라이딩을 해주었다. 그리고 정렬된 값을 순회하며 원하는 자리의 값을 반환해주었다. iterator를 직접 선언하지 않고 auto를 사용해서 쉽게 순회를 했다.

#include<iostream>
#include<string>
#include<set>

using namespace std;

struct Compare {
    bool operator() (const string& a, const string& b) const {
        return stoll(a, 0, 16) > stoll(b, 0, 16);
    };
};

long long find_number(string s, int real_length, int split_length, int order) {
    long long ret = 0;
    set<string, Compare> ans;
    for (int i = 0; i < split_length; i++)
    {
        for (int j = i; j < i + real_length; j += split_length)
        {
            ans.insert(s.substr(j, split_length));
        }
    }
    int cnt = 0;
    for (auto str16: ans)
    {
        cnt++;
        if (cnt == order) {
            ret = stoll(str16, 0, 16);
            cout << ret<< endl;
        }
    }
    return ret;
}

int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int n, k;
        string s;
        cin >> n >> k >> s;
        s += s.substr(0, n / 4);
        cout << "#" << test_case << " " << find_number(s, n, n / 4, k) << endl;
    }
    return 0;
}

 

이 방법은 substring을 만드는 방식이어서 속도나 메모리가 좋지 않은 방법이다. 효율적인 방법은 index로 string의 값을 읽고 조합해서 값을 만들면 된다.