본문 바로가기
Computer Science/Algorithm

프로그래머스 | Level 1 | Lesson 42576 완주하지 못한 선수 (Java)

by YIAN 2022. 1. 23.

 

 

📚 알고리즘 문제

 

코딩테스트 연습 - 완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수

programmers.co.kr

 

 

🏆 제출 코드와 요약

 

성공 코드 1 - Map을 사용한 방법

👉 GitHub URL: https://github.com/Yian-Kim/Algorithmer/blob/master/Programmers/Level-1/Programmers_lesson_42576_1.java

 

GitHub - Yian-Kim/Algorithmer: 알고리즘 문제풀기 (Algorithm Problem Solving) ~ing

:crown: 알고리즘 문제풀기 (Algorithm Problem Solving) ~ing :pushpin: - GitHub - Yian-Kim/Algorithmer: 알고리즘 문제풀기 (Algorithm Problem Solving) ~ing

github.com

 

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String, Integer> map = new HashMap<>();

        for (String key : participant) {
            map.put(key, map.getOrDefault(key, 0) + 1);
        }

        for (String key : completion) {
            map.put(key, map.get(key) - 1);
        }

        for (String key : map.keySet()) {
            if (map.get(key) != 0) {
                answer = key;
                break;
            }
        }

        return answer;
    }
}

 

성공 코드 2 - for문만 사용한 방법

👉 GitHub URL: https://github.com/Yian-Kim/Algorithmer/blob/master/Programmers/Level-1/Programmers_lesson_42576_2.java

 

GitHub - Yian-Kim/Algorithmer: 알고리즘 문제풀기 (Algorithm Problem Solving) ~ing

:crown: 알고리즘 문제풀기 (Algorithm Problem Solving) ~ing :pushpin: - GitHub - Yian-Kim/Algorithmer: 알고리즘 문제풀기 (Algorithm Problem Solving) ~ing

github.com

 

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";

        Arrays.sort(participant);
        Arrays.sort(completion);

        for (int i = 0; i < completion.length; i++) {
            if (!completion[i].equals(participant[i])) {
                answer = participant[i];
                break;
            }
        }

        return answer;
    }
}

 

실행 결과 비교

성공 코드 1 - Map을 사용한 방법 성공 코드 2 - for문만 사용한 방법
정확성 테스트
테스트 1 〉 통과 (0.05ms, 72.2MB)
테스트 2 〉 통과 (0.07ms, 78.2MB)
테스트 3 〉 통과 (0.46ms, 78.3MB)
테스트 4 〉 통과 (0.68ms, 74.3MB)
테스트 5 〉 통과 (0.60ms, 79.4MB)

효율성 테스트
테스트 1 〉 통과 (41.69ms, 81.3MB)
테스트 2 〉 통과 (87.51ms, 89.2MB)
테스트 3 〉 통과 (73.30ms, 94.9MB)
테스트 4 〉 통과 (89.37ms, 112MB)
테스트 5 〉 통과 (75.69ms, 95MB)

채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0		 정확성 테스트
테스트 1 〉 통과 (0.30ms, 73.7MB)
테스트 2 〉 통과 (0.25ms, 77.5MB)
테스트 3 〉 통과 (2.18ms, 75.2MB)
테스트 4 〉 통과 (3.89ms, 80MB)
테스트 5 〉 통과 (3.98ms, 76.8MB)

효율성 테스트
테스트 1 〉 통과 (93.98ms, 80.9MB)
테스트 2 〉 통과 (209.70ms, 104MB)
테스트 3 〉 통과 (245.44ms, 95.2MB)
테스트 4 〉 통과 (314.11ms, 95.8MB)
테스트 5 〉 통과 (354.21ms, 95.3MB)

채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0

 

 

📑 문제 설명


수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

  • 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
  • completion의 길이는 participant의 길이보다 1 작습니다.
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
  • 참가자 중에는 동명이인이 있을 수 있습니다.

 

입출력 예

participant completion return
["leo", "kiki", "eden"] ["eden", "kiki"] "leo"
["marina", "josipa", "nikola", "vinko", "filipa"] ["josipa", "filipa", "marina", "nikola"] "vinko"
["mislav", "stanko", "mislav", "ana"] ["stanko", "ana", "mislav"] "mislav"

 

입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

출처

 

🎯 문제 해설


마라톤에 참여한 선수들의 이름이 담긴 배열 String[] participant와 완주한 선수들의 이름이 담긴 배열 String[] completion이 주어지는데, 참여한 선수들 이름 중에서 완주하지 않은 선수의 이름을 String으로 반환하면 됩니다.

 

 

✍ 풀이과정

 

성공 코드 1 - Map을 사용한 방법

 

마라톤에 참여한 선수들의 이름이 담긴 배열 String[] participant를 Map에 넣어줍니다. 여기서 하단의 코드는 map에서 key 값에 해당하는 값을 가져와서 +1 하거나, 없으면 0으로 설정한 뒤 +1로 하겠다는 뜻입니다.

 

