알고리즘 연습 [1]

완주하지 못한 자

map 부분에서 가장 낮은 난이도에 있는 문제다.

입출력 예

participant completion return

["leo", "kiki", "eden"] ["eden", "kiki"] "leo"

["marina", "josipa", "nikola", "vinko", "filipa"] ["josipa", "filipa", "marina", "nikola"] "vinko"

["mislav", "stanko", "mislav", "ana"] ["stanko", "ana", "mislav"] "mislav"

배열 두개를 비교해서 단 하나의 차이점 데이터를 찾으라는 건데, 처음 드는 생각은 물론 이중 for문 이었다. 하지만 "1명 이상 100,000명 이하입니다." 라는 조건에 걸려 최대 100억번의 반복 비교를 해보는건 너무 비효율이라고 생각. 두번째로 든 생각은 현재 문제의 특수성, 참가자와 완주자는 무조건 한명의 차이점 외에 다른점은 없다. 그래서 두개의 배열을 정렬 시키고 다른 데이터가 있으면 그냥 그대로 반환 시켜 주기로 하였다. 

for문을 한번만 사용하기 때문에 최대 10만번 이내에서 연산을 끝낼 수 있어서 그런지 일단 정확도와 효율성 둘다 테스트는 통과 했지만, 다른 답안지를 보고 아차 했던 것은 이건 hash(map)에 관련된 알고리즘 문제였다. 해시 맵에 참가자 데이터를 넣으며 getOrDefault 메소드를 통해 +1을 넣어주고 완주자 목록을 이용해서 -1을 해주면 마지막에 0값이 아닌 key에 해당하는 참가자가 완주하지 못한 한명. 이 방법은 완주하지 못한 사람이 여러명이라도 쓸 수 있는 방법! 

전화번호 목록 

한 배열 안에서 다른 번호가 해당 번호로 시작하는 경우가 있나 판단해서 true/false를 반환하는 알고리즘이었다. 일단 내가 짠 코드는 이렇다.

단순하게 startsWith 를 생각했는데 나중에 알았지만 정답자 중에서도 이걸 쓴 경우가 많았다. 허나 21년 3월부로 테스트케이스를 변화했기 때문에 해당 방법으로는 효율성 부분에서 0점을 맞을 수 밖에 없다. 그래서 좀 찾아보니까 엄청난 효율성의 코드 발견(사실 위의 코드를 보면 시간 단축시킬 방법을 더 찾으려고 메소드화 했다가 써먹지도 안했다.) 

정렬을 해줌으로써 앞뒤로 한번씩 비교했던 것을 제거하고 indexOf를 마치 startsWith 처럼 써주는 방법이다. 그럼 여기서 사용한 개선점을 반영해서 위 코드를 간편화 시킬 수 있을까?

 

가능했다. 이렇게 간소화 해주니 효율성 테스트를 간단하게 통과 

2번째 문제로 배운점은 

• indexOf 를 startsWith 처럼 사용할 수 있다.
• 한가지 배열안에서의 이중for문을 이용한 비교는 정렬+index값 조절 로 단순 for문화 시킬 수 있다.