프로그래머스 level2 문제들(정답률60%~)

- 최댓값과 최솟값

function solution(s) {
    let nums = s.split(' ');
    let max = Number(nums[0]);
    let min = Number(nums[0]);
    for(let i=0; i<nums.length; i++) {
        const num = Number(nums[i])
        if(max < num)
            max = num;
        if(num < min)
            min = num;
    }
    return `${min} ${max}`;
}

- JadenCase 문자열 만들기

function solution(s) {
    let before = 'b' //a:albphbet 또는 숫자 b:blank
    // a면은 toLowerCase b면은 toUpperCase하면 된다.
    let str = '';
    for(let i=0; i<s.length; i++) {
        if(before === 'b')
            str += s[i].toUpperCase();
        else if(before === 'a')
            str += s[i].toLowerCase();
        
        if(s[i] === ' ')
            before = 'b'
        else 
            before = 'a'
    }
    return str;
}

- 최솟값 만들기

function solution(A,B){
    let answer = 0;
    A.sort((a, b)=>a-b);
    B.sort((a, b)=>a-b);
    for(let i=0; i<A.length; i++) {
        answer += A[i] * B[B.length - i - 1];
    }
    return answer;
}

- 올바른 괄호

function solution(s) {
    let stack = 0;
    let len = s.length;
    for(let i=0; i<len; i++) {
        if(s[i] === '(')
            stack += 1;
        else {
            stack -= 1;
            if(stack < 0)
                return false;
        }
    }
    if(stack === 0)
        return true;
    return false;
}

- 이진 변환 반복하기

function solution(s) {
    let binaryChange = 0;
    let zeroCount = 0;
    while(s !== '1') {
        binaryChange++;
        let oneCount = 0;
        for(let i=0; i<s.length; i++) {
            if(s[i] === '1')
                oneCount +=1;
        }
        zeroCount += s.length - oneCount;
        s = oneCount.toString(2);
    }
    return [binaryChange, zeroCount];
}

- 숫자의 표현

function solution(n) {
    let num = n;
    let half = num/2;
    let answer = 1;
    // 초항 a는 1부터 n/2까지이다.
    for(let a=1; a<half; a++) {
        // n을 num과 같거나 클때까지 키워보며 합을 구해본다.
        for(let n=1; ;n++) {
            const sum = n * (2*a+n-1) / 2;
            if(sum > num) break;
            else if(sum === num) {
                answer++;
                break;
            }
        }
    }
    return answer;
}

- 다음 큰 숫자

function solution(n) {
    const nOneCount = n.toString(2).replaceAll('0','').length;
    while(true) {
        n++;
        const oneCount = n.toString(2).replaceAll('0','').length;
        if(nOneCount === oneCount)
            return n;
    }
}

- 피보나치 수

function solution(n) {
    //전전 수
    let bb = 0;
    //전 수 
    let b = 1;
    //현재 수
    let c;
    for(let i=2; i<=n; i++) {
        c = (bb + b)%1234567;
        bb = b;
        b = c;
    }
    return c;
}

- 짝지어 제거하기

function solution(s)
{
    let arr = [];
    //길이가 2 이상이고 마지막과 마지막-1번째가 같으면 제거.
    for(x of s) {
        arr.push(x);
        const len = arr.length;
        if(len >= 2) {
            if(arr[len-1] === arr[len-2]) {
                arr.length -= 2;
            }
        }
    }
    return arr.length===0?1:0;
}

- 카펫

function solution(brown, yellow) {
    const all = brown + yellow;
    let sqrt = Math.floor(Math.sqrt(all));
    for(let h=3; h<=sqrt; h++) {
        if(all % h === 0) {
            const w = all / h;
            if(yellow === (h-2)*(w-2))
                return [w, h];
        }
    }
    return 0;
}

- 영어 끝말잇기

