HashMap과 TreeSet을 활용하여 문제를 해결해본다.
모든 코드는 깃허브 (링크)의 테스트 코드로 정리해두었다.
학급 회장
학급 회장을 뽑는데 후보로 기호 A, B, C, D, E 후보가 등록을 했습니다.
투표용지에는 반 학생들이 자기가 선택한 후보의 기호(알파벳)가 쓰여져 있으며 선생님은 그 기호를 발표하고 있습니다.
선생님의 발표가 끝난 후 어떤 기호의 후보가 학급 회장이 되었는지 출력하는 프로그램을 작성하세요.
반드시 한 명의 학급회장이 선출되도록 투표결과가 나왔다고 가정합니다.
- 입력설명
첫 줄에는 반 학생수 N(5<=N<=50)이 주어집니다.
두 번째 줄에 N개의 투표용지에 쓰여져 있던 각 후보의 기호가 선생님이 발표한 순서대로 문자열로 입력됩니다. - 출력설명
학급 회장으로 선택된 기호를 출력합니다. - 입력예제 1
15
BACBACCACCBDEDE - 출력예제 1
C
public class ClassPrinciple {
public char solution1(String input) {
Map<Character, Integer> scoreMap = new HashMap<>();
char[] chars = input.toCharArray();
for (char c : chars) {
scoreMap.put(c, scoreMap.getOrDefault(c, 0) + 1);
}
char maxUser = ' ';
int maxScore = Integer.MIN_VALUE;
for (char key : scoreMap.keySet()) {
if (maxScore < scoreMap.get(key)) {
maxScore = scoreMap.get(key);
maxUser = key;
}
}
return maxUser;
}
@Test
@DisplayName("학급 회장")
public void main() {
String input = "BACBACCACCBDEDE";
char expectedAnswer = 'C';
char answer1 = solution1(input);
assertEquals(expectedAnswer, answer1);
}
}아나그램
Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 합니다.
예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재 배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다.
길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요.
아나그램 판별시 대소문자가 구분됩니다.
- 입력설명
첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다. 단어의 길이는 100을 넘지 않습니다. - 출력설명
두 단어가 아나그램이면 “YES"를 출력하고, 아니면 ”NO"를 출력합니다. - 입력예제 1
AbaAeCe
baeeACA - 출력예제 1
YES - 입력예제 2
abaCC
Caaab - 출력예제 2
NO
public class Anagram {
// Arrays.sort를 활용한 방법
public String solution1(String input1, String input2) {
char[] chars1 = input1.toCharArray();
char[] chars2 = input2.toCharArray();
Arrays.sort(chars1);
Arrays.sort(chars2);
return Arrays.equals(chars1, chars2) ? "YES" : "NO";
}
// HashMap을 활용한 방법
public String solution2(String input1, String input2) {
Map<Character, Integer> charMap = new HashMap<>();
for (int i = 0; i < input1.length(); i++) {
charMap.put(input1.charAt(i), charMap.getOrDefault(input1.charAt(i), 0) + 1);
}
for (int i = 0; i < input2.length(); i++) {
if (!charMap.containsKey(input2.charAt(i)) || charMap.get(input2.charAt(i)) == 0) {
return "NO";
} else {
charMap.put(input2.charAt(i), charMap.get(input2.charAt(i)) - 1);
}
}
for (int count : charMap.values()) {
if (count > 0) {
return "NO";
}
}
return "YES";
}
@Test
@DisplayName("아나그램")
public void main() {
String expectedAnswer1 = "YES";
String answer1 = solution1("AbaAeCe", "baeeACA");
String answer2 = solution1("AbaAeCe", "baeeACA");
assertEquals(expectedAnswer1, answer1);
assertEquals(expectedAnswer1, answer2);
String expectedAnswer2 = "NO";
String answer3 = solution2("abaCC", "Caaab");
String answer4 = solution2("abaCC", "Caaab");
assertEquals(expectedAnswer2, answer3);
assertEquals(expectedAnswer2, answer4);
}
}매출액의 종류
현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 매출액의 종류를 각 구간별로 구하라고 했습니다.
만약 N=7이고 7일 간의 매출기록이 아래와 같고, 이때 K=4이면
20 12 20 10 23 17 10
각 연속 4일간의 구간의 매출종류는
첫 번째 구간은 [20, 12, 20, 10]는 매출액의 종류가 20, 12, 10으로 3이다.
두 번째 구간은 [12, 20, 10, 23]는 매출액의 종류가 4이다.
세 번째 구간은 [20, 10, 23, 17]는 매출액의 종류가 4이다.
네 번째 구간은 [10, 23, 17, 10]는 매출액의 종류가 3이다.
N일간의 매출기록과 연속구간의 길이 K가 주어지면 첫 번째 구간부터 각 구간별 매출액의 종류를 출력하는 프로그램을 작성하세요.
- 입력설명
첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다. - 출력설명
첫 줄에 각 구간의 매출액 종류를 순서대로 출력합니다. - 입력예제 1
74
20 12 20 10 23 17 10 - 출력예제 1
3 4 4 3
public class TypeOfSales {
public Integer[] solution1(int days, int section, int[] sales) {
List<Integer> answer = new ArrayList<>();
Map<Integer, Integer> mapOfSales = new HashMap<>();
for (int i = 0; i < section - 1; i++) {
mapOfSales.put(sales[i], mapOfSales.getOrDefault(sales[i], 0) + 1);
}
int left = 0;
for (int right = section - 1; right < days; right++) {
mapOfSales.put(sales[right], mapOfSales.getOrDefault(sales[right], 0) + 1);
answer.add(mapOfSales.size());
mapOfSales.put(sales[left], mapOfSales.getOrDefault(sales[left], 0) - 1);
if (mapOfSales.get(sales[left]) == 0) {
mapOfSales.remove(sales[left]);
}
left++;
}
return answer.toArray(new Integer[0]);
}
@Test
@DisplayName("매출액의 종류")
public void main() {
int[] sales = {20, 12, 20, 10, 23, 17, 10};
Integer[] expectedAnswer = {3, 4, 4, 3};
Integer[] answer2 = solution1(7, 4, sales);
assertArrayEquals(expectedAnswer, answer2);
}
}모든 아나그램 찾기
S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하세요.
아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.
- 입력설명
첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다.
S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다. - 출력설명
S단어에 T문자열과 아나그램이 되는 부분문자열의 개수를 출력합니다. - 입력예제 1
bacaAacba
abc - 출력예제 1
3
출력설명: {bac}, {acb}, {cba} 3개의 부분문자열이 "abc"문자열과 아나그램입니다. - 입력예제 2
bacaAacbaa
abca - 출력예제 2
3
public class FindAnagram {
public int solution1(String sentence, String target) {
int answer = 0;
Map<Character, Integer> sentenceMap = new HashMap<>();
Map<Character, Integer> targetMap = new HashMap<>();
for (char c : target.toCharArray()) {
targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
}
for (int i = 0; i < target.length() - 1; i++) {
sentenceMap.put(sentence.charAt(i), sentenceMap.getOrDefault(sentence.charAt(i), 0) + 1);
}
int left = 0;
for (int right = target.length() - 1; right < sentence.length(); right++) {
sentenceMap.put(sentence.charAt(right), sentenceMap.getOrDefault(sentence.charAt(right), 0) + 1);
if (sentenceMap.equals(targetMap)) {
answer++;
}
sentenceMap.put(sentence.charAt(left), sentenceMap.getOrDefault(sentence.charAt(left), 0) - 1);
if (sentenceMap.get(sentence.charAt(left)) == 0) {
sentenceMap.remove(sentence.charAt(left));
}
left++;
}
return answer;
}
@Test
@DisplayName("모든 아나그램 찾기")
public void main() {
int expectedAnswer1 = 3;
int answer1 = solution1("bacaAacba", "abc");
assertEquals(expectedAnswer1, answer1);
int expectedAnswer2 = 3;
int answer2 = solution1("bacaAacbaa", "abca");
assertEquals(expectedAnswer2, answer2);
}
}K번째 큰 수
현수는 1부터 100사이의 자연수가 적힌 N장의 카드를 가지고 있습니다. 같은 숫자의 카드가 여러장 있을 수 있습니다.
현수는 이 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록하려고 합니다. 3장을 뽑을 수 있는 모든 경우를 기록합니다.
기록한 값 중 K번째로 큰 수를 출력하는 프로그램을 작성하세요.
만약 큰 수부터 만들어진 수가 25 25 23 23 22 20 19......이고 K값이 3이라면 K번째 큰 값은 22입니다.
- 입력설명
첫 줄에 자연수 N(3<=N<=100)과 K(1<=K<=50) 입력되고, 그 다음 줄에 N개의 카드값이 입력된다. - 출력설명
첫 줄에 K번째 수를 출력합니다. K번째 수가 존재하지 않으면 -1를 출력합니다. - 입력예제 1
10 3
13 15 34 23 45 65 33 11 26 42 - 출력예제 1
143
public class KthBigNumber {
public int solution1(int length, int count, int[] numbers) {
int answer = -1;
Set<Integer> setOfSum = new TreeSet<>(Collections.reverseOrder());
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
for (int k = j + 1; k < length; k++) {
setOfSum.add(numbers[i] + numbers[j] + numbers[k]);
}
}
}
int tmpCount = 0;
for (int sum : setOfSum) {
tmpCount++;
if (tmpCount == count) {
return sum;
}
}
return answer;
}
@Test
@DisplayName("K번째 큰 수")
public void main() {
int expectedAnswer = 143;
int answer1 = solution1(10, 3, new int[]{13, 15, 34, 23, 45, 65, 33, 11, 26, 42});
assertEquals(expectedAnswer, answer1);
}
}'Algorithm' 카테고리의 다른 글
| [Algorithm] Queue (0) | 2022.02.23 |
|---|---|
| [Algorithm] Stack (0) | 2022.02.23 |
| [Algorithm] Sliding window (0) | 2022.02.21 |
| [Algorithm] Two Pointers (0) | 2022.02.21 |
| [Algorithm] 배열 다루기 (0) | 2022.02.20 |
