42576. 완주하지 못한 선수

프로그래머스 42576번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 완주하지 못한 선수 | 프로그래머스 스쿨

풀이 1 - completion을 기준으로 Map 만들기

동명이인이 있을 수 있기 때문에 각 이름의 등장 횟수도 함께 세어줘야 했다. Map을 이용해서 이름의 등장 횟수와 이름을 매핑해주었다.

재밌었던 것은 이 문제를 2개월 전에 풀었을 때에는 completion을 기준으로 Map을 만들어서 풀었었는데, 이번에 풀 때에는 participant를 기준으로 Map을 만들어서 풀었다는 점이었다.

아이디어

“완주자 명단을 먼저 만들어두고, 참가자를 하나씩 대조하면서 명단에 없는 사람을 찾자.”

• completion을 순회하면서 Map에 완주자 정보를 저장하고
• participant를 순회하면서 Map에 없거나 카운트가 0인 사람 찾기

코드

function solution1(participant, completion) {
  // 1. completion으로 map 만들기
  const map = new Map();
  for (const person of completion) {
    if (map.has(person)) {
      map.set(person, map.get(person) + 1);
    } else {
      map.set(person, 1);
    }
  }

  // 2. participant 돌면서 map에 없는 사람 찾기
  for (const person of participant) {
    if (!map.has(person) || map.get(person) === 0) {
      return person;
    } else {
      map.set(person, map.get(person) - 1);
    }
  }

  return ""; // 모든 사람이 완주했을 경우 (문제 조건상 발생하지 않음)
}

풀이 2 - participant를 기준으로 Map 만들기

아이디어

“전체 참가자를 먼저 세어두고, 완주한 사람을 하나씩 지웠을 때 남은 한 사람이 미완주자”

• participant를 순회하며 Map에 참가자 정보 저장
• completion을 순회하며 완주한 사람의 카운트 감소
• Map을 순회하며 카운트가 0보다 큰 사람 찾기

코드

function solution2(participant, completion) {
  // 참여자 맵 초기화
  const participantMap = new Map(); // key: 이름, value: 해당하는 선수 수
  for (const name of participant) {
    if (participantMap.has(name)) {
      participantMap.set(name, participantMap.get(name) + 1);
    } else {
      participantMap.set(name, 1);
    }
  }

  // 완주자 확인
  for (const name of completion) {
    participantMap.set(name, participantMap.get(name) - 1);
  }

  // 완주하지 못한 선수 확인
  for (const [name, count] of participantMap) {
    if (count > 0) return name;
  }

  return ""; // NEVER
}

비교

completion 기준으로 Map을 만드는 방법과 participant 기준으로 Map을 만드는 방법의 가장 큰 차이는 언제 판단해서 반환하느냐에 있는 것 같다.

• completion 기준: participant를 순회하는 중간에 바로 찾아서 반환
• participant 기준: 모든 데이터를 처리한 후에 결과를 찾음

비록 for문의 개수 차이가 있긴 하지만 worse case를 기준으로 하더라도 둘 다 시간복잡도가 O(N)이기 때문에 성능상 차이는 크게 없을 것 같다…!