[프로그래머스] - 2월26일 ~

정말 오랜만에 코테 연습을 하는듯 하네요,,,
다시 말랑 두뇌가 되도록 열심히 ~!

 

 

2월26일

짝지어 제거하기

 

스택이다!!!!

function solution(s) {
    const stack = [];
    
    for (let char of s) {
        // 스택이 비어있거나, 스택의 가장 위의 문자와 현재 문자가 다르다면
        if (stack.length === 0 || stack[stack.length - 1] !== char) {
            stack.push(char); 
        } else {
            stack.pop(); // 스택의 가장 위의 문자와 현재 문자가 같다면 스택에서 제거한다
        }
    }
    
    return stack.length === 0 ? 1 : 0;
}

3월3일(ㅎㅎ;;;)

카펫

 

탐색문제,, 라는걸 알고 보니 더 어렵게 느껴지는것 같지만, 일단 어떻게 풀어야 할지를 먼저 생각하자

1. 가능한 모든 카펫의 가로, 세로 길이를 탐색
2. 갈색 격자의 수와 노란색 격자의 수를 이용하여 카펫의 가로와 세로 길이를 만족하는지 확인 (<<이걸 어떻게 할것인가?)
3. 만족하는 경우 해당 카펫의 가로와 세로 길이를 반환

노란색 격자가 가운데에 위치하고, 갈색 격자가 이를 감싸는 구조여야 하므로, 노란색 격자의 수를 기준으로 가능한 카펫의 가로, 세로 길이를 찾는다.

 

풀이

function solution(brown, yellow) {
    const total = brown + yellow;
    
    // 가능한 모든 카펫의 가로와 세로 길이를 탐색
    for (let width = 3; width <= Math.sqrt(total); width++) {
        if (total % width === 0) {
            const height = total / width;
            
            // 갈색 격자의 수가 맞는지 확인
            const brownCount = (width + height) * 2 - 4;
            if (brown === brownCount) {
                return [Math.max(width, height), Math.min(width, height)];
            }
        }
    }
    
    return [];
}

노란 격자가 1개라면 가로는 무조건 3이 되야하므로 3부터 시작!

카펫 전체 격자의 수의 제곱근까지 증가시킵니다 -> 모든 가로 길이 탐색을 위함

 

만약 전체 격자 수를 가로 길이로 나누었을때 0이라면 (가로길이가 전체 격자 수의 약수라면) 높이를 구합니다

갈색 격자의 수를 계산하기 위채(width + height) * 2 - 4를 하면 갈색 격자에서 각 모서리를 제외한 격자의 수가 구해집니다

 

• width가 Math.sqrt(total)까지만 반복되는 이유 : 가로와 세로 길이가 쌍으로 구성되기 때문. 가로길이가 width일때 세로길이는 total/width가 되므로, 가로길이가 Math.sqrt(total)보다 큰 경우에는 세로 길이가 total보다 커지게 되므로 카펫 형성이 불가하다