[Java] 코딩테스트 연습_1

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

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

입출력 예 설명

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

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

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

출처

 

==> 소스 작성

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

 

 

---

 

이 문제를 제일 처음 봤을 때에는 사실 멘붕이었다.

어제 하루종일 들여다봤는데도 머리가 잘 안굴러 가더라...

그리고 오늘 번득 생각이 남!!!  '아, boolean 값을 줘서 구분을 하면 어떨까?'

그래서 써본 소스

1차

public String solution(String[] participant, String[] completion) {
	String answer = "";
	Boolean answerTF = null;

	for(int i=0; i<participant.length; i++){
		answerTF = false;
		for (int j=0; j<completion.length; j++ ) {
			if(participant[i].equals(completion[j])){
				answerTF = true;
			} 
		}
		if(answerTF == false) {
			answer += participant[i];
		}
	}
	return answer;
}

 는 당연히 땡이었다. 왜냐하면 동명이인을 고려하지 않은 괴상한 소스였음.

 

이리저리 다른 사람들이 올린 질문들을 보다 보니까...

HashMap을 이용하는 문제였다는 걸 확인했다.

import도 마음대로 해도 되는 거였나보다................. 후

다시 풀러 감

 

2차

import java.util.*;

한 후에 소스 고침

ArrayList participant_list = new ArrayList<>(Arrays.asList(participant));

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

은 또 땡이었다. 시도는 좋았으나 여전히 동명이인은 고려되지 않은 소스가 됨.

 

처음에 생각 했었는데, 순서를 맞추는 게 역시나 맞는 것 같다 라며 다시 도전

 

3차

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

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

	}

하지만 배열 길이가 다르니까 이걸 어떻게 처리하는지 생각해야겠지.

후

다시 풀러 감

 

4-1차

점심시간이라 찝찝하게 남겨둔 채 밥 먹으러 갔는데

고니 오라버니가 조언을 주심

'3차에서 참가자로 말고 완주자로 for문을 돌면 되지 않느냐'

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

그래서 바꿨더니 참가자 배열에서 마지막 값이 정답일 경우에는 결과를 받아오지 못하기에

마지막 반복 돌 때에 로직을 줌

결과는요~

채점을 시작합니다.
정확성  테스트
테스트 1 〉 통과 (39.23ms, 55.2MB)
테스트 2 〉 통과 (30.79ms, 54.9MB)
테스트 3 〉 통과 (39.08ms, 57.8MB)
테스트 4 〉 통과 (40.06ms, 57.5MB)
테스트 5 〉 통과 (49.33ms, 59.7MB)
효율성  테스트
테스트 1 〉 통과 (172.67ms, 91.6MB)
테스트 2 〉 통과 (280.41ms, 98.7MB)
테스트 3 〉 통과 (272.67ms, 99.9MB)
테스트 4 〉 통과 (362.28ms, 112MB)
테스트 5 〉 통과 (373.96ms, 104MB)
채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0

 

합격띠!

 

근데 아무리봐도 허접해 보이는 것임,, 느리기도 느리고,,

그 때 고니 오라버니가 보시고 다시 한 번 조언을 주심

'리턴이 꼭 밑에 있을 필요는 없다'

그래서 재 수정

 

4-2차

	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[completion.length];

결과는요~~~~

채점을 시작합니다. 
정확성  테스트 
테스트 1 〉 통과 (0.81ms, 52.5MB) 
테스트 2 〉 통과 (0.93ms, 50.8MB) 
테스트 3 〉 통과 (5.06ms, 52.7MB) 
테스트 4 〉 통과 (6.97ms, 55.2MB) 
테스트 5 〉 통과 (9.87ms, 51.3MB) 
효율성  테스트 
테스트 1 〉 통과 (120.83ms, 91.2MB) 
테스트 2 〉 통과 (178.27ms, 96.4MB) 
테스트 3 〉 통과 (242.57ms, 98.6MB) 
테스트 4 〉 통과 (262.08ms, 113MB) 
테스트 5 〉 통과 (313.03ms, 111MB) 
채점 결과 
정확성: 50.0 
효율성: 50.0 
합계: 100.0 / 100.0

 

정확성에서나 효율성에서나 훨씬 나아진 모습,, 넘나 만족스럽구만!!

 

마지막으로,,

ArrayList로 통과 로직 참고해서 리스트에서 지우는 식으로 해서 하나의 값만 남겨놓아도 될 것 같은 느낌적인 느낌

그래서 마지막 도전

 

5차

ArrayList participant_list = new ArrayList<>(Arrays.asList(participant));
int idx =0;
for(int i=0; i<completion.length; i++){
	idx = participant_list.indexOf(completion[i]);
	if (idx==-1) return completion[i]; 
	else participant_list.remove(participant_list.indexOf(completion[i]));
}
return participant_list.get(0).toString();

통과~! 한 줄 알았지만 탈락................

채점을 시작합니다. 
정확성  테스트 
테스트 1 〉 통과 (0.84ms, 52MB) 
테스트 2 〉 통과 (0.78ms, 50.3MB) 
테스트 3 〉 통과 (4.78ms, 52.5MB) 
테스트 4 〉 통과 (19.23ms, 55.1MB) 
테스트 5 〉 통과 (14.18ms, 55MB) 
효율성  테스트 
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과) 
테스트 3 〉 실패 (시간 초과) 
테스트 4 〉 실패 (시간 초과) 
테스트 5 〉 실패 (시간 초과) 
채점 결과 
정확성: 50.0 
효율성: 0.0 
합계: 50.0 / 100.0

 

이리저리 찾아보니 indexOf는 많은 자료가 있을 때에

처음부터 값을 하나하나 다 검사하여 인덱스 값을 리턴하기 때문에 효율이 많이 떨어진다고 한다.

 

 

여기까지 하고 다른 사람들의 소스를 보니,,, 와 다들 너므 잘한다ㅠ

오래 고민한 것일지 아니면 문제를 보자마자 머리에 번뜩하고 생각나서 바로 코딩 한 것일까,,,

나도 자꾸자꾸 공부해서 논리적인 머리를 계속계속 키워야겠다.

 

도와준 고니오라버니께 감사의 표시를.

감사합니당.

 

 

 

그나저나 이번 주 시간 너무 잘 가는 거 아닌가,,,