같은 애너그램인 문자열 묶기

ino5·2021년 9월 8일
0
package algorithm.tokroom;

import java.util.*;


/*
 * 문자열 배열이 주어졌을 때, 같은 애너그램마다 하나의 문자열 배열로 엮은 2차원 배열로 출력
 * 
 * strs = {"eat", "repaid", "paired" ,"tea", "bat"} 일 때
 * 답은 = {{"eat", "tea"}, {repaid, paired}, {bat}}
 * 
 */

public class Anagram {
	public static void main(String[] args) {
		// 주어진 문자열 배열
		String[] strs = {"eat", "repaid", "paired" ,"tea", "bat"};
		// 정답
		String[][] answer = solution(strs);
		
		// 정답 출력
		for (String[] strLine : answer) {
			System.out.print("{");
			int index = 0;
			for (String str : strLine) {
				System.out.print(str);
				if (++index != strLine.length) {
					System.out.print(", ");
				}
			}
			System.out.println("}");
		}
	}
	
	static String[][] solution(String[] strs) {
		// 정답인 2차원 배열의 row length
		int LengthOfRow = 0;
		// strs[i]가 정답 배열에 들어갔으면 isChecked[i] = true
		boolean[] isChecked = new boolean[strs.length]; 
		// key: 정답 배열의 row index, value: 같은 애너그램끼리 모은 list
		Map<Integer, List<String>> map = new HashMap<Integer, List<String>>(); 
		
		// strs에서 문자열 하나하나 확인
		for (int i = 0; i < strs.length; i++) {
			// 정답 배열에 이미 들어가 있는 문자열은 패스
			if (isChecked[i]) {
				continue;
			}
			// 같은 애너그램인 문자열들을 모을 리스트
			List<String> list = new ArrayList<String>();
			// 기준이 되는 문자열(strs[i]) 넣어주기
			list.add(strs[i]);
			isChecked[i] = true;
			char[] arr = strs[i].toCharArray();
			// 같은 애너그램인지 비교하기 위해 먼저 sort
			Arrays.sort(arr);
			
			// strs의 다른 문자열들을 하나씩 같은 애너그램인지 비교해주기
			for (int j = i + 1; j < strs.length; j++) {
				if (isChecked[j]) {
					continue;
				}
				char[] arr2 = strs[j].toCharArray();
				Arrays.sort(arr2);
				// 기준이 되는 문자열과 같은 애너그램일 경우  list에 넣어주기
				if (Arrays.toString(arr).equals(Arrays.toString(arr2))) {
					list.add(strs[j]);
					isChecked[j] = true;
				}
			}
			
			// key: 정답 배열의 row index, value: 같은 애너그램끼리 모은 list
			map.put(LengthOfRow, list);
			++LengthOfRow;
		}
		
		// 정답(map)을 2차원 배열로 변환하기
		String[][] res = new String[LengthOfRow][];
		for (int i = 0; i < LengthOfRow; i++) {
			res[i] = new String[map.get(i).size()];
			for (int j = 0; j < map.get(i).size(); j++) {
				res[i][j] = map.get(i).get(j);
			}
		}
		return res;
	}
}

profile
지금은 네이버 블로그만 해요... https://blog.naver.com/chero77

0개의 댓글