[코드트리/NOVICE MID] k번째로 신기한 문자열 (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());
        String T = st.nextToken();
 
        String[] arr = new String[N];
        for(int i = 0 ; i < N ; i++) {
            arr[i] = br.readLine();
        }
        Arrays.sort(arr);
 
 
        String answer = "";
        int idx = 0;
 
        for(String s : arr) {
            if(s.startsWith(T)) {    // 문자열 T로 시작하는 단어들 中
                if(idx + 1 == K) { // K번째 원소라면 출력
                    System.out.println(s);
                    return;
                }
 
                idx += 1; // K번째 원소가 아니라면, 인덱스 + 1
            }
        }      
    }
}

 

 

🧩  해결 아이디어

• 정렬

- String형 배열에 문자열을 입력받고, 오름차순 정렬한다.

- int형 변수 idx를 설정하고, 문자열 T로 시작하는 단어인 경우, 이 idx에 값을 1씩 더한다.

- idx가 0에서 시작하게 했으므로, idx + 1이 K 값과 같을 때, 정답을 출력하고 반복문을 탈출한다.

 

 

 

---

🔺 다른 풀이들

- T로 시작하는 문자열 배열을 생성하고, 여기에 값을 넣어 해당 배열의 K번째 값을 출력하도록 하셨다.

(시간 복잡도 : O(NT + L N log N))

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static final int MAX_N = 100;
    
    public static int n, k;
    public static String t;
    public static int cnt;
    
    public static String[] str = new String[MAX_N];
    public static String[] words = new String[MAX_N];
    
    // a가 b로 시작하는지 확인하는 메소드
    public static boolean startsWith(String a, String b) {
        if((int) a.length() < (int) b.length())	return false;
        
        // a와 b가 완벽히 동일한지 확인
        for(int i = 0; i < (int) b.length(); i++) {
            if(a.charAt(i) != b.charAt(i))
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        t = sc.next();
        for(int i = 0; i < n; i++) {
            str[i] = sc.next();
            
            // 문자열 t로 시작하는 경우인지 확인하고, 그 경우에만 목록에 넣음
            if(startsWith(str[i], t))
                words[cnt++] = str[i];
        }
        
        Arrays.sort(words, 0, cnt);
        System.out.print(words[k - 1]);
    }
}

 

---

💬 느낀 점

다른 문제도 잘 풀장...

 

1회독	2회독	3회독	4회독	5회독
V