(코테) 마라톤 완주_프로그래머스

프로그래머스 코딩테스트

 

 

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

마라톤에 참여한 선수들의 이름이 담긴 배열 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"

 

 

 

 

 

내가 제시한  답.

 

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        List<String> listA = new LinkedList<>();
        List<String> listB = new LinkedList<>();

        for (String p : participant) {
            listA.add(p);
        }
        for (String c : completion) {
            listB.add(c);
        }

        Collections.sort(listA);
        Collections.sort(listB);

        for (int i = 0; i < listB.size(); i++) {
            if (!listA.get(i).equals(listB.get(i))) {
                return listA.get(i);
            }
        }
        return listA.get(listA.size() - 1); // 끝까지 다 맞으면 마지막 사람이 미완주자
    }
}

 

 

 

 

 

 

 

개선 한 답. 

 

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> map = new HashMap<>();
        
        for (String p : participant) {
            map.put(p, map.getOrDefault(p, 0) + 1);
        }
        
        for (String c : completion) {
            map.put(c, map.get(c) - 1);
        }
        
        for (String key : map.keySet()) {
            if (map.get(key) != 0) {
                return key;
            }
        }
        
        return "";
    }
}

 

 

 

 

 

 

 

++ 추가 ++ 내가 처음 제출 한 답에서 더 간략한 방법

 

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);

        for (int i = 0; i < completion.length; i++) {
            if (!participant[i].equals(completion[i])) {
                return participant[i];
            }
        }
        // 마지막 사람이 완주 못했을 경우
        return participant[participant.length - 1];
    }
}

 

 

 

 

 

 

회고

1. 문제 인식

처음 코드를 설계할 때,
**LinkedList가 순서정렬(자동 정렬)**이 된다고 착각했다.

→ 하지만 LinkedList는 정렬이 아니라 "순서 보장" 이다.
(데이터를 넣은 순서대로만 저장할 뿐, 값 기준으로 자동 정렬하지 않는다.)

→ LinkedList는 노드 방식으로 데이터를 저장하며, 순서를 유지할 뿐 정렬은 별도로 필요하다.

---

2. 코드 오류 분석

• Collections.sort() 호출을 하지 않아서
• 결국 정렬이 안 된 리스트끼리 비교하게 되어 문제를 틀리게 되었다.

---

3. 개선 방향 고민

회고해보니,
굳이 LinkedList 객체를 생성해서 복사하고 정렬하는 건 메모리 낭비였다.

→ 애초에
String 배열(participant, completion) 자체를 정렬해서 바로 비교하는 게
메모리 절약 + 코드 단순화 측면에서 더 적절했다.

---

4. 성능 관점에서 추가 학습

더 나아가,
배열을 매번 정렬하는 것보다
HashMap을 이용해 참가자 이름을 카운트하는 방식이 훨씬 빠르다는 사실도 알게 되었다.

(→ HashMap은 이름별 등장 횟수 관리가 가능해서 중복 이름 문제도 해결 가능.)

---

5. 착각과 배움

처음에는
**"중복 이름이 있으니까 Map은 쓰면 안 되겠다"**고 잘못 판단했다.

하지만,
Map에 동일한 이름이 들어오면 value를 누적(count)해서 관리하면 된다는 방법을 보고,
마치 머리에 총을 맞은 듯한 충격을 받았다.

---

6. 최종 소감

• 이번 문제를 풀면서
  **자료구조의 특성(LinkedList, 배열, Map)**과
  시간복잡도/공간복잡도까지 고민해보게 되었고,
• 스스로 부족함을 느끼면서도
  굉장히 재미있고 의미 있는 학습 경험이 되었다.

---

한줄 정리

착각을 인정하고, 더 나은 방향을 고민해보면서, 자료구조와 알고리즘의 본질을 깊게 이해하는 좋은 회고였다.

 

 

 

 

참고하면 좋은 글 

hashmap 관련 글  - https://moon-97.tistory.com/46

(java) 값이 중복되는 객체를 제거 hash set , HashMap 사용

 

컬렉션-  https://moon-97.tistory.com/39

Java Map 컬렉션 정리 – HashMap, LinkedHashMap, TreeMap

 

https://moon-97.tistory.com/41

(Java) Map 구조 정리 - ADT 관점에서의 이해 (****별 다섯개****)