[D+79] 알고리즘문제 3 - 4번

 

 

D+79

-  알고리즘문제 3 - 4번 -

(Toy Problem 3 - 4)

 

---

 

 

# 03

두개의 배열을 입력받아 sample이 base의 부분집합인지를 구별하는 문제였는데

기본적인 문제들은 다 완성했지만 아쉽게도 Advanced한 문제는 통과하지 않았다.

 

사실 Advanced한 문제로 테스트가 아예 돌아가지 않아서 콘솔창에서 테스트를 돌려보았다 ㅎㅎㅎ

 

시간 복잡도를 개선해서 문제를 작성하는 것이었는데 생각보다 쉽지 않았다.

 

래퍼런스코드를 봤는데도 이해하는데 쉽지 않아서 인터넷에 검색을 통해 

내가 이해할 수 있는 코드를 참고로 작성해 보았다.

 

확인해 보니 나는 index를 변수로 따로 주면서 계산하지 않았는데

저렇게 하지 않으면 테스트가 돌아가지 않는 다는걸 알았다.

 

아무래도 시간 복잡도 개선을 위해 꼭 거쳐야 하는 과정인 것 같다.

 

 

# 04

버블 정렬을 구현하는 방식으로  단순히 버블 정렬만 구현하는 것이 아니라

더이상 정렬이 일어나지 않을때에는 끝까지 돌리는 것이 아니라 중간에 리턴해 버리는 코드를 구현하는 것이었다.

 

버블 정렬은 서로 인접한 (n번째, n+1번째) 요소를 검사해서 정렬하는 알고리즘으로

n번째가 n+1번째 보다 큰 값일 경우 서로의 위치를 바꾸는 방식으로 구현하면 된다.

 

이때 정렬이 더이상 일어나지 않을 경우 중간에 멈추는 방법은

카운트 변수를 따로 지정해 줌으로써 반복문에서 if문이 먹히지 않아 count가 0을 유지할 경우

바로 리턴해 버리면 된다.

 

이 개념은 Advanced한 개념이었기에 코드를 이해하는데에는 어렵지 않았지만

바로 코드에 적용시키는 것은 생각 보다 어려웠던 문제였던 것 같다.