ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [프로그래머스] 완주하지 못한 선수 - 해시
    알고리즘/문제풀기 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;
        }
    }

    드디어 통과!!!!

    댓글

Designed by Tistory.