프로그래머스 Level 1 완주하지 못한 선수 찾아내기

* 해당 문제풀이는 Python을 이용했습니다.

1. 문제 파악하기

- 마라톤에 참가한 선수들이 있는데 그 수는 1명 이상, 100,000명 이하이다.

- completion의 길이는 participant의 길이보다 1 작다. → 완주하지 못한 사람은 1명이다.

- 참가자 이름은 알파벳 소문자로 이루어져 있으며 동명 이인이 있을 수 있다.

 

2. 문제 접근하기

우선 참가자 이름들이 들어 있는 participant와 완주자 이름들이 들어있는 completion은 리스트로 들어 있다. 가장 쉽게 해결하는 방법은 participant와 completion을 먼저 정렬한 다음 for문을 돌면서 같은 index 에 같은 원소가 아닌 참가자 이름을 찾아내면 된다. 파이썬은 리스트에 대한 다양한 함수들이 있으며 이 함수들을 이용하면 다른 언어보다 쉽고 빠르게 코드를 작성할 수 있다는 장점이 있다. 파이썬을 사용한다면 이 장점을 잘 사용하는 것이 중요하다.

 

3. 주의할 점

- for문을 돌릴 때 participant를 기준으로 돌리면 어떻게 될까

→ 문제 파악하기의 2번째에서 확인 할 수 있듯이, completion의 길이가 participant의 길이보다 1 작기 때문에, participant를 기준으로 돌리게 된다면 participant의 마지막 원소까지 갔을 때, index에러가 발생할 수 있다. 따라서 for문은 completion을 기준으로 해야한다.

 

- completion의 원소를 다 찾았는데도 발견을 못한 경우는?

→ for문을 통해서 completion의 원소를 다 확인했는데도 정답을 찾지 못했다는 뜻은 무엇일까? 바로 participant의 마지막 원소가 정답이라는 뜻이다. 따라서 for문을 통과한 뒤에 answer가 빈 문자열인지 확인하는 if문이 필요하다.

 

4. 정답 코드

따라서 정답 코드는 아래와 같다고 할 수 있다.

participant와 completion을 정렬한 뒤, completion을 기준으로 for문을 돌린다. 이때 participant의 i번째와 completion의 i번째 가 다르다는 것은 i번째 participant가 completion에 없다는 뜻이므로 이 사람이 완주를 하지 못한 사람이다. 정답을 찾은 뒤에는 뒤에 원소를 굳이 볼 필요가 없으므로 break문을 통해서 빠져나온다. 이렇게 찾았다면 다행이지만 completion의 마지막 원소까지 보았을 때 answer를 찾지 못한 경우(paritipant의 마지막 원소가 정답일 때)가 있으므로 if문을 통해서 확인을 해준다.

정답 코드

 

5. 문제점

이 코드는 정답처리가 되긴한다. 정답처리가 되지만 과연 이 코드에 문제가 없다고 할 수 있을까? 이런 단순한 코드에는 여러 문제가 있을 수 있지만 가장 먼저 떠오르는 것은 호율성 문제이다. 이번 문제는 level 1이기 때문에 프로그래머스에서 호율성 테스트 통과 기준을 엄청 쉽게 해놨을 것이다. 만약 실제 코딩테스트에서 이런식으로 간단하게 코드를 작성했을 경우, 시간초과가 나타날 가능성이 높다.

실제 이번 문제에서 제출 버튼을 눌렀을 때 실행시간을 보면, 만족스럽지 못할 것이다.

정확성 테스트 결과

효율성 테스트 결과

 

코드가 간단해서 나쁠건 없다. 하지만 코드가 간단하면 실행시간이 오래걸리는 경우가 많고 너무 단순하게(1줄 코드)로 작성하면 처음 보는 사람은 '이 코드를 왜 이렇게 작성했을까?' 라는 생각이 들 수 도 있다. 이 trade off관계를 잘 조절하는 것이 중요할거 같다.

 

그렇다면 이 시간 문제를 어떻게하면 조금 더 줄일 수 있을까?

그 힌트는 문제 옆에있는 해시에 있다.

프로그래머스는 문제 옆에 어떤 알고리즘을 사용하면 좋은지 나와있다.

 

해시에 대해서 간단하게 설명하자면 키값마다 다른 값이 만들어진다. 파이썬에는 hash 함수가 기본으로 사용할 수 있는데 hash("a")와 hash("b")는 다른 값이 만들어진다.

따라서 hash 함수를 이용해서 코드를 작성하면 다음과 같이 적을 수 있다.

hash 함수를 이용한 정답

 

해당 코드로 제출 버튼을 누르면 다음과 같은 시간이 걸린다.

정확성 테스트 결과

효율설 테스트 결과

 

정확성 테스트에선 그렇게 큰 차이가 없지만 효율성 테스트에선 꽤 많은 차이가 나는 것을 확인할 수 있다.

 

6. 마치며

알고리즘 문제를 풀고나면 정답을 맞춘 것도 좋지만 다른 사람은 어떻게 생각을 했고 어떤 식으로 작성했는지 확인하는 것도 도움이 많이 된다. 가끔씩은 나도 모르던 함수를 이용해서 엄청 쉽게 푼 사람들도 있으며 어떤 사람은 문제 해결 시작을 나와 다른 방향으로 진행해서 해결한 사람들도 있다.