[프로그래머스][level 1] 완주하지 못한 선수

 

문제

https://programmers.co.kr/learn/courses/30/lessons/42576

주의할 점

 - 효율성

• bad : participant, completion 원소들 다 도는 2중 for문 돌면 O(N^2)
• good : sort()함수 사용하면 O(nlogn)
• best : 해시테이블 사용 (unordered_map): O(n)

해결 방법

 - sorting : 둘 다 sorting하고, 원소 비교

 - hash table : unordered map사용

• map : 초기 모든 원소 int값 0
• participant내의 원소를 map에서 값 1로 변경
• completion내의 원소가 map에서 값 0으로 변경
• map에서 값 1인 것 찾아서 매칭 string return

코드

1. best : hash table


2. good : sorting

* participant의 제일 마지막 원소도 되는 이유

• completion의 size보다 1큰 상태로 비교해야함
• p = participant, c = completion이라고 하면,
• p[p의 마지막] = c[c의 마지막 + 1]
• 일반 배열이었다면 c에서 접근할 수 없다며 에러를 뱉었겠지만, c는 vector
• 맨 마지막 원소의 다음에는 ""로 저장되어 있음.
• ex ) c = {"leo"} -> c[0] = "leo", c[1] = ""