Map - [Java]

노력하는 배짱이·2021년 4월 2일
0

Map

개념

Map<Key, Value> 형태 -> value를 찾는데 시간복잡도는 O(1)
ex) Map<Integer, String> map = HashMap<>();
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");

주로 사용하는 형태

  1. Map + String(getOrDefault())
  2. Map + Array
  3. Map + Math.max
  4. Map + Set
  5. Map + Map
  6. Set + Set

출력하기

  1. map.keySet()
for (Integer key : map.keySet()) {
			System.out.println("key : " + key + " value : " + map.get(key));
		}
  1. map.entrySet()
for (Map.Entry<Integer, String> element : map.entrySet()) {
			System.out.println("key : " + element.getKey() + " value : " + element.getValue());
		}
  1. map.keySet().iterator()
Iterator<Integer> keys = map.keySet().iterator();
		while (keys.hasNext()) {
			Integer key = keys.next();
			System.out.println("key : " + key + " value : " + map.get(key));
		}

문제

1. Map + getOrDefault()

주어진 문자열에서 반복되지 않는 첫 번째 문자를 찾아서 Index를 return
존재하지 않으면 -1를 반환

Input : String s = "inflearninlove"
Output : 2

풀이

  1. 문자열의 각 문자의 갯수를 파악 (2이상이면 반복되는 문자임)
  2. 각 문자에 갯수를 Map에 저장함
  3. 문자열의 길이만큼 for문을 돌려 첫번째로 1이 나오는 문자의 인덱스를 출력

소스

public class Q1 {

	public static void main(String[] args) {
		String s = "inflearninlove";

		System.out.println(solve(s));
	}

	public static int solve(String s) {

		if (s == null || s.length() == 0) {
			return -1;
		}

		Map<Character, Integer> map = new HashMap<Character, Integer>();

		for (char ch : s.toCharArray()) {
			// 1
			map.put(ch, map.getOrDefault(ch, 0) + 1);

			// 2
//			if (!map.containsKey(ch)) {
//				map.put(ch, 1);
//			} else {
//				map.put(ch, map.get(ch) + 1);
//			}
		}

		for (int i = 0; i < s.length(); i++) {
			if (map.get(s.charAt(i)) == 1) {
				return i;
			}
		}

		return -1;
	}

}

2. Map + Array

자연수가 들어가 있는 배열이 주어졌을 때 가장 빈도수가 높은 k개의 요소를반환

Input : int[] nums = {1,1,2,2,2,3,5,5,5,5} , int k = 2
Output : [5, 2]

풀이

  1. map.getOrDefault()를 이용하여 각 수의 갯수를 저장한다.
  2. 빈도수에 따른 List<> 배열을 선언하여 각 빈도수의 맞는 수(key)를 넣어준다.
  3. k만큼 빈도수를 갖는 값을 뽑아준다.

빈도수 List) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (nums의 길이가 10)
value List) null, 1, 2, 3, 4, null, null, null, null, null, null
key List) null, 3, 1, 2, 5, null, null, null, null, null, null

소스

public class Q2 {

	public static void main(String[] args) {
		int[] nums = { 1, 1, 2, 2, 2, 2, 3, 5, 5, 5, 5 };
		int k = 2;

		System.out.println(solve(nums, k));
	}

	public static List<Integer> solve(int[] nums, int k) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		List<Integer>[] list = new List[nums.length + 1];
		List<Integer> result = new ArrayList<>();

		for (int num : nums) {
			map.put(num, map.getOrDefault(num, 0) + 1);
		}

		for (int key : map.keySet()) {
			int topFreq = map.get(key);
			if (list[topFreq] == null) {
				list[topFreq] = new ArrayList<Integer>();
			}
			list[topFreq].add(key);

		}

		for (int lastIndex = list.length - 1; lastIndex >= 0; lastIndex--) {
			if (list[lastIndex] != null) {
				// System.out.println(list[lastIndex]);
				for (int i = 0; i < list[lastIndex].size() && result.size() < k; i++) {
					result.add(list[lastIndex].get(i));
				}
			}
		}

		return result;
	}

}

참고

인프런 강의 : 코딩테스트 전 꼭 알아야 할 개념과 문제(with 자바) - 푸샵맨 코딩스터디

0개의 댓글