작업실

문제 링크

https://www.acmicpc.net/problem/1158

풀이

const fs = require('node:fs');
const input = fs.readFileSync('예제.txt','utf8').split(' '); // 백준 경로:'/dev/stdin'

const [n, k] = input.map(Number);
const circle = [];
const result = [];

for(let i=1;i<=n;i++) circle.push(i); //[1,2,3,4,5,6,7]

//k번째 사람을 제거한다.
//제거하고, 그 시점부터 다시 k번째

let remove = 0;
while(circle.length>0){
    remove = (remove + k-1) % circle.length;
    result.push(circle.splice(remove,1)[0]);
}

console.log(`<${result.join(', ')}>`);

💡 유형: 스택/큐

문제 링크 

https://school.programmers.co.kr/learn/courses/30/lessons/12909

구현 및 풀이

<처음 답안>

1. 첫 문자가 '('이면, 남은 문자열 중 ')'가 있는지 확인한다. 따라서 '('를 제거하고 남은 문자열을 확인한다.

2. 있으면 그 문자')' 도 제거한다. 

3. 모든 문자가 제거되면 true를 리턴한다.

4. 문자가 남아있으면 false를 리턴한다.

➡️ 정확성: 통과 / 효율성: 실패 (시간초과)

function solution(s) {  
    const arr = [...s];
    while(arr.length>0 && arr[0] === '('){
        let first = arr.shift();
        if(first === '('){
            let pairIndex = arr.findIndex((x) => x === ')');
            if (pairIndex === -1) return false;
            arr.splice(pairIndex,1); 
        } 
    }
    
    if(arr.length === 0 ) return true;
    
    return false;
    
}

시간 복잡도를 생각해보니 O(n^2)이므로 비효율적이다.

문자열을 배열로 바꾸지 않고 그냥 처리할 수 있는 방법을 다시 생각해보았다.

새로운 자료구조를 만들어서, 결과를 비교하자!

<수정한 답안>