function solution(n, words) {
    const set = new Set();
    let first = words[0][0];
    for(let i=0; i<words.length; i++) {
        if(set.has(words[i])) {
            return [i%n+1,Math.floor(i/n)+1];
        }
        else if(first !== words[i][0]) {
            return [i%n+1,Math.floor(i/n)+1];
        }
        set.add(words[i]);
        first = words[i][words[i].length-1];
    }
    return [0,0];
}

- 점프와 순간 이동

function solution(n)
{
    let ans = 0;
    while(n !== 0) {
        if(n % 2 === 1) {
            n -= 1;
            ans++;
        }
        n/=2;
    }
    return ans;
}

- 구명보트

function solution(people, limit) {
    let answer = 0;
    let bIdx = 0;
    let sIdx = people.length - 1;
    people.sort((a, b)=>b-a);
    while(bIdx <= sIdx) {
        if(people[bIdx] + people[sIdx] <= limit) {
            bIdx++; sIdx--;
        }
        else {
            bIdx++;
        }
        answer++;
    }
    return answer;
}

- 예상 대진표

function solution(n,a,b)
{
    var answer = 0;
    while(a !== b) {
        a = Math.ceil(a/2);
        b = Math.ceil(b/2);
        answer++;
    }
    return answer;
}

- N개의 최소공배수

유클리드 호제법을 사용한 방법이다.

function solution(arr) {
    var answer = 0;
    const gcd = (a, b) => a%b === 0 ? b : gcd(b, a%b);
    const lcm = (a, b) => a*b / gcd(a, b);
    arr.sort((a, b)=>b-a);
    while(arr.length > 1) {
        arr[0] = lcm(arr[0], arr[1]);
        arr.splice(1, 1);
    }
    return arr[0];
}

- 멀리 뛰기

처음에는 조합을 이용해 하나하나 구하려고 하였지만, 정수 오버플로가 나면서 풀 수 없게되었다. 질문하기 세션에 가보니 피보나치 수열을 이용해 풀었다고 하여 피보나치로 풀었다.

function solution(n) {
    // 1일때 정답이 1, 2일때 정답이 2이다.
    let arr = [0, 1, 2];
    for(let i=1; i<=n; i++) {
        if(i>2) arr[i] = arr[i-1] + arr[i-2];
        arr[i] %= 1234567;
    }
    return arr[n];
}

- 귤 고르기

function solution(k, tangerine) {
    let obj = {};
    tangerine.forEach((v)=>{
        if(obj[v]===undefined)
            obj[v] = 1;
        else
            obj[v] += 1;
    })
    let arr = Object.values(obj).sort((a, b)=>b-a);
    let sum = 0;
    for(let i=0; i<arr.length; i++) {
        sum += arr[i];
        if(sum >= k)
            return i+1;
    }
    return 0;
}

- 연속 부분 수열 합의 개수

function solution(elements) {
    let sumSet = new Set();
    const len = elements.length;
    // l은 길이가 몇인지
    for(let l=1; l<=len; l++) {
        // s는 시작 인덱스가 어딘지
        for(let s=0; s<len; s++) {
            //s부터 s+l까지 합은?
            let sum = 0;
            for(let i=s; i<s+l; i++) {
                sum += elements[i%len];
            }
            sumSet.add(sum);
        }
    }
    return sumSet.size;
}

- 괄호 회전하기

function solution(s) {
    let answer = 0;
    for(let i=0; i<s.length; i++) {
        if(rightParenthesis(s.slice(i)+s.slice(0, i)))
            answer++;
    }
    return answer;
}
function rightParenthesis(str) {
    let arr = [];
    for(const c of str) {
        if(c === ']' && arr[arr.length-1] === '[') {
            arr.length -= 1; continue;
        }
        else if(c === ')' && arr[arr.length-1] === '(') {
            arr.length -= 1; continue;
        }
        else if(c === '}' && arr[arr.length-1] === '{') {
            arr.length -= 1; continue;
        }
        else
            arr.push(c);
    }
    return arr.length===0?true:false;
}

- 할인 행사