map.getOrDefault(key, 0) + 1

 

그다음, 완주한 선수들의 이름이 담긴 배열 String[] completion을 기준으로 map에 저장된 key의 값을 -1 해줍니다. 여기서 map에 남아있는 값은 0이면 완주한 선수이고, 0이 아니면 완주하지 못한 선수입니다. map.keySet()을 사용하여 값이 0이 아닌 key를 찾아서 반환해줍니다.

 

코드와 설명은 다음과 같습니다.

 

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String, Integer> map = new HashMap<>();

        for (String key : participant) {
            // 마라톤에 참여한 선수들의 이름을 map에 저장
            // key가 있으면 +1 하고 없으면 0
            map.put(key, map.getOrDefault(key, 0) + 1);
        }

        for (String key : completion) {
            // 완주한 선수들의 이름이 있으면 map에서 -1
            map.put(key, map.get(key) - 1);
        }

        for (String key : map.keySet()) {
            // 값이 0이 아닌 키, 참여한 선수들의 이름 중 남아있는 이름 반환
            if (map.get(key) != 0) {
                answer = key;
                break;
            }
        }

        return answer;
    }
}

 

성공 코드 2 - for문만 사용한 방법

 

마라톤에 참여한 선수들의 이름이 담긴 배열 String[] participant와 완주한 선수들의 이름이 담긴 배열 String[] completion을 정렬해줍니다. 그리고 제약사항에서 나왔던 것처럼, "completion의 길이는 participant의 길이보다 1 작습니다."라고 했으니 두 배열을 비교하여 같지 않은 원소를 찾아서 반환해줍니다. 두 배열에서 같지 않은 원소를 가지고 있다는 것은, 완주하지 못한 선수입니다. 이때, for 문의 효율성을 위해 원소를 찾으면 break 하도록 했습니다.

 

코드와 설명은 다음과 같습니다.

 

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";

        // 마라톤에 참가한 선수들의 배열과 완주한 선수들의 배열을 정렬
        Arrays.sort(participant);
        Arrays.sort(completion);

        for (int i = 0; i < completion.length; i++) {
            // 두 배열을 비교하여 같지 않은 원소 찾기
            if (!completion[i].equals(participant[i])) {
                answer = participant[i]; // 완주하지 않은 선수
                break; // 효율성을 위해 사용
            }
        }

        return answer;
    }
}

 

실행 결과 비교

성공 코드 1 - Map을 사용한 방법 성공 코드 2 - for문만 사용한 방법
정확성 테스트
테스트 1 〉 통과 (0.05ms, 72.2MB)
테스트 2 〉 통과 (0.07ms, 78.2MB)
테스트 3 〉 통과 (0.46ms, 78.3MB)
테스트 4 〉 통과 (0.68ms, 74.3MB)
테스트 5 〉 통과 (0.60ms, 79.4MB)

효율성 테스트
테스트 1 〉 통과 (41.69ms, 81.3MB)
테스트 2 〉 통과 (87.51ms, 89.2MB)
테스트 3 〉 통과 (73.30ms, 94.9MB)
테스트 4 〉 통과 (89.37ms, 112MB)
테스트 5 〉 통과 (75.69ms, 95MB)

채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0		 정확성 테스트
테스트 1 〉 통과 (0.30ms, 73.7MB)
테스트 2 〉 통과 (0.25ms, 77.5MB)
테스트 3 〉 통과 (2.18ms, 75.2MB)
테스트 4 〉 통과 (3.89ms, 80MB)
테스트 5 〉 통과 (3.98ms, 76.8MB)

효율성 테스트
테스트 1 〉 통과 (93.98ms, 80.9MB)
테스트 2 〉 통과 (209.70ms, 104MB)
테스트 3 〉 통과 (245.44ms, 95.2MB)
테스트 4 〉 통과 (314.11ms, 95.8MB)
테스트 5 〉 통과 (354.21ms, 95.3MB)

채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0

 

위 결과를 통해 Map을 사용한 방법이 훨씬 빠르다는 것을 알 수 있습니다.

 

 

🌸 회고

 

스터디를 진행하던 중, 새로 알게 된 내용이 있어서 정리해 보았습니다. 알고리즘 문제를 잘 푸는 편이 아니었는데 이번 문제는 비교적 쉬워서 두 가지 방법으로 풀 수 있었습니다. 문제의 종류가 해시였기 때문에, 당연히 해시로 풀어야 할 것으로 생각했었습니다. 문제를 풀 당시 정확성에서 모두 맞췄지만, 효율성에서는 시간 초과가 발생했던 부분에서 어려웠습니다. 학창 시절 수학 시간에 풀었던 "문제 푸는 방법 찾기" 같아서 재미있네요.

 

 

저작자표시 변경금지

댓글

티스토리툴바