Cooper's devlog

[문제 처음 접할 때]

간단히 문제를 설명하자면 성적순으로 이름을 정렬했을 때 범위 안에 들어가고 이름 길이가 같은 친구을 찾는 문제 입니다. 성적과 이름이 같다는 것으로 친구을 찾는 과정이 슬프지만 일단 문제를 한번 보겠습니다.

 문제 풀이 수가 많은 문제가 일반적인 문제라고 생각해서 해당 문제를 선정했습니다. 문제 풀이에 앞서 투포인터에 대해 한마디로 정의하자면 두 개의 포인터를 사용한 방법으로 필요한 범위만 연산하고자 하는 방법에서 고안되었습니다. 기본적인 투포인터 문제는 좌우 인덱스를 선언해서 범위를 선정하는 방법으로 접근했지만 해결하지 못했고 이름의 길이를 담은 Queue를 생성한 접근 방법으로 문제를 해결했습니다다.

[문제 접근 방법]

1. 이름 인덱스를 담는 Queue를 원소로 하는 배열을 생성한다.

 - 배열의 인덱스 = 이름 길이

 - Queue에는 '순위'를 추가해서 계산한다.

2. 순차적으로 학생들을 탐색한다.

     (1) 이름의 길이가 같은 인덱스의 Queue가 비어있다면 순위를 추가한다.

     (2) Queue의 원소를 탐색해서 친구가 불가능한 경우는 제외 시킨다.

     (3) Queue에 친구들만 남아있으므로 친구 수를 추가한다.

     (4) 탐색하고 있는 학생의 순위를 Queue에 추가한다.

[전체 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int numberOfStudent = Integer.parseInt(st.nextToken());
        int gapOfPoint = Integer.parseInt(st.nextToken());
        long freindsCount = 0;

        Queue<Integer>[] nameLenArr = new Queue[21];

        for (int i = 0; i <= 20; i++) {
            nameLenArr[i] = new LinkedList<>();
        }

        for (int nowIndex = 0; nowIndex < numberOfStudent; nowIndex++) {
            int nameLen = br.readLine().length();

            if (nameLenArr[nameLen].isEmpty()) {
                nameLenArr[nameLen].offer(nowIndex);
                continue;
            }

            while (nowIndex - nameLenArr[nameLen].peek() > gapOfPoint) {
                nameLenArr[nameLen].poll();
                if (nameLenArr[nameLen].isEmpty()) {
                    break;
                }
            }

            freindsCount += nameLenArr[nameLen].size();
            nameLenArr[nameLen].offer(nowIndex);
        }

        System.out.println(freindsCount);

        br.close();
    }
}

[코드 세부 설명]

numberOfStudent	:	전체 학생 수
gapOfPoint	:	범위
freindsCount	:	친구 수

먼저 변수들을 한번 확인하고 아래서 부터 로직을 시작하도록 하겠습니다.

1. 이름 인덱스를 담는 Queue를 원소로 하는 배열을 생성한다.

Queue<Integer>[]:	이름 길이에 따른 Queue 배열

먼저 학생의 이름 길이에 따른 Queue 배열을 생성합니다.

배열의 인덱스는 학생 이름 길이를 뜻하고, Queue에는 학생들의 순위를 추가합니다.

2. 순서대로 학생들을 탐색한다.

for (int nowIndex = 0; nowIndex < numberOfStudent; nowIndex++)

먼저 학생들을 순차적으로 탐색하기 위해 반복문을 사용합니다.

이 문제의 현재 인덱스(학생)이 얼마나 친구들이 있는지를 확인하고자 하기 때문에  이 점을 유의해서 로직을 보시면 좋을 것 같습니다. 

(1) 이름의 길이가 같은 인덱스의 Queue가 비어있다면 순위를 추가한다.

if (nameLenArr[nameLen].isEmpty()) {
  nameLenArr[nameLen].offer(nowIndex);
  continue;
}

(2) Queue의 원소를 탐색해서 친구가 불가능한 경우는 제외 시킨다.

while (nowIndex - nameLenArr[nameLen].peek() > gapOfPoint) {
  nameLenArr[nameLen].poll();
    if (nameLenArr[nameLen].isEmpty()) {
    	break;
  }
}

 현재 학생을 기준으로 Queue의 가장 앞에 있는 경우를 찾습니다. 여기서 Queue를 구현한 이유가 나오게 되는데,

가장 먼저 들어간 원소가 현재 순위와 가장 멀기 때문입니다.

만약 범위(gapOfPoint)에 벗어나면 앞에 있는 원소를 제거하게 되고

벗어난 경우는 계속해서 탐색해 Queue에 있는 값(순위)을 제거해 나가기 시작합니다.

(3) Queue에 친구들만 남아있으므로 친구 수를 추가한다.

freindsCount += nameLenArr[nameLen].size();

예외처리가 완료가 되면 남아있는 Queue 원소들은 친구들이 됩니다.

그러므로 해당 인덱스(학생)의 친구들을 freindsCount 원소에 추가해 주도록 합니다.

(4) 탐색하고 있는 학생의 순위를 Queue에 추가한다.

nameLenArr[nameLen].offer(nowIndex);

친구 탐색이 완료 후, 다음 인덱스들이 친구들을 찾기 위해서 Queue에 해당 현재 인덱스를 추가해주도록 합니다.

[결과]

시간 복잡도는 O(N^2)을 띄고 있지만 조건에 따른 while문 처리기 때문에 효율적으로 계산되는 것을 확인할 수 있습니다! 이 문제 방식이 확실한 방법은 모르겠지만 twoPointer로 접근하는 방법을 찾으면 다시 업로드하도록 하겠습니다.

감사합니다ㅎㅎ