BOJ_1411 : 비슷한 단어

👉 문제링크

1411번: 비슷한 단어

---

---

 

🔸 문제 분석 🔸

• n개의 문자열에서 서로 비슷한 쌍의 수를 출력한다.
  • 비슷하다는 의미는 문자열의 문자가 같은 방식으로만 변환 된 상태이다.
  • 다른 두 문자가 하나의 문자로 중복되어 변환되지 못한다.
• 시간복잡도를 계산해보자
  • n개의 문자열이 갖을 수 있는 모든 쌍을 계산하므로 선택정렬과 같다. O(n^2)
  • 그 안에서 문자열을 하나씩 검사해야한다. O(m)
  • 따라서 시간 복잡도는 O(n^2 * m)
    • 계산하면 100*100*50 == 500,000(50만) 이므로, 시간적으로는 여유있다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int n = Integer.parseInt(br.readLine());
        String arr[] = new String[n];

        for (int i = 0; i < n; i++)
            arr[i] = br.readLine();

        int answer = 0;
        for (int i = 0; i < n-1; i++){
            for (int j = i+1; j < n; j++){
                int chr[] = new int[27];
                int rev[] = new int[27];
                boolean flag = true;
                for (int k = 0; k < arr[i].length(); k++) {
                    int idx = arr[i].charAt(k) - 'a' + 1;
                    int temp = arr[j].charAt(k) - 'a' + 1;
                    if (chr[idx] == 0 && rev[temp] == 0) {
                        chr[idx] = temp;
                        rev[temp] = idx;
                    }
                    else if (chr[idx] != temp || rev[temp] != idx){
                        flag = false;
                        break;
                    }
                }
                if (flag) answer++;
            }
        }
        System.out.println(answer);
    }
}

🔸 코드 해석 🔸

• n개의 문자열을 배열 arr에 저장한다.
• n개의 문자열을 순회하며 쌍을 검사한다.
  • chr[ ] : 문자 하나를 인덱스로 변환(a == 1)해서, 변환했을때 어떤 문자인지 가리킨다.
  • rev[ ] : chr[ ]의 값이 rev[ ]의 인덱스이다. 한 문자를 여러 문자가 가리킬 수 없게 한다.
  • idx 는 기준 문자열 중 한 문자의 인덱스, temp는 비교할 문자열 중 한 문자의 인덱스
    • chr[idx] == 0이면 아직 안나온 문자이고, rev[temp] == 0 이면 다른 문자가 가리키고 있는 값도 아니다.
      • 서로 가리키게 값을 넣는다.
    • 0이 아닌 경우가 있으면, 오류이거나 변환 값이 중복이므로 비슷한 문자가 아니다.
  • 비슷한 문자의 수를 센다.
• 비슷한 문자의 수를 출력한다.

---

🔸 end 🔸

• chr[ ]와 rev[ ]를 나누지 않고, 하나의 배열에서 서로 가리키가 만들어서 논리적 오류가 생겨 풀이가 오래걸렸다.
• 예전에 못풀었던 문제를 다시 푸는데 어려운 건 아닌데도 생각보다 헷깔리는 부분이 많았다.