[BOJ 3078] 좋은 친구

문제

3078번: 좋은 친구

 

[좋은 친구]
상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다.
상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아.
??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 있는지 나와. 요즘 애들은 친구를 사귀기 전에 먼저 그 친구의 반 등수를 살펴봐. 말콤은 이 연구를 하기 위해서 6년동안 초등학교에서 선생님으로 위장 했었지. 하지만, 6년이라는 시간을 초등학교에서 보냈지만, 그 사람은 결국 결론을 얻지 못했어.
상근: 근데?
??: 내 말 아직 안끝났어. 말콤이 어느 날 자신이 초등학생이 되어 학교를 활보하는 꿈을 꾸었어. 근데 잠을 깨고 나니 내가 꿈을 꾸고 초등학생이 된건지, 아니면 초등학생이 꿈을 꾸고 지금의 내가 되어있는지를 모르겠는거야. 그래서 말콤은 상식적인 사고 방식에 큰 의문을 가졌지. 그 때 말콤은 깨달았던거야. 초등학교 친구는 부질없구나. 그제서야 알게된거야. 모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아니라는거.
상근: 아? 근데 K는 어떻게 구해?
??: K는 문제에서 주어지지. 근데, 더 중요한 사실이 있어. 친구와 좋은 친구의 차이야. 말콤이 친구와 성적을 쓰고 2년 뒤에 낸 책인 좋은 친구라는 책에는 좋은 친구는 이름의 길이가 같아야 된다는 말이 나와.
상근: 아! 그럼 난 오늘 집에 가서 우리 반에 좋은 친구가 몇 쌍이나 있는지 구해봐야 겠어!
상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다.

문제의 이해

등수로 정렬된 이름 리스트와 등수 차이 K가 주어집니다. '좋은 친구'의 조건을 만족하기 위해선 등수 차이가 K보다 작거나 같은 친구들 중 이름 길이가 같아야 합니다.

서현과 좋은 친구가 될 수 있는 사람들은 서현보다 +- 4등 앞선 사람들이다.

단순히 코딩하기

처음 봤을 때는 골드 3 개꿀~ 하면서 x등부터 x+k등까지 이름의 길이를 x+(k+1)등 사람의 길이와 비교를 n번 하면 되는게 아니야? 라고 단순하게 생각했습니다. O(nk)의 복잡도로 풀면 단순하게 풀릴 것이라 생각했습니다.

G5 문제인데 실버 수준의 발상...

당연히 어림도 없이 시간 초과가 납니다. N은 0부터 30만까지, K는 1부터 N까지입니다. K=N일 경우, 시간복잡도는 O(n^2)이 됩니다.

 

5년 전 junie님 이 자리를 빌어 감사의 말씀을 드립니다.

모든 사람을 탐색하여 최소한 O(n)만큼은 순회를 하여야 올바른 답을 구할 수 있다고 생각했기 때문에, 비교에 필요한 시간복잡도를 최소한 O(logk)까지는 줄여야 가망이 있을 것이라 생각했습니다. 

#슬라이딩윈도우

blog.fakecoding.com/archives/algorithm-slidingwindow/를 읽으며 문제풀이에 대한 큰 힌트를 얻었습니다.

슬라이딩 윈도우/큐 두 가지로 풀 수 있습니다.

슬라이딩 윈도우의 구간 합 구하기 예제를 보면서, queue/슬라이딩 윈도우 안에 있는 비교대상과 일일이 다 비교하는 대신에 슬라이딩 윈도우/큐 안의 사람들의 길이정보를 큐에 enque()/윈도우를 한 칸 이동할 때 마다 업데이트를 O(1)에 해놓으면, 단일 원소의 좋은 친구 쌍 구하기는 O(1)에 가능합니다.

 

좋은 친구를 중복으로 카운트 하지 않기 위해, 어떤 친구보다 더 나은 등수의 친구들과만 비교를 하여 짝을 짓기로 했습니다. 만약 어떤 친구보다 등수가 낮은 친구들까지 비교를 하게 된다면, 중복으로 카운트가 될 것이기 때문입니다.

예를 들자면 k=3이고, 철수가 1등, 영희가 3등, 짱구가 5등일 때, 영희 차례가 되었을 때 철수/짱구와 좋은 친구 쌍을 카운트하게 되면, 철수는 영희와 좋은 친구라고 이미 카운트 했을 것이고, 짱구 역시 영희와 좋은 친구 조건을 충족하기 때문에 카운트를 하게 되는 것이죠.

 

비교는 O(1) 시간에 가능하다!

 길이 array 업데이트는 새로운 element가 enque() 혹은 윈도우가 움직일 때 O(1) 수행한다.

이 풀이가 가능한 이유는 이름 길이의 범위가 2~20이기 때문에, length가 20 정도인 어레이를 만드는건 공간복잡도에 큰 영향을 주지 않는데, 그로 얻어지는 비교 시 시간 복잡도 이득은 매우 큽니다. 만약 이름 길이의 제한이 20이 아니라 더 크다면, array 대신에 해쉬맵을 사용하는 것이 더 좋지 않을까 생각합니다.