문제
환경 운동가인 동현이는 길거리에 휴지통을 볼 때마다 한숨이 나온다고 한다. 쓰레기들이 플라스틱, 종이 할 것 없이 분리수거 되지 않고 버려져 있기 때문이다. 동현이는 본인부터 솔선수범해서 재활용하는 습관을 들이기로 했다.
양의 정수쌍 ( A , B )에서 다음과 같은 조건을 만족할 때, A를 B로 재활용한다고 하며, ( A , B )를 재활용 순서쌍이라고 한다.
- 조건 1: A<B이다. - 조건 2: 두 정수는 자리수가 같다. - 조건 3: A의 맨 앞자리 수 몇개를 순서를 바꾸지 않고 뒤로 옮겼을 때, B가 된다.
예를 들면 다음과 같다. (1234,3412)는 앞의 12를 순서를 바꾸지 않고 뒤로 보내서 3412를 만들 수 있으므로 1234를 재활용하면 3412가 된다고 할 수 있다.
그러나 (1234,3421)은 12를 뒤로 보낼 때 순서를 바꾸어야 하므로 재활용할 수 없는 경우이다.
또한 순서쌍을 이루는 두 수가 같은 수들로 이루어진 경우 같은 경우로 본다.
너저분하게 버려져 있는 n개의 양의 정수 중 만들 수 있는 재활용 순서쌍의 수를 세는 프로그램을 작성해서 동현이를 행복하게 해주어라.
입력
첫 줄에 n(1 <= n <= 100,000 , n은 정수)이 주어진다. n은 재활용 순서쌍을 찾을 숫자들의 개수다.
둘째 줄에 n개의 정수들이 입력된다.
이 정수들은 1이상 1,000,000이하의 정수로 같은 수들이 포함될 수 있다.
전체 데이터의 40%는 (1 <= n <= 10,000)임을 보장한다.
출력
재활용 정수쌍의 수를 출력하라.
예제
6
10 1 13 31 23 32
2
출처
Women's CodeSprint 5
로그인해야 코드를 작성할 수 있어요.