221018 :: [프로그래머스] 2016년, 위장, 네트워크

2016년

👾 문제 설명
2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요.

요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT입니다.
예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요.

👾 제한 사항

• 2016년은 윤년입니다.
• 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다)

 

👾 나의 답안

function solution(a, b) {
    return new Date(2016, a - 1, b).toString().split(" ")[0].toUpperCase();
}

 

• Date 객체를 사용해서 풀이하였다. a 자리의 경우 monthIndex의 자리이므로 (ex:: 0 - Jan, 1 - Feb, 2 - Mar...) a에 -1을 해 주어야 원하는 값을 얻을 수 있다.
• new Date(2016, 3, 12).toString() // Output: Tue Apr 12 2016 00:00:00 GMT+0900 (대한민국 표준시)
• 요일만 대문자 반환하면 되므로 띄어쓰기 단위로 쪼개서 배열을 만든 뒤 인덱스 0 값을 대문자 변환 후 반환한다.

 

👾 다른 사람의 풀이

function solution(a, b) {
    const monthDay = [31,29,31,30,31,30,31,31,30,31,30,31]
    const weekDay = ["THU", "FRI", "SAT", "SUN", "MON", "TUE", "WED"]

    let days = b
    for(let i=0 ; i<a-1 ; i++)
        days += monthDay[i];

    return weekDay[days%7];
}

function solution(a, b) {
    var answer = '';
    let days= ['THU','FRI','SAT','SUN','MON','TUE','WED'];
    let months = {
        29:[2],
        30:[4,6,9,11],
        31:[1,3,5,7,8,10,12]
    }
    let sum = 0;
    for (let key in months){
      months[key].forEach(el => {
          if (el < a){
            sum = sum + Number(key);
          }
      })       
    }
      let checkedNum = (sum+b)%7;
        answer = days[checkedNum]   
    return answer;
}

 

• Date 객체를 쓰지 않은 풀이
• 두 번째 답안은 months 객체를 깔끔하게 잘 구현한 것 같다

 

---

위장

👾 문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

👾 제한 사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

 

👾 나의 답안

function solution(clothes) {
    let obj = {};
    let cnt = 1;

    for (let i = 0; i < clothes.length; i++) {
        if (obj[clothes[i][1]] >= 1) {
            obj[clothes[i][1]] += 1;
        } else {
            obj[clothes[i][1]] = 1;
        }
    }

    for (let i = 0; i < obj.length; i++) {
        cnt *= obj[key] + 1;
    }

    return cnt - 1;
}

 

• 첫 답안, 모든 테스트 케이스에서 0이 나오는 걸 보니까 for문이 의도대로 작성이 안 된 것 같음
• 빈 객체 obj 생성 후 옷의 종류(clothes[i][1])를 key라고 하고, 객체의 동일 key가 한 개 이상이면 1을 더하고, 그렇지 않으면 1로 만든다.
• 예를 들어, 얼굴 3, 상의 2, 하의 2인 경우 옷을 입는 경우의 수는 (3 + 1) * (2 + 1) * (2 + 1)이 된다. +1은 아무것도 입지 않는 경우이다. 따라서 key값에 1을 더해서 모두 곱해주면 됨.
• 스파이는 최소 한 개의 옷은 입으므로 누적된 cnt 값에서 1을 (모든 옷을 입지 않은 경우) 빼서 반환한다.

 

function solution(clothes) {
    let obj = {};
    let cnt = 1;

    for (let i = 0; i < clothes.length; i++) {
        if (obj[clothes[i][1]] >= 1) {
            obj[clothes[i][1]] += 1;
        } else {
            obj[clothes[i][1]] = 1;
        }
    }

    for (let key in obj) {
        cnt *= obj[key] + 1;
    }

    return cnt - 1;
}

 

• 테스트 케이스 모두 통과한 답안
• 객체 접근 시에는 for in 문을 써야 함!!

 

👾 다른 사람의 풀이

function solution(clothes) {
    return Object.values(clothes.reduce((obj, t)=> {
        obj[t[1]] = obj[t[1]] ? obj[t[1]] + 1 : 1;
        return obj;
    } , {})).reduce((a,b)=> a*(b+1), 1)-1;    
}

 

• 옷의 종류(obj[t[1]])로 값을 누적하고, 누적한 값 + 1을 모두 곱한 뒤 1을 빼서 리턴

 

---

네트워크

👾 문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

👾 제한 사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

 

책 안 읽은 놈보다 책 한 권 읽은 놈이 무섭다 함

예전에 컴퓨터일반 과목 공부할 때 DFS BFS 탐색 순서 같은 거 외운 적이 있어서 대충 그게 뭔지는 앎

내가 지금 책 한 권 읽은 놈인 거임

이 문제를 통해 책 두 권 정도는 읽은 놈이 될 것이다

 

그래프 탐색

• 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
  
  

깊이 우선 탐색 (DFS)

• 루트 노트(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법. 즉, 넓게 탐색하기 전에 깊게 탐색하는 것이다.
• 모든 노드를 방문하고자 하는 경우 이 방법을 선택한다.
• 이 알고리즘을 구현할 때 그래프 탐색의 경우, 어떤 노드를 방문했는지 여부를 반드시 검사해야 한다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

 

구현 코드

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
};

const DFS = (graph, startNode) => {
  const visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...graph[node], ...needVisit];
    }
  }
  return visited;
};

console.log(DFS(graph, "A"));
// ["A", "B", "D", "E", "F", "C", "G", "H", "I", "J"]

 

레퍼런스

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

https://velog.io/@sangbooom/JS-BFS-DFS

[JS] BFS, DFS

 

👾 나의 답안

function solution(n, computers) {
    let network = 0;
    let visited = Array.from({ length: n }, () => false);

    function dfs(idx) {
        visited[idx] = true;

        for (let i = 0; i < computers[idx].length; i++) {
            if (computers[idx][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }

    for (let i = 0; i < computers.length; i++) {
        if (!visited[i]) {
            dfs(i);
            network++;
        }
    }
    return network;
}

 

• 내 머리에서 나온 건 아니고... 구글링의 도움을 많이 빌림 솔직히 나의 답안이라고 하기도 민망시러움
• 방문을 마친 컴퓨터를 체크하기 위해 컴퓨터 개수만큼의 길이의 배열을 선언 후 배열의 값들을 모두 false로 둔다.
• dfs 함수를 통해 시작 컴퓨터로부터 방문 가능한 컴퓨터를 모두 방문하며 해당 컴퓨터의 visited를 true로 바꾼다.
• 새로운 네트워크를 생성할 때마다 정답을 1 증가시킨다.

 

오호라 그렇단 말이지

블로그 몇 개 찾아보니까 이 문제가 DFS 정석이라고 하던데

솔직히 이건 너무 어려웠고 그래도 비교적 만만해 보이는 문제부터 차근차근 풀어봐야겠다