function solution(want, number, discount) {
    let result = 0;
    // i는 회원가입 첫날.
    for(let i=0; i<=discount.length - 10; i++) {
        let subDiscount = discount.slice(i, i+10);
        // want가 number인것과 subDiscount가 개수가 같다면 result + 1
        const disObj = {};
        subDiscount.forEach((v)=>{
            if(disObj[v]===undefined)
                disObj[v] = 1;
            else
                disObj[v] += 1;
        })
        for(const x in want) {
            if(number[x] !== disObj[want[x]]) {
                result--; break;
            }
        }
        result++;
    }
    return result;
}

- n^2 배열 자르기

function solution(n, left, right) {
    let answer = [];
    for(let i=left; i<=right; i++) {
        const y = Math.floor(i/n);
        const x = i % n;
        answer.push(x<y?y+1:x+1);
    }
    return answer;
}

- H-Index

function solution(citations) {
    var answer = 0;
    let arr = new Array(10001).fill(0);
    for(const x of citations) {
        for(let i=0; i<=x; i++) {
            arr[i]++;
        }
    }
    for(let i=10000; i>=0; i--) {
        if(arr[i] >= i)
            return i;
    }
    return answer;
}

- 행렬의 곱셈

행렬의 곱셈은 앞행렬의 열의 개수와 뒷행렬의 행의 개수가 같을때만 정의된다.

function solution(arr1, arr2) {
    const yLen = arr1.length; //행 길이
    const xLen = arr2[0].length; //열 길이
    let answer = [];
    for(let y=0; y<yLen; y++) {
        const arr = [];
        for(let x=0; x<xLen; x++) {
            let sum = 0;
            for(let k=0; k<arr1[0].length; k++) {
                sum += arr1[y][k] * arr2[k][x];
            }
            arr.push(sum);
        }
        answer.push(arr);
    }
    return answer;
}

- [1차] 캐시

function solution(cacheSize, cities) {
    let answer = 0;
    //cash는 도시이름: index를 쌍으로 갖는 object
    const cache = {};
    for(const i in cities) {
        //캐시에 값이 있을 때
        if(Object.keys(cache).includes(cities[i].toUpperCase())) {
            cache[cities[i].toUpperCase()] = i;
            answer += 1;
        }
        //캐시에 값이 없을 때
        else {
            answer += 5;
            //캐시가 꽉찼다면 가장 오래된 캐시 삭제
            if(Object.keys(cache).length >= cacheSize) {
                //가장 오래된 캐시를 제거후 캐시에 추가.
                const min = Math.min(...Object.values(cache));
                for(const key of Object.keys(cache)) {
                    if(cache[key] == min) {
                        delete cache[key];
                        break;
                    }
                }
            }
            //캐시에 추가.
            if(cacheSize !== 0)
                cache[cities[i].toUpperCase()] = i;
        }
    }
    return answer;
}

- 의상

처음에 문제를 보고 combination으로 모든 경우를 계산하려고 했으나, 간단하게 [안입고, 1, 2] 경우의 수를 모두 곱한후 1(모두 안입는 경우)을 빼면 되는 쉬운 문제였다...

function solution(clothes) {
    let answer = 1;
    let obj = {};
    for(const cloth of clothes) {
        if(obj[cloth[1]]==undefined) {
            obj[cloth[1]] = 1;
        }
        else 
            obj[cloth[1]] += 1;
    }
    const arr = Object.values(obj);
    for(let i=0; i<arr.length; i++) {
        answer *= (arr[i]+1);
    }
    answer -= 1;
    return answer;
}

- 튜플

function solution(s) {
    var answer = [];
    s = s.replaceAll('{', '[');
    s = s.replaceAll('}', ']');
    s = JSON.parse(s);
    s.sort((a, b)=>a.length-b.length);
    for(const arr of s) {
        for(const num of arr) {
            if(!answer.includes(num)) {
                answer.push(num);
                break;
            }
        }
    }
    return answer;
}

- 기능개발

