-
[프로그래머스] 완주하지 못한 선수 - 해시알고리즘/문제풀기 2019. 4. 16. 01:00
중복된 이름이 있을 수가 있어서 Hash를 사용해서 <중복을 방지하기 위한 숫자, 이름>으로 배열을 넣어주었다.
처음엔 participant 배열만 runner에 <숫자, 이름>을 넣고, completion은 배열을 가져와서 이중 for문으로 비교하였다. => 실패
1. 첫 번째 채점
runner와 finish에 같은 이름이 존재하면 각 해시에서 삭제해 주었다. 그리고 남은 runner의 key를 이용해 값을 answer에 저장하였다. 그랬더니 정확성은 통과였지만, 효율성 문제에서 실패하였다.
public static String solution(String[] participant, String[] completion) { String answer = ""; Arrays.sort(participant); Arrays.sort(completion); HashMap<Integer, String> runner = new HashMap<>(); HashMap<Integer, String> finish = new HashMap<>(); for(int i=0; i<participant.length; i++) { runner.put(i, participant[i]); } for(int i=0; i<completion.length; i++) { finish.put(i, completion[i]); } for(int i=0; i<participant.length; i++) { for(int j=0; j<completion.length; j++) { if(runner.get(i).equals(finish.get(j))) { runner.remove(i); finish.remove(j); break; } } } for(int k : runner.keySet()) { answer = runner.get(k); } return answer; }
2. 두 번째 채점
두 배열을 정렬을 해줘서 저장되는 순서를 같게 해주고, 이중 for문을 없애고 한번에 비교 할 수 있게 했다.
해시를 remove 해주는 것은 불필요한 코드 같아서, 값이 같지 않을 때 answer에 저장해 주었다.
여기서 break; 를 필수적으로 해주어야 하는데, 왜냐하면 중간에 중복된 값이 있다면 그 후의 값 모두 달라져서 answer에 중복된 이후의 값들도 저장되게 된다.
어차피 sort를 이용해서 정렬을 해주었기 때문에 처음 같지 않았으면 그게 정답이다.
하지만 효율성에서 테스트 하나를 통과하지 못하고 실패 했다..
class Solution { public String solution(String[] participant, String[] completion) { String answer = ""; Arrays.sort(participant); Arrays.sort(completion); HashMap<Integer, String> runner = new HashMap<>(); HashMap<Integer, String> finisher = new HashMap<>(); for(int i=0; i<participant.length; i++) { runner.put(i, participant[i]); } for(int i=0; i<completion.length; i++) { finisher.put(i, completion[i]); } for(int i=0; i<participant.length; i++) { if(!runner.get(i).equals(finisher.get(i))) { answer = runner.get(i); break; } } return answer; } }
3. 세 번째 채점
어느 부분을 줄여야 할지 고민하다가 participant.length가 계속 쓰인다는 것을 알고 변수 plength에 저장했다.
그리고 completion의 길이는 participant보다 1작기 때문에 completion.length 또한 plength-1 으로 사용했다.
이 외 다른 코드는 동일하게 채점했다.
class Solution { public String solution(String[] participant, String[] completion) { String answer = ""; Arrays.sort(participant); Arrays.sort(completion); HashMap<Integer, String> runner = new HashMap<>(); HashMap<Integer, String> finisher = new HashMap<>(); int plength = participant.length; for(int i=0; i<plength; i++) { runner.put(i, participant[i]); } for(int i=0; i<plength-1; i++) { finisher.put(i, completion[i]); } for(int i=0; i<plength; i++) { if(!runner.get(i).equals(finisher.get(i))) { answer = runner.get(i); break; } } return answer; } }
드디어 통과!!!!
'알고리즘 > 문제풀기' 카테고리의 다른 글
[프로그래머스] 타겟넘버 - DFS (0) 2019.05.21 [프로그래머스] 가장 큰 수 - 정렬 (0) 2019.05.01 [프로그래머스] K번째 수 - 정렬 (0) 2019.04.20 [프로그래머스] 위장 - 해시 (0) 2019.04.17 [프로그래머스] 전화번호 목록 - 해시 (0) 2019.04.16 댓글