1. 여는 괄호 (를 만나면 스택에 추가한다

2. 닫는 괄호 )를 만나면 스택에서 ( 제거 (짝을 맞춤)

3. stack.length === 0이면 모든 괄호가 짝을 이루므로 true, 그렇지 않으면 false

function solution(s) { 
    const stack = [];
    
    for(const char of s){
        if(char==='('){
            stack.push(char);
        } else { //')'
            if(stack.length === 0) return false; // )가 더 많을 경우
            stack.pop();
        }
    }
    
    return stack.length === 0; 
}

=> 시간 복잡도 O(N)**으로 최적화됨

세부적인 조건에 집중하기보다 주요 기능을 먼저 구현해야겠다.

💡 유형: 스택/큐

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42586

구현

<조건>

- 각 기능의 개발속도는 모두 다르다.

- 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다.

- progresses: 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열

- speeds: 각 작업의 개발 속도가 적힌 정수 배열

- 구하는 것: 각 배포마다 몇 개의 기능이 배포되는지

1. 각 작업마다 100%까지 작업량을 구하여 큐(days)에 삽입한다.

2. 첫 번째 작업이 완료될 때, 같이 배포할 수 있는 작업들을 큐에서 꺼내면서(shift()) 카운트한다. 

=> 같이 배포할 작업들: 첫 번째 작업보다 일찍 끝나는(작업량이 작은) 작업들

3. 한 번에 몇 개의 기능이 배포되는지 deploy 배열에 저장한다.

풀이

function solution(progresses, speeds) {
    let deploy = [];
    const days = progresses.map((progress,idx)=> Math.ceil((100-progress)/speeds[idx])); //각 작업이 완료되기까지 걸리는 날짜

    while(days.length>0){
        let count = 1;
        let first = days.shift();

        while(days.length>0 && days[0] <= first){
            days.shift();
            count++;
        }
        //배포
        deploy.push(count);
    } 

    return deploy;
}

큐 자료구조를 사용하는 것이 익숙하지 않아 오래 걸렸다. 레벨 1부터 풀어보아야겠다.

💡 유형: DFS/BFS

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/43165

구현

주어진 숫자를 적절히 더하고 빼서 타켓 넘버를 만드는 방법의 수

-> 주어진 숫자를 모든 경우의 수로 조합하고, 그 값 === target이면 답에 +1

각 숫자에는 +, - 두 가지 경우가 존재한다.

각 숫자마다 두 가지 경우 중 하나를 선택하고, 또 두 가지 경우 중 하나를 선택하는 것을 반복 => DFS

풀이

function solution(numbers, target) {
    let count = 0;
    
    const dfs = (index, sum) => {
        if(index === numbers.length){ //모든 숫자를 사용한 경우
            if(sum === target) count++;
            return;
        }
        
        dfs(index+1, sum + numbers[index]);
        dfs(index+1, sum-numbers[index]);
    }
    
    dfs(0,0);
    return count;
}

1. DFS 탐색 수행
   • index를 이용하여 현재 탐색 중인 숫자의 위치를 추적한다.
   • sum을 현재까지의 합으로 유지하여, 최종적으로 target과 비교한다.
   • 모든 숫자를 탐색한 후 sum === target이면 경우의 수를 증가시킨다.
2. 재귀 호출
   • 각 숫자에 대해 +와 -의 두 가지 선택을 적용하며 DFS 탐색을 수행한다.

재귀 함수를 생각해내는 것이 아직 좀 어려운 것 같다.

dfs, bfs에 대한 개념은 아래의 블로그를 보면서 정리했다.

https://velog.io/@sean2337/Algorithm-DFS%EC%99%80-BFS%EC%9D%98-%EC%89%AC%EC%9A%B4-%EA%B0%9C%EB%85%90-JavaScript-%EA%B5%AC%ED%98%84-%EB%B0%A9%EB%B2%95

💡 유형 : 해시

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42578

구현

하루에 최소 한 개의 의상을 입을 때, 서로 다른 옷의 조합 수

clothes: [의상의 이름, 의상의 종류] 2차원 배열

각 종류 당 하나의 옷 고를 수 있음

1. 1개의 의상을 입는 경우: 행의 개수(clothes.length)

2. 2개 이상의 의상을 입는 경우: 의상의 종류를 보고 고름 => 같은 종류끼리 모아야한다. 따라서 객체를 만들어 종류를 키로 사용. 이때 개수만 사용하면 된다.

풀이

function solution(clothes) {
    //옷 종류별로 옷을 그룹화
    const clothesObj = clothes.reduce((acc,[name, type])=>{
        acc[type] = (acc[type] || 0) + 1; //각 종류의 옷 개수를 카운트
        return acc;
    },{});
    
    //각 종류 별 옷 개수 + 1(입는 경우 +  안 입는 경우)을 곱한 뒤, 아무것도 입지 않는 경우 제외
    return Object.values(clothesObj).reduce((acc, count)=> acc * (count + 1),1) -1 ;

2차원 배열을 객체로 변환하는 방법은 아래의 블로그를 참고했다. 

https://velog.io/@rhkrgudwh/2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4-%EB%8D%B0%EC%9D%B4%ED%84%B0-key-value-%EA%B0%9D%EC%B2%B4%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0

reduce를 처음으로 제대로 사용해보았다. 초깃값을 설정해서 계산해야할 때 유용한 것 같다. reduce를 사용해서 코드를 작성하는 연습을 많이 해봐야겠다.

💡 유형: 해시

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42577

구현

어떤 번호가 다른 번호의 접두어인 경우가 있으면 false, 아니면 true

접두어 => 포함하고 있고, 인덱스가 0이여야함

1. phone_book을 순회하면서, 한 번호가 다른 번호들에 포함되는지 확인한다.

2. 포함된다면, 인덱스가 0인지 확인한다. 

=> 이렇게 생각했는데 MDN 문서를 보니 startsWith() 라는 메서드가 있었다!

풀이

function solution(phone_book) {
    //길이가 짧은 것부터 정렬
    phone_book.sort();
    
    for(let i=0;i<phone_book.length-1;i++){
        if(phone_book[i+1].startsWith(phone_book[i])){
            return false;
        }
    }
    return true;
}

처음에 i를 phone_book.length 까지 순회하게 하여 undefined 오류가 났다.. 맨 마지막은 i+1의 값이 존재하지 않기 때문이다.

sort 함수는 원 배열이 정렬된다! (복사본이 생성되는 것 아님)

계속 해시 유형 문제를 풀고 있기 때문에 개념을 정리해보았다.

🥳 해시 테이블(Hash Table)이란?
키와 값을 받아 키를 해싱(Hashing)하여 나온 index값을 저장하는 선형 자료구조
삽입은 O(1)이며 키를 알고 있다면 삭제, 탐색도 O(1)로 수행한다.

해시 테이블에 대한 개념을 잘 몰랐었는데, 나도 모르게 배열과 객체를 통해 해시 테이블을 사용하고 있었다. 

자바스크립트에서는 배열(또는 객체)를 생성하고 바로 key를 지정해 값에 접근할 수 있기 때문이다.

배열로 구현하는 방법 외에 객체, Map, Set을 사용하는 방법이 있다.

아래의 블로그에 해당 방법이 잘 정리되어있다.

https://velog.io/@93minki/JavaScript-%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94Hash-Table