[백준] 3078 좋은 친구 - Java

 

 

 

처음에 풀다가 틀린 코드 먼저 소개하겠다.

 

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

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 N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        LinkedList<String> q = new LinkedList<>();

        for(int i=0; i<N; i++){
          String str = br.readLine();

          q.add(str);
        }


        ArrayList<String> student;

        long cnt = 0;

        while(true){

          if(q.isEmpty()){
            break;
          }

          String candidate = q.pollFirst();
          student = new ArrayList<>();

          if(K > q.size()){
            K = q.size();
          }

          for(int i=0; i<K; i++){
            
            String temp = q.pollFirst();

            if(temp.length() == candidate.length()){
              cnt++;
              
            }

            student.add(temp);
          }

          for(int i=student.size()-1; i>=0; i--){
            q.addFirst(student.remove(i));
          }
          
          
        }// end of while 

        System.out.println(cnt);
    
        
   
    }
}

 

 

예제는 잘 나오는데.. 메모리 초과가 나온다.

왜그러지는 아직도 잘 모르겠다.. 리스트에 원소가 엄청나게 담기는 경우를 처리하지 못하는 것 같다.

 

 

큐 배열을 사용해 문제를 다시 풀었다.

 

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

public class Main01 {

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

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());

    long ans = 0;

    Queue[] q = new Queue[21];

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

    for (int i = 0; i < N; i++) {
      int len = br.readLine().length();

      if (q[len].isEmpty()) { // 문자열의 길이로 접근
        q[len].offer(i);
      } else {
        while (i - (int)q[len].peek() > K) { // 좋은 친구의 쌍을 찾기
          q[len].poll();
          if (q[len].isEmpty()) {
            break;
          }
        } // end of while

        ans = ans + q[len].size();
        q[len].offer(i);
      }

    }

    System.out.println(ans);

  }
}