BOJ3052 - 서로 다른 나머지의 개수

 간단한 문제이나,

 은근 자주 쓰이는 생각의 방법을 담고 있는 문제라

 기록할 가치가 있어 적는다.

 

 단순하게 생각하면

 나머지들을 구하고, 서로 다른 값이 있는 것을 비교하는 알고리즘을 짤 수 있다.

 이 경우 이중 for문이 사용되고, 하나의 값마다 전체 리스트에 중복값이 있는지 비교하게 되므로

 시간복잡도는 O(n^2) 이 된다.

 

 여기서 

 

 이런 식으로

 값을 받아올때 42로 나눈 나머지를 저장하고,

 나머지의 종류를 세어주는 것으로 시간복잡도를 낮출 수 있다.

 

 이러한 방법처럼 내가 원하는 데이터로 변환해서 다루는 것이 유용한 경우들이 있다.