function solution(progresses, speeds) {
    let answer = [];
    let index = 0;
    while(index < progresses.length) {
        for(const i in progresses) {
            progresses[i] += speeds[i];
        }
        let count = 0;
        for(let i=index; i<progresses.length; i++) {
            if(progresses[i]>=100) {
                count += 1; index += 1;
            }
            else
                break;
        }
        if(count > 0)
            answer.push(count);
    }
    return answer;
}

- 프로세스

function solution(priorities, location) {
    let count = 0;
    while(priorities.length !== 0) {
        const max = Math.max(...priorities);
        let priority = priorities.shift();
        location -= 1;
        // 최고우선순위가 아니라면 다시 큐에 넣는다.
        if(max !== priority) {
            priorities.push(priority);
        }
        else {
            count++;
            if(location === -1)
                return count;
        }
        if(location === -1)
            location += priorities.length;
    }
    return count;
}

- [1차] 뉴스 클러스터링

function solution(str1, str2) {
    str1 = str1.toUpperCase();
    str2 = str2.toUpperCase();
    let obj1 = {};
    let obj2 = {};
    let sumObj = {};
    let intersection = 0;
    let union = 0;
    //obj를 만들자.
    for(let i=0; i<str1.length - 1; i++) {
        let key = str1[i] + str1[i+1];
        if(/[^A-Z]/.test(key))
            continue;
        if(obj1[key] === undefined)
            obj1[key] = 1;
        else
            obj1[key]++;
    }
    for(let i=0; i<str2.length - 1; i++) {
        let key = str2[i] + str2[i+1];
        if(/[^A-Z]/.test(key))
            continue;
        if(obj2[key] === undefined)
            obj2[key] = 1;
        else
            obj2[key]++;
    }
    //교집합의 개수는 한쪽 obj의 키들을 추출해, 그 키들의 최소개수들의 값
    for(let key of Object.keys(obj1)) {
        console.log(key);
        intersection += Math.min(obj1[key], obj2[key]?obj2[key]:0);
        //합집합 만드는 과정
        sumObj[key] = obj1[key];
    }
    //합집합의 개수는 두 obj의 최대값들을 더한 값.
    for(let key of Object.keys(obj2)) {
        sumObj[key] = Math.max(obj2[key], obj1[key]?obj1[key]:0)
    }
    for(let val of Object.values(sumObj)) {
        union += val;
    }
    //집합A와 B가 모두 공집합일때는 1로 정의한다.
    if(Object.values(obj1).length === 0 && Object.values(obj2).length === 0)
        return 65536;
    return Math.floor(intersection/union * 65536);
}

- 피로도

순열을 사용하는 문제인데, getPermutations함수를 잘 사용하자.

function solution(k, dungeons) {
    var answer = -1;
    let arr = [];
    for(let i=0; i<dungeons.length; i++)
        arr.push(i);
    const getPermutations = function (arr, selectNumber) {
        const results = [];
        if (selectNumber === 1) return arr.map((el) => [el]); 
        arr.forEach((fixed, index, origin) => {
            const rest = [...origin.slice(0, index), ...origin.slice(index+1)] 
            const permutations = getPermutations(rest, selectNumber - 1); 
            const attached = permutations.map((el) => [fixed, ...el]); 
            results.push(...attached); 
        });
        return results; 
    }
    const permutations = getPermutations(arr, dungeons.length);
    for(let x of permutations) {
        let tireness = k;
        let count = 0;
        for(let i=0; i<x.length; i++) {
            if(tireness>= dungeons[x[i]][0]) {
                tireness-= dungeons[x[i]][1];
                count++;
            }
        }
        if(answer < count) answer = count;
    }
    return answer;
}

- 전화번호 목록

접두사==접두어: 낱말의 앞에 붙는 것.

sort하면 i번째와 바로 뒤에것만 비교하면 된다는 것을 알 수 있다.

