[Baekjoon 13915] Hot Air Ballooning - JAVA

[Silver III] Hot Air Ballooning - 13915

문제 링크

성능 요약

메모리: 16680 KB, 시간: 164 ms

분류

비트마스킹, 자료 구조, 해시를 사용한 집합과 맵, 정렬, 트리를 사용한 집합과 맵

문제 설명

Dave is the director of the Summer school of hot air ballooning. Being a responsible director, he keeps a list of flights of each trainee in the school. After each flight, Dave appends a note to the lists of flights of each trainee participating in that particular flight. The note is very simple, it just indicates the type number of the balloon. In this way, each trainee flight history is characterized by a list of numbers.

At the end of the season, Dave wants to categorize the trainees according to their experience with different brands of balloons.

Two trainees belong to the same category if they have flown the same types of balloons. It does not matter how many times they have flown any particular balloon type, what does matter is the set of the balloon types they have flown and that has to be the same.

There are exactly nine types of balloons in Dave’s school, and no trainee has flown more than nine times in a balloon, so Dave expresses each trainee list as an integer consisting of digits 1, 2, . . . , 9 and smaller than one billion. He thinks that this representation will help him to process the lists programmatically by a computer.

For example, the trainees characterized by integers 234423 and 342 belong to the same category, while the trainees characterized by integers 118821 and 1189821 belong to different categories.

Help Dave to calculate how many different categories of trainees attended the school this season.

입력

There are more test cases. Each case starts with a line containing one integer N (1 ≤ N ≤ 1 000) representing the number of trainees. Next, there are N lines, each line contains one integer representing the list of flights of one particular trainee.

출력

For each test case, print a single line with one integer C specifying the number of different trainee categories in the school.

문제 풀이

문제에서는 여러 수강생들이 탑승한 풍선의 유형을 나타내는 숫자 리스트가 주어졌을 때, 서로 다른 풍선 탑승 이력을 가진 수강생의 범주 수를 구하는 문제다.

문제에서는 각 수강생의 풍선 탑승 이력을 정수로 표현하고, 이를 기반으로 범주를 구분하라고 하고 있다.

예를 들어, 수강생 A가 123과 312 풍선을 탔고, 수강생 B가 231과 321 풍선을 탔다면, 두 수강생은 같은 풍선 탑승 이력을 가진 범주에 속한다.

입력에는 수강생 수를 나타내는 하나의 정수 N이 주어지고, 각 줄마다 특정 수강생의 비행 목록을 나타내는 하나의 정수가 주어진다.

해당 문제는 비트 마스킹을 이용해 풀 수 있다.

• 비트 마스킹이란 = 정수를 2진수로 표현하는 것으로 생각하면 된다.

비트 마스킹 알고리즘 이해를 돕기 위해 아래 예시를 들었다.

예시 입력:

4 123 312 112233 1332 

각 수강생의 풍선 탑승 이력을 비트 마스킹으로 표현하면 다음과 같다:

• 수강생 1: 123 -> 000000111 (2진수)
• 수강생 2: 312 -> 000000111 (2진수)
• 수강생 3: 112233 -> 000000111 (2진수)
• 수강생 4: 1332 -> 000000111 (2진수)

이제 비트 마스킹된 이력을 해시맵으로 카운팅하면 다음과 같다:

해시맵을 사용하는 이유는 중복된 값들을 제거하기 위해서다.
중복된값을 제거하는 이유는 문제에서 동일한 열기구를 탄 값을 제거하라고 나와있기 때문이다.

중복된 값 제거하는 방법은 필자의 블로그에 정리되어 있다.

https://lold2424.tistory.com/50

[Java] 배열에 중복된 값 제거하는법 (Set)

배열에서 중복값을 제거하는 방법은 크게 2가지(Set, Stream)가 있다. 1. Set Java에서 Set은 중복을 허용하지 않는 컬렉션 인터페이스다. Set은 순서가 없는 요소들의 집합으로, 원소들이 추가된 순서나 삽입된 위치에 따라 인덱스를 갖지 않는다. Java에서는 Set 인터페이스를 구현한 여러 클래스들이 있다. 그 중 가장 일반적인 클래스로는 (HashSet, TreeSet, LinkedHashSet)들이 있다. 한번 순서대로 알아보자. 1-1 HashSet 해싱(Hashing) 알고리즘을 사용하여 요소들을 저장하는 Set입니다. HashSet은 중복을 허용하지 않으며, 순서가 보장되지 않는다. 코드 import java.util.Arrays; import java.util.HashSet;..

lold2424.tistory.com

해시맵: 000000111 -> 4명 

동일한 2진수의 값에 4명이 중복되고, 해시맵의 크기는 1이므로 서로 다른 범주의 수는 1이 된다.

위 예시를 보면 알겠지만 동일한 숫자만 있는지만 확인하면 되는 문제다.

만약 동일한 숫자를 가진다면 몇개가 반복되든 확인할 필요가 없다.

비트마스킹을 사용하지 않아도 풀 수 있을것 같긴한데 처음 보는 알고리즘이기 때문에 한번 사용해보았다.

이대로 구현하면 문제는 간단하게 해결할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

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

		while (true) {
			String input = br.readLine();
			if (input == null || input.equals("")) {
				break;
			}

			int N = Integer.parseInt(input.trim());
			Set<Integer> uniqueSets = new HashSet<>();

			for (int i = 0; i < N; i++) {
				String elements = br.readLine().trim();
				int len = elements.length();
				int setFlag = 0;

				for (int j = 0; j < len; j++) {
					int elementValue = elements.charAt(j) - '1';
					setFlag = setFlag | (1 << elementValue);
				}

				uniqueSets.add(setFlag);
			}

			System.out.println(uniqueSets.size());
		}
	}
}

코드 풀이

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

		while (true) {
			String input = br.readLine();
			if (input == null || input.equals("")) {
				break;
			}

			int N = Integer.parseInt(input.trim());
			Set<Integer> uniqueSets = new HashSet<>();

• input: 입력을 받아올 변수, 입력이 없거나 빈 문자열일 경우 루프를 종료한다.
• N: 수강생 수를 저장할 변수 Integer.parseInt를 사용하여 파싱한다.
• uniqueSets: 각 수강생의 풍선 탑승 이력을 비트 마스킹으로 변환하여 저장할 HashSet
Set은 중복된 값을 허용하지 않는 자료구조다.

			for (int i = 0; i < N; i++) {
				String elements = br.readLine().trim();
				int len = elements.length();
				int setFlag = 0;

				for (int j = 0; j < len; j++) {
					int elementValue = elements.charAt(j) - '1';
					setFlag = setFlag | (1 << elementValue);
				}

				uniqueSets.add(setFlag);
			}

• String elements: 각 수강생의 풍선 탑승 이력을 나타내는 문자열
• int len: 각 수강생의 풍선 탑승 이력의 길이를 저장한다.
• int setFlag: 비트 마스킹을 통해 풍선 탑승 이력을 나타내는 정수
• 1 << elementValue: 해당 풍선 유형을 나타내는 비트를 설정한다.
• setFlag에 각 풍선 탑승 이력을 나타내는 비트를 | 연산을 통해 추가한다.
• uniqueSets.add(setFlag)를 사용해 해당 수강생의 풍선 탑승 이력을 uniqueSets에 추가한다.
  중복된 값은 Set에 의해 자동으로 제거된다.

			System.out.println(uniqueSets.size());
		}
	}
}

• uniqueSets의 크기를 출력한다.