[알고리즘]프로그래머스LV.1 - 대충 만든 자판(JS)

문제

 

풀이

function solution(keymap, targets) {
  const answer = [];
  const map = new Map();

    //keymap 순환
  for (const key of keymap) {
    // key를 순환
    for (let i = 0; i < key.length; i++) {
       //만약에 map에 key[i]가 없거나 , i+1 보다 map.get(key[i]) 가 더 작을때에
        //map에 key[i]와 밸류값으로 i+1을 추가함 (그버튼과 , 그버튼을 누르기 위한 최소 횟수가 저장될것임)
      if (!map.has(key[i]) || i + 1 < map.get(key[i]))
          map.set(key[i], i + 1);
    }
  }

    //각 요소를 target이라는 이름으로 targets를 순회함
  for (const target of targets) {
      //count를 할당해주고
    let count = 0;
      //target[i]를 순회하면서
    for (let i = 0; i < target.length; i++) {
    //count에 map에서 target[i]와 같은 key의 밸류를 더해줌
      count += map.get(target[i]);
    }
    //answer 에 count 혹은 없을시에는 -1을 추가함
    answer.push(count || -1);
  }

  return answer;
}

 

자판에서 해당하는 알파벳을 치기위해 몇번의 클릭이 필요한지를 구하는것이 우선이다 .

맵 객체를 만들어 주어진 자판들 중에 해당하는 알파벳을 누르기위한 버튼의 수가 가장 최소한이 되는 경우의 수를 구하기 위해 조건문으로

if (!map.has(key[i]) -> map안에서 key[i]에 해당하는 알파벳이 없다면 또는 i + 1 <map.get(key[i]) ->

원래 있던 키의 밸류가 i+1 보다 크다면 새로 갱신을 해주어야 하기에(더 최소한의 클릭으로 가능)

라는 조건을 걸고 둘중 하나라도 해당한다면 map 에 set을 이용해 key[i](알파벳)에 i+1이라는 키와 밸류를 넣어준다.

 

후에 타겟을 순회하며 map.get(target[i]) 로 키를 이용해 밸류를 찾아주고 그 값을 count에 더한다.

 

만약 count가 undifined라면 -1을 추가한다.

 

map 과 set을 쓰는 상황을 알아보자

 

우선 셋을 사용한 문제는 보통 두 집합의 비교를 필요로 하는 문제에서 사용됩니다. 셋의 특성 상 중복을 허용하지 않고 값을 저장하기 때문에 첫 번째 집합을 만족시키는 원소들을 셋에 추가하고 두 번째 집합을 만족시키는 원소들을 셋에서 찾아 로직을 처리하는 방식으로 풀이합니다.

백준 1764(듣보잡) 문제의 경우 듣도 못한 사람의 명단과 보도 못한 사람의 명단이 주어질 때 듣도 보도 못한 사람의 명단을 구하는 문제입니다. 듣도 못한 사람을 셋에 저장한 후 보도 못한 사람이 그 셋에 들어있는 경우 출력하는 방식으로 풀 수 있습니다.

백준 7785(회사에 있는 사람) 문제의 경우 로그가 주어졌을 때 현재 회사에 있는 모든 사람을 구하는 문제입니다. 들어간 사람을 셋에 저장한 후 나간 사람이 있을 경우 셋에서 제거한 후 셋의 크기를 출력하는 방식으로 풀 수 있습니다. 여기서 포인트는 현재 존재하는 사람들을 내림차순으로 보여줘야하기 때문에 자동으로 셋을 정렬해주는 TreeSet을 사용하고 Collections.reverseOrder() 를 이용하여 정렬해주시면 됩니다.

맵을 이용한 문제는 이전 상태가 계속 변동되는 문제에서 사용됩니다. 맵의 특성 상 중복을 허용하지 않고 key-value 형식으로 값을 저장하기 때문에 이전 상태를 key로 하여 상태값을 value에 저장하여 로직을 처리합니다. 배열을 이용한 상태 체크(ex boolean[][] check)의 경우 이전 상태가 계속 변동될 경우 그 값을 계속 불러와야 하기 때문에 특정 경우에서 메모리 초과가 발생할 수 있어 이 경우 맵을 사용하여 상태를 처리합니다.

백준 1302(베스트셀러) 문제의 경우 오늘 하루 동안 팔린 책의 제목이 들어왔을 때 가장 많이 팔린 책의 제목을 출력하는 문제입니다. 맵에 책을 추가하면서 이미 존재한다면 값을 1씩 증가시키고 맵에 저장된 값 중 value가 가장 큰 값을 출력합니다.

백준 1525(퍼즐) 문제의 경우 빈 칸으로 퍼즐을 이동시킬 때 정리된 상태로 만드는 최소 횟수를 구하는 문제입니다. 이전 상태가 계속 바뀌기 때문에 배열을 이용해서 처리하게 되면 메모리 초과가 발생합니다. 따라서 빈 칸을 9로 변경한 후 퍼즐 정답을 "123456789"로 정리하여 현재 퍼즐의 모양을 이 방식대로 변환한 값을 key로, 이동 횟수를 value로 설정하여 bfs로 탐색하여 정답이 되었다면 value값을 리턴하는 방식으로 풀 수 있습니다.

 

출처 - https://velog.io/@gale4739/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%ED%85%8C-%EC%9C%A0%ED%98%95-%EB%B6%84%EC%84%9D-4.-%EC%85%8BSet-%EB%A7%B5Map