프로그래머스-완주하지 못한 선수

목차

1.문제

2.풀이과정

3.다른 사람들의 과정 복기

4.소감

 

1.문제

 

 

2.풀이과정

2-1. 문제 요구사항 정리

 

문제를 읽으면서 우선은 요구사항에 대해서 정리한 내용은 아래와 같았습니다.

 

• 참가자 목록이 있는 배열 (participant) 과 완주자 목록이 있는 배열(completion)이 있고 이 중 완주를 못한 사람을 출력하는 문제 
• 각 배열에는 동명이인이 있을 수 있다. (중복이 되어 있는 경우가 있다.)
• 배열에 있는 문자열은 전부 소문자로 한다.
• 참가자는 1명에서 100000명까지

2-2. 문제를 풀기 위한 내 사고 과정

 

방법1.정렬과 배열을 활용한 방법

 

각 배열을 오름차순으로 정렬을 한다.

참가자 배열을 반복문을 돌리고 반복문 안에서 완주자 배열과 비교를 한 다음에 일치를 하지 않으면 answer 에 넣는 방식입니다. 

아래는 제가 문제를 보고 생각을 한  작성순서입니다.

 

1.참가자와 완료자의 배열을 정렬을 한다. (Arrays.sort를 사용)
2.참가자의 배열을 반복문으로 돌린다. 
3. 2번 반복문 안에서 조건문을 걸고 참가자와 완주자의 값을 비교
if(!participant[i].equals(completion[i]) {
	answer = participatent[i];
}

 

방법2.자료구조 Hash를 사용하는 방법

 

각 배열안에는 동명이인이 들어가 있다는 조건이 있기에 중복을 제거를 해야된다는 점 

그리고 중복을 제거하고 각 선수들의 이름이 어느정도 들어갔는지를 체크를 해야된다는 점 

 

이2가지를 고려를 해봤을때 해시를 써보는 방식도 괜찮다고 생각을 했습니다. 

1.HashMap<String,Integer>타입으로 hashMap을 선언
2.참가자 배열을 반복문을 사용해서 map에 key는 배열의 값 그리고 value의 경우에는 map에서 제공을 하는 
getOrDefault를 사용해서 key값의 빈도수를 체크 (map.put(key,map.getOrDefault(key,0)+1);)
3.완주자 배열을 반복문을 사용해서 map에서 저장된 빈도수를 key값만큼 뺀다.
map.put(key,map.get(key)-1); -> 이렇게 하면 완주자만큼의 빈도수가 빠지기에 나머지가 문제의 답.
4.map에 저장된 값을 반복문으로 돌리면서 map에 있는 value값이 0이 아닌 키값이 정답.

 

2-3. 코드 작성 

 

코드에 적용을 하기 전의 의사코드는 만들었으니 다음은 제가 작성을 한 코드입니다. 방법1, 2 순서대로 작성한 결과는 아래와 같습니다.

왼쪽순으로 배열의 정렬을 이용한 방법, HashMap을 이용한 방법

 

 

3.다른 사람들의 과정 복기

다음은 문제를 맞추고 난 다음에 다른 사람들이 제출한 코드를 봤습니다. 대부분은 배열의 정렬을 사용해서 비교를 하는 방법 그리고 HashMap을 사용해서 빈도수를 카운팅을 하는 방법이 주를 이뤘습니다. 제출한 코드의 대다수가 대동소이하기에 처음부터 해시(Hash) 자료구조를 선택해 접근한 내 방식이 이 문제의 출제 의도에 가장 부합하는 정석적인 풀이였음을 확신할 수 있었다. 

4.소감

특별히 기발하고 복잡한 로직을 짜는 것보다, 주어진 자료구조의 특성(Hash의 빠른 탐색 속도 O(1))을 정확히 이해하고 목적에 맞게 사용하는 '기본기'가 알고리즘 문제 해결의 핵심이라는 것을 다시 한번 느꼈다.

 

 

문제 출저

https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스