99클럽 코테 스터디 16일차 TIL (챌린저): [백준][Java] 2179 비슷한 단어 - 골드4

 

문제 보기

https://www.acmicpc.net/problem/2179

 

 

풀이

HashMap을 사용해 문제를 풀었다.

입력 순서대로 단어와 인덱스를 넣었다.

이 때 단어의 길이-1을 해가며 접두사들을 넣었다.

우선순위가 높은 값(최대한 비슷한 단어)부터 넣기 위해서인데 이유는 아래에 나온다.

 

for (int i = 0; i < N; i++) {
  String line = br.readLine();
  arr[i] = line;
  for (int j = line.length(); j > 0; j--) {
    String key = line.substring(0, j);
    if(key.length() < length) break;
    if(map.containsKey(key)) {
      if(key.length() == length && map.get(key) > s) break;
      if(key.length() == length && map.get(key) == s && i > t) break;
      s = map.get(key);
      t = i;
      length = key.length();
      break;
    }
    map.put(key, i);
  }
}

이게 로직을 수행하는 부분이다.

length가 이미 비슷한 단어로 뽑인 접두사의 길이보다 짧다면 그 다음은 볼 필요 없기 때문에 반복문을 빠져나온다.

그렇기 위해서는 긴 접두사부터 확인하여야 한다.

 

그리고 현재 단어의 접두사가 map에 이미 있는지 확인한다.

없으면 map에 추가한다.

있을 경우 설명에 나와있는 비교 로직을 수행한다.

• 접두사의 길이가 최대인 경우가 여러 개일 때에는 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 한다.
• 즉, 답으로 S라는 문자열과 T라는 문자열을 출력한다고 했을 때, 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고,
• 그런 경우도 여러 개 있을 때에는 그 중에서 T가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력한다.

  if(key.length() == length && map.get(key) > s) break;
  if(key.length() == length && map.get(key) == s && i > t) break;

그 코드가 바로 이 부분이다.

접두사의 길이가 같지만 s가 입력된 순서보다 뒤일 경우 break

접두사의 길이도 같고 s도 동일하지만 t가 입력된 순서보다 뒤일 경우 break

 

이 로직을 통과했을 경우만 s, t, length의 값을 갱신한다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;

public class Main {
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    HashMap<String, Integer> map = new HashMap<>();
    int s = 0;
    int t = 1;
    int length = 0;
    String[] arr = new String[N];
    for (int i = 0; i < N; i++) {
      String line = br.readLine();
      arr[i] = line;
      for (int j = line.length(); j > 0; j--) {
        String key = line.substring(0, j);
        if(key.length() < length) break;
        if(map.containsKey(key)) {
          if(key.length() == length && map.get(key) > s) break;
          if(key.length() == length && map.get(key) == s && i > t) break;
          s = map.get(key);
          t = i;
          length = key.length();
          break;
        }
        map.put(key, i);
      }
    }
    bw.write(arr[s] + "\n" + arr[t]);
    bw.flush();
    bw.close();
  }

}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/2179.%E2%80%85%EB%B9%84%EC%8A%B7%ED%95%9C%E2%80%85%EB%8B%A8%EC%96%B4

CodingTest_AutoSave/백준/Gold/2179. 비슷한 단어 at main · MetroDefro/CodingTest_AutoSave