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

문제

- 문제 링크: 튜플

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#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<>

solution 3)

#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

solution 3)

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

solution 3)

import