딱히 할게 없을때는 알고리즘 문제를 풀면서 시간을 보내보도록 하려구 합니다.
프로그래머스에서 나온 문제들을 하나씩 풀면서 알고리즘을 공부하겠습니다.
알고리즘을 잘 못하기때문에 쉬운거부터 하나씩 풀어가면서 문제를 풀어보도록 하죠!
(참고로 Java를 사용합니다.)
[문제 Lv.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
[입출력 예 설명]
예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.
[문제 풀이]
import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
Arrays.sort(participant); //참가자를 이름 순으로 정렬 합니다.
Arrays.sort(completion); //완주자를 이름 순으로 정렬 합니다.
/*참가자와 완주자를 배열 0부터 하나씩 비교합니다. */
for(int i=0; i<completion.length; i++) {
if(participant[i].equals(completion[i])==false) {
answer=participant[i]; //만약 참가자 배열[i] 완주자 배열[i]이 동일하지 않은 위치가 완주하지 못한 선수
break;
}else
answer = participant[i+1]; // 완주하지 못한 선수가 정렬시 참가자 배열에서 마지막에 위치한 경우
}
return answer;
}
}
실행 시간은 O(n)
'알고리즘 공부 > 알고리즘 문제' 카테고리의 다른 글
| 문자열 내 맘대로 정렬하기 (0) | 2019.03.12 |
|---|---|
| 빙고 개수 카운트하기 (0) | 2019.01.31 |
| 배열 회전 결과값 확인하기 (1) | 2019.01.26 |
| 도로에 가로등 전구 달기 (0) | 2019.01.26 |
| 숫자를 한글로 읽기 (0) | 2019.01.06 |