function solution(phone_book) {
    let len = phone_book.length;
    phone_book.sort();
    if(len === 1) return true;
    for(let i=0; i<len - 1; i++) {
        if(phone_book[i] == phone_book[i+1].slice(0, phone_book[i].length))
            return false;
    }
    return true;
}

- 타겟 넘버

dfs, bfs문제라던데 그렇게 풀지 않았다. 2진법을 활용해 풀었다.

def solution(numbers, target):
    answer = 0
    length = len(numbers)
    count = pow(2,length)
    for x in range(count):
        sum = 0
        binStr = bin(x)[2:].zfill(len(numbers))
        for i in range(length):
            if binStr[i] == '0':
                sum += numbers[i]
            else:
                sum -= numbers[i]
        if sum == target:
            answer+=1
    return answer

후에 재귀를 활용해 다시 풀었다.

def solution(numbers, target):
    answer = 0
    length = len(numbers)
    def recursive(sum, num, idx):
        sum += num
        if idx == length:
            if sum == target:
                return 1
            else:
                return 0
        return recursive(sum, numbers[idx], idx+1) + recursive(sum, -numbers[idx], idx+1)
        
    answer = recursive(0, 0, 0)
    return answer

- k진수에서 소수 개수 구하기

정규표현식과 sqrt(num)소수 판별을 하면 된다.

def solution(n, k):
    import math
    import re
    answer = 0
    
    def toBaseNum(n, k):
        num=''
        while n >= k:
            num += str(n % k)
            n = n // k
        num += str(n)
        return num[::-1]
    
    def isPrimeNum(n):
        if n == 1:
            return False
        for x in range(2, int(math.sqrt(n))+1):
            if n % x == 0:
                return False
        return True
    
    allNum = re.findall(r'[^0]+', toBaseNum(n, k))
    for num in allNum:
        if isPrimeNum(int(num)):
            answer+=1
    return answer

- [3차] 압축

def solution(msg):
    answer = []
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    table = {}
    length = len(msg)
    for i in range(len(alphabet)):
        table[alphabet[i]] = i+1
    # 사전에 등록된 key의 최대길이
    maxLen = 1
    # 사전에서 현재 탐색중인 인덱스
    currentIdx = 0
    while currentIdx < length:
        # maxLen ~ 1까지 길이의 알파벳을 dict에 대응되는 key가 있는지 확인
        i = maxLen
        while i > 0:
            # 대응되는 key가 있을 때
            if msg[currentIdx:currentIdx+i] in table:
                answer.append(table[msg[currentIdx:currentIdx+i]])
                # 처리되지 않은 글자가 있다면 
                if msg[currentIdx+i:currentIdx+i+1] != '':
                    # table에 추가
                    table[msg[currentIdx:currentIdx+i+1]] = len(table) + 1
                    # maxLen 변경
                    if maxLen < len(msg[currentIdx:currentIdx+i+1]):
                        maxLen = len(msg[currentIdx:currentIdx+i+1])
                currentIdx += i
                break
            i -= 1
    return answer

- [3차] n진수 게임

def solution(n, t, m, p):
    answer = ''
    def toBaseNum(n, k):
        num=''
        while n >= k:
            # 나머지를 문자열에 추가
            num += "0123456789ABCDEF"[n % k]
            # 몫을 n에 저장
            n = n // k
        num += "0123456789ABCDEF"[n]
        return num[::-1]
    
    decimal = 0     # 현재숫자가 10진수로 몇인지
    baseNum = '0'   # 진수로 변환된 숫자 문자열
    numIdx = 0      # 변환된 문자열의 인덱스
    tCount = 0      # 몇번 말했는지
    count = 0       # 현재 몇번째 순서인지
    p -= 1
    while tCount < t:
        if numIdx >= len(baseNum):
            numIdx = 0
            decimal += 1
            baseNum = toBaseNum(decimal, n)
        # 자기 차례
        if count % m == p:
            tCount += 1
            answer += baseNum[numIdx]
        numIdx += 1
        count += 1
        
    return answer