[알고리즘 스터디 3주 차(2)] 완주하지 못한 선수

https://school.programmers.co.kr/courses/12729/lessons/84345

프로그래머스

 

 

나의 코드 -> 실패!

틀렸지만 어쨌든 제출한 게 자랑스러운 코드이다..ㅎ

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

 

 

왜 틀렸는지를 파헤쳐보자.

 

1. 두 배열을 sorting 했었어야 한다.

Arrays.sort()
배열을 오름차순 정렬하는 메소드
* import java.util.Arrays; 하기

 

2. for문의 조건을 paricipant으로 하는 것이 아닌 completion으로 해야 했음

그 이유는 두 배열의 크기가 다르고, 배열의 값을 비교할 경우에는 길이가 짧은 배열을 기준으로 반복문을 돌려야 한다.

paricipant를 기준으로 반복문을 돌린다면 completion에는 없는 인덱스에 접근하게 되기 때문에 오류가 발생할 수 있음

 

풀이 1

import java.util.Arrays;

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

 

더 좋은 방법은 없을까?

풀이 2

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public String solution(String[] participant, String[] completion) {
       
        List<String> players = new ArrayList<>();
        
        // for(String p : partiscipant) players.add(p);
        players.addAll(Arrays.asList(participant));
        for(String c: completion){
            players.remove(c);
        }
        
        return players.get(0);
    }
}

 

 

동작은 제대로 하지만 효율성 테스트에서 통과하지 못했다.

 

병목 지점은 바로 players.remove(); 이다.

for(String c: completion){
            players.remove(c);
        }

 

그 이유는 바로 for문의 시간 복잡도는 O(n)이고 ArrayList.remove() 시간 복잡도 또한 O(n)이기 때문에

전체 프로그램의 시간 복잡도는 O(n^2)이다. (가장 높은 시간 복잡도를 따르기 때문이다.)

따라서 O(n^2)보다 시간 복잡도가 낮은 방법을 사용해야 한다.

 

* 해쉬 맵을 이용한 방법도 알려주셨는데, 아직 내 수준에서는  어려운 코드인 것 같아서 첨부하지는 않았다.

해쉬맵을 사용할 경우 O(n)이 나오기 때문에 통과!

 

따라서 위의 문제는 O(n^2) 보다 빠르면 통과되는 문제이다.

 

풀이 1이 맞을 수 있었던 이유는?

import java.util.Arrays;

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

 

Arrays.sort()의 시간 복잡도는 O(nlogn)이고, 반복문의 시간 복잡도는 O(n)이기 때문에 위 프로그램의 시간 복잡도는 O(nlogn)이 된다. 왜? O(n) < O(nlogn)이기 때문에! 

 

 

 

 💭 배운 점

• 빅오 표기법
• 경제적으로 생각해야 한다. 우리는 엔지니어니까요
• Art of programming : 프로그래밍 행위에 대해 총망라한 교과서
• 효율성 문제를 해결하는 방법
  • 병목지점을 찾기
    • 항상 루프 안에 있다.
    • 대놓고 루프는 아니지만 루프가 숨어 있는 것들(여기서는 remove())도 생각해보기
    • → 그렇기 때문에 자료구조를 공부하는 것이 중요하다.
  • 그곳을 좀 더 빠른 것으로 대체한다.
• OOP를 잘하기 위해서는
  1. 잘게 나눠야 한다.
  2. 각기 나눈 것들이 어떤 연관 관계를 갖는지 잘 설계한다.
• 그것들의 기준이 바로 SOLID이다!

그래서 4명의 해커가 만든 Gang of 4 GoF 답안지를 모으기 시작했고, 그게 바로 디자인 패턴이다!

디자인 패턴 → SOLID → OOP 이런 식으로 역순으로 공부하는 것을 추천한다.

 

외우지 말고 직접 해보자

언제 쓰이는지, 왜 써야 하는지? 안 쓰면 어떻게 되는지?

SOLID 원칙에 의해서 나왔고, 그게 어떤 문제를 해결하는데 필요한 정답인지까지 파악해야 한다.

 

💡 결론

절대적인 답은 없으니 경제적으로 생각하면 된다.

엔지니어 = 기술을 이용해서 돈을 버는 사람 

적당한 속도, 적당한 기능을 사용해서 경제적으로 만들어야 한다.