본문 바로가기
Problem Solving/카카오 블라인드 기출

2021 - 메뉴 리뉴얼

by Libi 2021. 8. 9.
반응형

https://programmers.co.kr/learn/courses/30/lessons/72411

 

코딩테스트 연습 - 메뉴 리뉴얼

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서

programmers.co.kr

[ 문제풀이 ]

주어진 orders들로 만들 수 있는 길이가 2 이상인 코스들을 조합한 후 course의 길이마다 최대 주문 횟수를 가지는 코스들을 추출하면 되는 문제이다.

"AC" 코스나 "CA" 코스는 똑같은 코스이기 때문에 조합을 통해 가능한 모든 코스를 추출해주면 된다.

import java.util.*;

class Solution {
	Map<String, Integer> hm;
	List<Character> list;

	class Node {
		String str;
		int count;

		public Node (String str, int idx) {
			this.str = str;
			this.count = idx;
		}
	}

	public String[] solution(String[] orders, int[] course) {
		hm = new HashMap<>();
		list = new ArrayList<>();

		boolean[] Course = new boolean[11]; //길이가 i인 코스가 존재하는지
		int[] maxOrder = new int[11]; //길이가 i인 코스의 최대 주문 횟수

		for (int c : course) {
			Course[c] = true;
		}

		for (String order : orders) {
			for (int i = 0; i < order.length(); ++i) {
				list.add(order.charAt(i));
			}

			//코스의 조합을 오름차순으로 생성하기 위해
			Collections.sort(list);

			//길이가 2이상인 코스만 생성
			for (int i = 0; i < order.length() - 1; ++i) {
				dfs(i + 1, Character.toString(list.get(i)));
			}

			list.clear();
		}

		Iterator<String> it = hm.keySet().iterator();
		List<Node> nodeList = new ArrayList<>();

		//생성한 모든 코스의 조합을 돌면서
		while (it.hasNext()) {
			String str = it.next();

			//주문 횟수가 2이상인 코스만 추출
			if (hm.get(str) >= 2) {
				nodeList.add(new Node(str, hm.get(str)));

				//현재 코스의 길이가 존재하면 최대 주문 횟수 갱신
				if (Course[str.length()]) {
					maxOrder[str.length()] = Math.max(maxOrder[str.length()], hm.get(str));
				}
			}
		}

		List<String> answerList = new ArrayList<>();

		//주문 횟수가 최대 주문 횟수인 코스 추출
		for (Node node : nodeList) {
			if (maxOrder[node.str.length()] == node.count) {
				answerList.add(node.str);
			}
		}

		//오름차순으로 정렬
		Collections.sort(answerList);

		return answerList.toArray(new String[answerList.size()]);
	}

	public void dfs(int idx, String str) {
		//코스의 길이가 2이상일때 주문 횟수 갱신
		if (str.length() >= 2) {
			if (hm.containsKey(str)) {
				hm.replace(str, hm.get(str) + 1);
			} else {
				hm.put(str, 1);
			}
		}

		if (idx == list.size()) return;

		for (int i = idx; i < list.size(); ++i) {
			dfs(i + 1, str + Character.toString(list.get(i)));
		}
	}
}

 

 

반응형

'Problem Solving > 카카오 블라인드 기출' 카테고리의 다른 글

2021 - 합승 택시 요금  (0) 2021.08.09
2021 - 순위 검색  (0) 2021.08.09
2021 - 신규 아이디 추천  (0) 2021.08.09
2020 - 블록 이동하기  (0) 2021.08.08
2020 - 외벽 점검  (0) 2021.08.08

댓글