백준 2825 자바 - 수업시간에 교수님 몰래 교실을 나간 상근이 (BOJ 2825 JAVA)

https://www.acmicpc.net/problem/2825

 

  알고리즘 분류랑 솔브닥 티어 표시 끄고, 문제 검색 옵션에서 실~플로 랜덤으로 나오게 하고 문제푸니 쫄깃하게 재밌다. 이건 처음엔 실버상위~골드하위 정도일줄 알았는데, 생각할수록 최소 골드 중간쯤은 될꺼란 생각이 들었다..

 

  처음엔 단순하게 1이 포함된 숫자 리스트, 2가 포함된 숫자 리스트, ... 이렇게 분류해서 union-find나 각 쌍을 hashset에 넣으면서 nCr로 계산하면 될 것 같았다. 하지만 아무리 생각해봐도 시간복잡도를 O(N^2)에서 줄일수가 없었다. 이쯤에서 실~골하위는 아닐꺼라 일단 생각이 들었다 ㅋㅋ N이 100만개이므로 O(N^2) 풀이는 아예 불가하고, 못해도 O(NlogN) 정도 수준으로 생각해내야 한다. 결론적으로 좀 푸는데 오래걸렸다. 이하 해당 풀이다.

 

  입력이 1123, 1333332, 2222231, 12222, 211111, 3 이렇게 들어왔다고 생각해보자. 모두 다른 숫자이긴 하지만, 사실 포함된 숫자의 구성이 같다면 이 문제에서는 동일한 숫자라고 생각해도 문제가 없다.

즉, [1123, 1333332, 2222231] / [12222, 211111] / [3] 이렇게는 동일한 숫자라 생각할 수 있다!

그럼 이걸 압축시킬 수 있는데, 포함된 숫자의 구성만으로 보자면 처음 그룹은 1,2,3 숫자 포함 / 두번째는 1,2 포함 / 세번째는 3 포함 이므로 '1,2,3포함 : 3개 / 1,2포함 : 2개 / 3포함 : 1개'

이렇게 볼 수 있게 된다.

 

  이렇게 그룹을 지어 생각해보면 뭐가 달라지냐면, 최대 0~9까지 총 10개의 숫자에 대해 해당 숫자 중 어떤게 포함됬는지에 따라 그룹을 지으면 되므로, 비트마스킹으로 10 bit짜리 숫자로 변환할 수 있다. 그럼 최대 10^18짜리 숫자 100만개에서 최대 1<<10 (=1024)개의 그룹 사이의 연산으로 압축되버린다.

 

  그럼 우선 위 예시를 이어서, '1,2,3포함[A그룹] : 3개 / 1,2포함[B그룹] : 2개 / 3포함[C그룹] : 1개' 에 대해 각 그룹끼리 쌍의 갯수를 구해보자. 각 그룹 중 공통된 숫자를 포함하는 경우 해당 그룹에 포함된 갯수끼리 모두 쌍이 지어질 것임을 알 수 있다. 예를들어 A그룹과 B그룹은 1이나 2가 공통되므로 해당 그룹에 포함된 숫자들 끼리도 쌍이 가능하다. 이 경우, 단순히 해당 그룹의 숫자를 곱해주면 모든 쌍이므로 3x2 = 6개이다. 다음으로 A와 C그룹을 보면 3이 공통되므로 마찬가지로 3x1개의 쌍이 추가된다. B와 C그룹은 겹치는게 없으므로 0개이다. 그럼 각 그룹 사이에서 만들 수 있는 쌍의 갯수는 총 3x2 + 3x1 + 0 이다.

 

  다음으로 각 그룹 내에서 자기들끼리의 쌍의 갯수를 구해보자. 이 경우 당연히 nC2의 Combination으로 구할 수 있다. (해당 그룹 내의 모든 수에 대해 2개씩 쌍을 지으므로) 그럼 A그룹은 3C2 = 3개, B그룹은 1개, C그룹은 0개 이다.

최종적으로 입력 1123, 1333332, 2222231, 12222, 211111, 3 에 대한 답은 위에서 계산한 모든걸 더하면 된다. 그럼 13개가 된다.

 

  그럼 시간복잡도는 우선 최대 100만개를 입력받으면서 비트마스킹으로 1<<10 이하의 그룹번호로 변경한다( O(N) ). 그리고 최대 1024개의 그룹에 대해 다른 모든 그룹과의 공통 숫자가 있는지 확인하는 과정을 거쳐야 하므로 ( O(1024^2) ) 최종적으로 O(N + 1024^2)이 된다. 대강 200만번 정도로 예상되므로 별 문제 없이 시간내에 연산할 수 있을꺼라 예상할 수 있다.

 

  이제 위의 내용을 구현하면 된다.

8~14 line에서 groupNum변수가 그룹번호가 된다. 예를들어 46이라는 숫자는 1<<4와 1<<6 지점에 비트마스킹을 하므로, '..001010000'(2진수) 와 같이 변경될 것이다. 6444444라는 숫자도 역시 마찬가지로 '..001010000'가 된다. 이런식이다. 18~19 line이 모든 그룹끼리 해당 그룹의 모든 숫자끼리의 쌍의 갯수를 구하는 부분이다. 20~21line이 nC2 처리하는 부분이다.

 

  참고로 

nCr 공식은 위와 같고, r이 2로 고정되므로 nC2 = n * (n-1) / 2 이다.

 

https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02800/BOJ_2825.java