[백준 1411] 비슷한 단어 (JAVA)

🔰 문제



💡 접근방식


원본 알파벳이 하게 바뀔 경우, 이를 HashMap을 이용해서 쌍으로 묶어준다.

단어 A와 단어 B의 같은자리 문자를 비교

1. A의 단어가 이미 HashMap에 값이 있을 경우(이미 숌하게 처리됨) 
	-> B의 단어가 숌한 단어가 맞는지 확인
2. A의 단어가 HashMap에 값이 없을 경우 
	-> A의 단어를 숌하게 바꾸기 위해 B의 단어가 이미 A의 다른 알파벳의 숌 단어인지 확인. 
       아직 사용된 적 없으면 HashMap에 추가

HashMap 사용법이 익숙하지 못 해서 어려웠던 문제이다.

HashMap 사용법

HashMap<String, String> map = new HashMap<>();

//값 추가
map.put("key1","value1"); 
map.put("key2", "value2");

//값 삭제 by key
map.remove(key2);

//key 값을 통해 value 얻기
String value = map.get("key1"); //value1 반환

//HashMap 전체 탐색 
Iterator<String> keys = map.keySet().iterator();
while(keys.hasNext()){
	String key = keys.next();
    System.out.println("("+key+", "+map.get(key)+")");
}

🕑소요시간

30분

풀이

💬 투포인터 버전

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

public class Main_1411 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String[] words = new String[N]; //N개의 단어
		
		for(int i=0;i<N;i++)
			words[i] = br.readLine();
		
		int cnt = 0; //비슷한 단어 쌍 (정답)
		
		for(int i=0;i<N;i++) {		//단어 A
			for(int j=i+1;j<N;j++) {		//단어 B
				boolean flag = true;
				HashMap<Character,Character> map = new HashMap<>(); //숌스럽게 바꾼 문자 저장
				for(int k=0;k<words[j].length();k++) {	//단어 A와 단어 B의 문자열 탐색
					char origin = words[i].charAt(k); //단어 A의 원본 문자열
					char compare = words[j].charAt(k); //숌스럽게 바꾼 단어 B의 문자열
					if(map.containsKey(origin)) { //원본 문자열이 이미 있을 경우(숌하게 바꾼 적 O)
						if(map.get(origin)!=compare) { //숌하지 않을 경우
							flag=false;
							break;
						}
					}
					else { //단어 A의 원본 문자열의 숌스럽게 바꾼 것이 없는 경우
						Iterator<Character> keys = map.keySet().iterator();
						while(keys.hasNext()) {
							char key = keys.next();
							if(map.get(key)==compare) { //이미 다른 알파벳의 대체 알파벳일 경우
								flag=false;
								break;
							}
						}
						if(flag)
							map.put(origin, compare);
					}
				}
				if(flag)
					cnt++;
			}
		}
		System.out.println(cnt);
		
	}
}


참고

좋은 웹페이지 즐겨찾기