[PCCP] Lv2: 튜플(64065) 해설

문제

- 문제 링크: 튜플

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

 

(C++)

solution 1)

- updateCounts()에서 문자열 s의 길이를 N이라고 한다면, 문자열을 한번 순회하므로 시간 복잡도는 O(N)

- 반복문 내부에 sort()가 있지만 각 숫자는 최대 10만이므로 6자리를 넘지 않아 무시 가능한 연산

- solution()의 freqPairs를 정렬하는 부분에서 freqParis의 원소 개수를 M이라 한다면 시간 복잡도는 O(MlogM)

- freqPairs를 순회할 때 시간 복잡도는 O(M)

- 최종 시간 복잡도: O(N + M*logM + M) → O(N + M*logM)

#include <algorithm>
#include <vector>

using namespace std;

int counts[100001] = {};

void updateCounts(const string& s) {
    string numStr;
    // 인수로 받은 문자열 순회
    for (char ch : s) {
        // 현재 문자가 숫자일 때
        if (isdigit(ch)) {
            numStr += ch;
            // 현재 문자가 숫자가 아닐 떄
        } else {
            if (!numStr.empty()) {
                // 계수 정렬을 하기 위해 각 숫자의 개수 저장
                counts[stoi(numStr)]++;
                numStr.clear();
            }
        }
    }
}

vector<int> solution(string s) {
    vector<int> answer;
    // 집합이 담긴 문자열의 각 원소를 계수 정렬
    updateCounts(s);
    
    vector<pair<int, int>> freqPairs;
    for (int i = 1; i <= 100000; i++) {
        // 집합에 있는 웜소면 (개수, 값) 형식으로 푸시
        if (counts[i] > 0) {
            freqPairs.push_back({counts[i], i});
        }
    }
    
    // 각 원소의 개수를 기준으로 내림차순 정렬
    sort(freqPairs.rbegin(), freqPairs.rend());
    
    // 원소의 개수로 내림차순 정렬된 벡터를 순회하며 원소를 푸시
    for (const auto& p : freqPairs) {
        answer.push_back(p.second);
    }
    
    return answer;
}

solution 2)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

 

(Java)

solution 1)

- N: s의 길이

- M: s를 split()한 결과로 얻은 배열의 길이

- 처음에 split()을 수행할 때의 시간 복잡도는 O(N)이고 split()한 문자열을 정렬하기 위해 필요한 시간 복잡도는 O(MlogM)

- 이중 반복문에서는 외부 반복문은 M번, 내부 반복문은 제약 조건에서 최종  배열의 길이가 500이하, 튜플의 최대 길이도 500이라고 했으므로 최대 25,000번을 넘지 않음

- 총 시간 복잡도: O(N + MlogM + 25,000)

- M은 최대 100만이므로 25,000은 무시 가능. 최종 시간 복잡도: O(MlogM)

import java.util.Arrays;
import java.util.HashSet;

class Solution {
    public int[] solution(String s) {
        // 문자열 s에서 대괄호를 제거하고 ","을 기준으로 나누어 배열에 저장한 후 길이 기준으로 오름차순 정렬
        s = s.substring(0, s.length() - 2).replace("{", "");
        String[] arr = s.split("},");
        Arrays.sort(arr, (o1, o2) -> Integer.compare(o1.length(), o2.length()));
        
        HashSet<String> set = new HashSet<>();
        int[] answer = new int[arr.length];
        
        // 각 원소를 순회하면서 이전 원소와 차이 나는 부분을 구함
        for (int i = 0; i < arr.length; ++i) {
            String[] numbers = arr[i].split(",");
            for (String number : numbers) {
                if (!set.contains(number)) {
                    answer[i] = Integer.parseInt(number);
                    set.add(number);
                }
            }
        }
        return answer;
    }
}

solution 2)

#include<>

 

(Python)

solution 1)

- N: s의 길이

- M: s를 split()한 결과로 얻은 리스트의 길이

- 처음 split()수행시 O(N), split()한 문자열 정렬시 O(MlogM)

- 이중 반복문에는 외부 반복문은 M번, 내부 반복문은 제약 조건에서 최종 배열의 길이가 500이하, 튜플의 최대 길이도 500이하이므로 최대 25,000번 수행

- 총 시간 복잡도: O(N + MlogM + M*25,000)

def solution(s):
    # 문자열 s를 파싱하여 리스트로 변환
    s = s[2:-2].split("},{")
    s = sorted(s, key=len)
    answer = []
    
    # 각 원소를 순회하면서 이전 원소와 차이가 나는 부분을 구함
    for element in s:
        numbers = element.split(",")
        for number in numbers:
            if int(number) not in answer:
                answer.append(int(number))
    return answer

solution 2)

import

 

(JavaScript)

solution 1)

- N: s의 길이

- M: s를 split()한 결과로 얻은 배열의 길이

- 처음 split()을 수행할 때의 시간복잡도: O(N)

- split()한 문자열을 정렬하기 위해 필요한 시간 복잡도: O(MlogM)

- 이중 반복문에서는 외부 반복문은 M번, 내부 반복문은 제약 조건에서 최종 배열의 길이가 500 이하, 튜플의 최대 길이도 500이므로 최대 25,000번 수행

- 총 시간 복잡도: N + MlogM + M*25,000)

- M은 최대 100만이므로 25,000은 무시가능. 최종 시간 복잡도: O(MlogM)

function solution(s) {
    // 문자열 s를 파싱하여 배열로 변환
    const numbers = s.slice(2, -2).split("},{");
    const sorted = numbers.sort((a, b) => a.length - b.length);
    const answer = [];
    
    // 각 원소를 순회하면서 이전 원소와 차이가 나는 부분을 구함
    for (const element of sorted) {
        const nums = element.split(",");
        for (const num of nums) {
            if (!answer.includes(Number(num))) {
                answer.push(Number(num));
            }
        }
    }

    return answer;
}

solution 2)

import