CS/Algorithm
완주하지 못한 선수
Hinos
2021. 4. 30. 11:35
반응형
https://programmers.co.kr/learn/courses/30/lessons/42576
코딩테스트 연습 - 완주하지 못한 선수
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수
programmers.co.kr
문제 처음 보자마자 아 이거 5분컷 가능 ㅇㅇ 이랬다가
효율성 검사에서 막히고 좌절했음..
첫 번째 코드
public static String solution(String[] participant, String[] completion)
{
String result="";
Loop1 : for(int i = 0; i<participant.length; i++)
{
Loop2 : for(int j = 0; j < completion.length; j++)
{
if(participant[i] == null)
{
continue Loop1;
}
else if (completion[j] == null)
{
continue Loop2;
} else {
if (participant[i].equals(completion[j]))
{
participant[i] = null;
completion[j] = null;
continue Loop1;
}
}
}
}
for(int i = 0; i <participant.length; i++)
{
if(participant[i] != null)
{
result = participant[i];
break;
}
}
return result;
}
정확성 100
효율성 0...
ㅋㅋㅋㅋ
다시 고민하다가
두 배열 모두 정렬해서 순차탐색하면 더 빠르지 않을까해서 정렬 때려버림
두번째 코드
public static String solution(String[] participant, String[] completion)
{
String result = "";
Arrays.sort(participant);
Arrays.sort(completion);
for (int i = 0; i<completion.length; i++)
{
if (!participant[i].equals(completion[i]))
{
result = participant[i];
break;
}
}
if (result.equals(""))
{
result = participant[completion.length];
}
return result;
}
정렬 로직을 따로 넣으면 오히려 효율성이 더 떨어지는거 아닐까 걱정했었는데 쓸데없는 걱정이었다.. 갓머지정렬..
문제 제출하고 나서 유형을 보니 해시로 분류되어 있음..
다음에 비슷한 문제 만나면 해시로 풀어봐야겠다~~~
반응형