[PCCP] Lv2: 카펫(42842) 해설

문제

- 문제 링크: 카펫

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int y = 0;
    for (size_t x = yellow; x > 0; --x){
        y = yellow / x;
        if (2*x + 2*y + 4 == brown && x*y == yellow){
            answer.push_back(x+2);
            answer.push_back(y+2);
            break;
        }
    }
    return answer;
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: totalSize

- 한 변의 최대 길이는 sqrt(N)이므로 최종 시간 복잡도는 O(sqrt(N))

class Solution {
    public int[] solution(int brown, int yellow) {
        // 격자의 총 개수 (붉은색 격자 + 흰색 격자)
        int totalSize = brown + yellow;
        // 세로 길이의 범위는 3부터 (붉은색 격자 + 흰색 격자)의 제곱근
        int sqrt = (int)Math.sqrt(totalSize);
        for (int vertical = 3; vertical <= sqrt; vertical++) {
            // 사각형 구성이 되는지 확인
            if (totalSize % vertical == 0) {
                // 사각형의 가로 길이
                int horizontal = (int)(totalSize / vertical);
                // 카펫 형태로 만들 수 있는지 확인
                if (brown == (horizontal + vertical - 2) * 2) {
                    return new int[]{horizontal, vertical}; // [가로 길이, 세로 길이]
                }
            }
        }
        return new int[]{}; // 만약 답을 찾기 못했다면 빈 리스트를 반환
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: total_size

- 한변의 최대 길이는 sqrt(N)이므로 최종 시간 복잡도: O(sqrt(N))

def solution(blue, white):
    # 격자의 총 개수(파란색 격자 + 흰색 격자)
    total_size = blue + white
    
    # 세로 길이의 범위는 3부터 (파란색 격자 + 흰색 격자)의 제곱근
    for vertical in range(3, int(total_size**0.5) + 1):
        # 사각형ㅇ 구성이 되는지 확인
        if total_size % vertical == 0:
            horizontal = (int)(total_size / vertical) # 사각형의 가로 길이
            # 카펫 형태로 만들 수 있는지 확인
            if blue == (horizontal + vertical - 2) * 2:
                return [horizontal, vertical] # [가로 길이, 세로 길이]
    return [] # 만약 답을 찾기 못했다면 빈 리스트를 반환

solution 2)

def solution(brown, yellow):
    answer = []
    for x in range(yellow,0,-1):
        y = yellow // x
        if 2*x + 2*y + 4 == brown and x*y == yellow:
            return [x+2, y+2]

solution 3)

import

 

(JavaScript)

solution 1)

- N: totalSize

- 한 변의 최대 길이는 sqrt(N)

- 최종 시간 복잡도: O(sqrt(N))

function solution(yellow, white) {
    // 격자의 총 개수 (노란 격자 + 하얀 격자)
    const totalSize = yellow + white;
    
    // 세로 길이의 범위는 3부터 (노란 격자 + 하얀 격자)의 제곱근
    for (let vertical = 3; vertical <= Math.sqrt(totalSize); vertical++) {
        // 사각형 구성이 되는지 확인
        if (totalSize % vertical === 0) {
            const horizontal = totalSize / vertical; // 사각형의 가로 길이
            
            // 카펫 형태로 만들 수 있는지 확인
            if (yellow === (horizontal + vertical - 2) * 2) {
                return [horizontal, vertical]; // [가로 길이, 세로 길이]
            }
        }
    }
    
    return []; // 만약 답을 찾지 못했다면 빈 배열을 반환
}

solution 2)

import

solution 3)

import