220829 TIL 시간복잡도.. 새로운데?

오늘은 평소보다 일찍 일어나서 맑은 정신 상태로 코딩 도장 시간에 문제를 풀 수 있었다. 

오늘의 코딩 도장 문제는 뭐였을까용???

 

이거 모르는 사람 없죠..?

오늘의 문제는 완주하지 못한 선수로 이전에 한 번 풀어봤었던 문제라서 금방 풀 수 있을 줄 알았다.

우선 문제를 딱 보자마자 풀이과정이 바로 떠올라서 빠르게 작성하고 예시 테스트 케이스 다 통과시키고 프로그래머스에 빠르게 제출할 수 있었다.

근데 통과하지 못했다..

 

나는 3개의 예시 테스트를 모두 통과해서 다 맞춘 줄 알았지만 효율성 테스트에서 0점이 나왔다..

 

아래  코드가 효율성 0점짜리 코드이다.

public String solution(String[] participant, String[] completion) {
	String answer = "";
    
    List<String> participants = new LinkedList<>(Arrays.asList(participant));

    for (String value : completion) {
      for (String s : participant) {
        if (Objects.equals(value, s)) {
          participants.remove(s);
          break;
        }
      }
    }

    answer = participants.get(0);
    
    return answer;
}

아마 효율성 테스트에서 0점이 나온 이유는 이중 반복문 때문이라고 생각했다.

문제 요구사항을 보면 참가자의 수가 1명 이상 100,000명 이하인데 만일 100,000명일 경우 반복하는 횟수가 배로 증가해서 시간을 초과한 것 같다.

 

내가 생각해도 엄청 오래 걸릴 거 같은 게 만일 100,000명이 참가했을 경우 완주한 선수의 배열(길이 99,999)에서 한 명씩 뽑아온 뒤 그 선수를 참가자 배열(길이 100,000)에 모든 선수와 차례대로 비교하면 99,999 x 100,000번이 되는 거니까.... 시간이 좀 걸릴 수밖에 없는 코드였다.

 

이렇게 효율성 테스트를 통과시키기 위해 시간을 고려해서 알고리즘을 짜는 것을 시간 복잡도라고 하는 것 같다.

 

시간 복잡도란?

어떤 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 의미한다. 

만일 결과가 같은데 시간이 더 적게 걸리는 코드가 있다면 그 코드가 더 좋은 코드라고 할 수 있다.

많은 사람들이 시간이 더 적게 걸리는 효율적인 알고리즘을 구성하기 위해 시간 복잡도를 고려한다고 한다.

---

 

지금까지 코드를 짜면서 시간은 고려해본 적이 없었던 것 같았는데 오늘 처음으로 똑같은 결과를 어떻게 하면 더 빨리 계산하게 할 수 있을지 생각해봤다.

근데 저번에 풀었던 문제인데 저번에는 어떻게 푼 거지..? 그때는 효율성 테스트 같은 거 고려 안 했던 거 같은데.....

 

아무튼 이중 반복문을 안 쓰고 풀었던 나의 방법은 정렬을 이용하는 거였다.

public String solution(String[] participant, String[] completion) {
    String answer = "";

    Arrays.sort(participant);
    Arrays.sort(completion);

    answer = participant[participant.length - 1];

    for (int i = 0; i < completion.length; i += 1) {
      if (!participant[i].equals(completion[i])) {
        answer = participant[i];
        break;
      }
    }

    return answer;
}

기존의 방법은 배열에서 한 명씩 꺼내서 모든 배열의 선수와 한 명씩 비교하는 거였다면

이번에는 두 배열을 정렬한 다음에 앞에서부터 비교해서 완주자와 참가자가 서로 다르면 바로 answer에 값을 담고 break를 통해 반복문을 멈췄다.

이렇게 하면 앞에서 완주자와 참가자가 서로 다른 선수가 발견되었을 때 뒤에 불필요한 선수들까지 비교할 필요가 없어져서 걸리는 시간이 확연히 줄어드는 것을 알 수 있다.

 

아무튼 오늘 코딩 도장 시간에 지금까지와는 다른 생각을 하면서 문제를 풀어서 재미있었다.

지금까지는 어떻게 하면 문제를 풀 수 있을지에 집중을 했다면 오늘은 어떻게 하면 코드의 실행 시간을 줄일 수 있을까?? 이 쪽에 더 포커스를 맞췄다.

 

지금까지 문제만 맞히면 장땡인 줄 알았는데 시간 복잡도라는 것을 알아버린 이상 더 나은 코드를 위해 시간을 고려 안 할 수가 없어졌다.

사실 아직 내 레벨이 프로그래머스 레벨 1 문제 하나 맞추는 것도 버거울 때가 많은데 시간까지 고려한다는 건 너무 욕심인가??

 

그러면 쉬운 문제를 풀 때는 의도적 수련으로 난이도를 높여 시간 복잡도도 고려하는 수련을 해봐야겠다.