programmers - 완전 탐색 - 카펫

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

∙ 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
∙ 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
∙ 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

---

주어진 yellow 타일의 M x N 형태에 따라서 brown 타일의 배치가 달라지고 카펫의 가로, 세로가 달라지는 문제. 여러 가지 경우를 고려해야 한다.

function solution(brown, yellow) {
    let final = [];
    let overLap;
    let answer = [];
    
    if(yellow > 2){
        for( let i = 2 ; i < yellow ; i++){
            if( yellow % i === 0){
                answer.push([ i, yellow / i] );
            }
        }
    }else if(yellow === 2){
        return [4,3];
    }else{
        return [3,3];
    }
    
    for( let j= 0; j < answer.length ; j++){
        answer[j][0] = Math.max(answer[j][0] + 2, answer[j][1] + 2);
        answer[j][1] = Math.min(answer[j][0] + 2, answer[j][1] + 2);
        if( ( answer[j][0] + answer[j][1] - 2) === (brown / 2) ){
            final.push( [answer[j][0], answer[j][1] ])
        }
    }
    
    overLap = final.find( value => value === value);
    
    return overLap;
    
}

1) 주어진 yellow 타일이 배치될 수 있는 경우를 모두 찾기 위해 if문으로 들어간 후, 가능한 모든 경우의 조합들을 answer 배열에 차례대로 넣는다. 중복이 발생할 수 있다.
2) 사실상 yellow가 1~2장일 땐 답이 정해져 있으므로 else문에 처리.
3) brown타일이 붙여진 최종 카펫의 가로의 길이 세로의 길이는 answer 원소들(yellow 타일들의 조합)에 2를 더 해주는 구조.
4) ' (가로+세로) - 2'의 값이 브라운 타일 갯수의 절반이면 최종 후보군 final배열로 넣는다.
5) 중복된 경우는 있지만 하나만 출력해주기 위해 overLap에 할당해서
마지막 리턴.

+) yellow 타일이 여러 개의 조합이 생길 수 있고, 각 조건에 맞게 정해진 brown 타일의 갯수로 채워줄 수 있는지 필터링해야 하는 부분에서 시간이 소요되었다. 각 카펫의 모서리 엣지에 붙는 타일들도 케어해서 풀어야 한다.

아래는 직관적인 다른 사람의 풀이

function solution(brown, yellow) {
    let answer = [];
    for (let i = 3; i <= (brown+yellow)/i; i++) {
        let x = Math.floor((brown+yellow)/i);
        if( (x-2)*(i-2)=== yellow) {
            break;
        }
    }

    return [x,i];
}

+) python version

def solution(brown, yellow):
    answer = []
    final = []
    overlap = []
    
    if yellow > 2:
        for i in range(2, yellow):
            if yellow % i == 0: answer.append([i, yellow / i])
    elif yellow == 2: return [4, 3]
    else: return [3, 3]
    
    
    for j in range(0, len(answer)):
        answer[j][0] = max(answer[j][0] + 2, answer[j][1] + 2)
        answer[j][1] = min(answer[j][0] + 2, answer[j][1] + 2)
        
        if answer[j][1] + answer[j][0] - 2 == brown / 2:
            if final.count([answer[j][0], answer[j][1]]) == 0:
                final.append(answer[j][0])
                final.append(answer[j][1])
    
    return final