[코테준비] 입문자를 위한 알고리즘 해결전략 - 1

프로그래머스 > 해시 > 완주하지 못한 선수

큰 그림

앞으로 문제풀이를 할 때 다음의 절차를 따르려고 한다 (TDD 방식과 비슷)

1. 문제를 풀기전에 종이에 문제해결을 위한 스케치를 한다.

 1-1. 큰그림을 그린다

 1-2. 벽을 세운다.

 1-3. 의문을 세운다.

2. 코딩을 시작한다.

 2-1. 큰그림을 구현한다. 테스트 케이스를 돌려서 큰그림 테스트를 통과, 벽에 대한 테스트 케이스가 실패함을 확인한다. 처음에는 무조건 테스트에 실패한다.

 2-2. 벽을 넘는다. 

 2-3. 의문을 해결한다.

3. 제출한다. 

큰그림 : 문제를 푸는 큰 틀이자 뼈대. 고양이를 그릴 때 전체적인 고양이 골격을 그리는 것을 의미. 스케치를 해 나갈 때, 고양이의 머리 -> 몸통 -> 다리 순으로 그려나가는 것이 아닌, 고양이 뼈대 -> 눈코입 -> 내장기관 이런식으로 top-down 방식으로 해결하는것을 추구한다. 이게 실제 개발과정과도 비슷하기 때문에 이 방식을 사용하기로 하였다. 
벽 : 큰 그림 이외에 예외사항들에 대한 구현을 의미 ex) 이 문제에서는 동명이인 판별법이 되겠다.
의문 : 문제에 주어진 조건에 대한 구현을 의미 ex) 문자열 길이 1-20 이하, 알파벳 20문자 이하, 선수 수 100,000명 이하 등 자잘한 조건들에 대한 구현
=> 이때, 우선순위는 당연히 큰그림 >> 벽 > 의문 이다. 이 과정이 1시간이 넘지 않도록 한다. 1시간이 넘는 순간 다른 사람의 풀이를 보고 공부한다. 

 

큰그림 완료

동명이인 빼고 다 정상출력 확인

깨달음:  == 가 아닌 .equals() 메소드를 써야 string 값이 정상적으로 비교된다. 

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer="";
        int i=0,j=0;
        for(i=0;i<participant.length;i++){
            for(j=0;j<completion.length;j++){
                if(participant[i].equals(completion[j])) break;
                if(j==completion.length-1){
                    answer = participant[i];
                    break;
                }
            }
            if(participant[i].equals(completion[j])) continue;
            if(j==completion.length-1){
                    answer = participant[i];
                    break;
            }
        }
        
        return answer;
    }
    
}

해시맵을 이용하여 '벽'을 넘었다.

즉, 동명이인 문제를 해결하였다 => 테스트 통과(예제 테스트만 통과..)

😒효율성 다 실패 

이유 : 시간복잡도가 O(n^2)임.

해시맵 활용을 더 해야 할 것 같다.

지금 나는 participant 쪽에만 해시를 이용했는데, 반대로 completion 쪽에도 이용하는 방향을 고색해봐야 할 것 같다. 

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer="";
        Map<String, Integer> hm = new HashMap<String, Integer>(); // 동명이인 판별용 해시맵
        for(int i=0; i<participant.length; i++){ 
            hm.put(participant[i], 0); 
        }

        int i=0,j=0;
        for(i=0;i<participant.length;i++){
            
            for(j=0;j<completion.length;j++){
                if(participant[i].equals(completion[j]) && (hm.get(participant[i]) == 0)){
                    hm.put(participant[i], 1); 
                    break;
                } 
                if(j==completion.length-1){
                    answer = participant[i];
                    break;
                }
            }
            if(participant[i].equals(completion[j])) continue;
            if(j==completion.length-1){
                    answer = participant[i];
                    break;
            }
        }
        
        return answer;
    }
    
}

한시간의 고민에도 풀이 방향이 나오지 않아서 다른 사람들의 풀이를 구경해보았다.

HashMap 사용하지 않은 풀이.

🤔번뜩이는 아이디어.. 처음에 정렬을 해버리면 된다!!

시간복잡도는 O(n) 이다.

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);
        int i;
        for ( i=0; i<completion.length; i++){

            if (!participant[i].equals(completion[i])){
                return participant[i];
            }
        }
        return participant[i];
    }
}

 

이외의 풀이

getOrDefault 메소드와 더불어 completion 쪽에도 해시맵을 적용하여 중복되는 동명이인에 대한 카운트를 고려해주는 동시에 O(n) 의 시간복잡도로 문제를 해결하는 방법이다.

public String solution(String[] participant, String[] completion) {
	String notRunner = "";
	HashMap<String, Integer> map = new HashMap<String, Integer>(); 
	for(String runner : participant) map.put(runner, map.getOrDefault(runner, 0) + 1);
	for(String runner : completion) map.put(runner, map.get(runner) - 1); 
	
	for(String runner : map.keySet()) {
		if(map.get(runner) != 0) {
			notRunner = runner; 
			break;
		}
	}
	
	return notRunner;
}

아 자바로 다시 하려니 어색하기도 하고 실수하는게 많다. 매일 한문제씩 최소한 꾸준히 풀어줘야 겠다. level1 문제도 이렇게 힘들어 하다니 ㅎㅎㅎ 정신 똑바로 차리고 공부 열심히 해야겠다

알고리즘은 단순히 코딩테스트 뿐만 아니라 개발을 할 때 효율적인 피드 알고리즘 구현 등 실질적으로 매우 중요한 분야이다. 절대 소홀히 해서는 안된다는 것을 저번 서버개발캠프에서 깨달았기에, 매일 최소한 못해도 1문제씩 꾸준히 3개월을 잡고 풀어야 겠다.

물론 3개월 후에도 취직을 못한다면, 계속해서 풀어야겠지만... 제발 그전에 취직에 성공하기를!