목차
1. 회문 만들기
2. 문자열 뒤집기
3. 조건에 맞게 재 정렬하기
4. 특정 단어 추출하기
5. 애너그램
6. 가장 긴 회문 찾기
7. 문자열 개수에 따른 조합 구하기
8. 문자열 개수에 따른 순열 구하기
9. KMP 알고리즘
10. 접미사
1. 회문 만들기
문제를 요약하자면 다음과 같다.
회문인 경우 0을 출력/ 유사 회문(한개의 문자만 제거했을 때 회문인 경우)인 경우 1을 출력/ 아무것도 해당되지 않는 경우 2를 출력
그래서 생각한 방법은, 일반적으로 회문을 체크할 때 주어진 문자열의 길이의 반만큼 순회를 돌며 i번째와 length - i -1번째의 문자가 같은지 확인하고 다르다면 chance(유사 회문의 기회)가 존재할 경우 재귀적으로 다시 solution을 실행시키며 한 글자를 없앴을 때 유사회문이 되는지를 확인하는 방법을 생각했다.
처음엔 재귀적을 생각하지 못하고, 회문이 아닌 경우 chance가 존재할 때, 아래 check 메서드를 i+1, j와 i, j-1에 대해서만 진행하고 일치하는 경우에는 계속 진행, 둘 다 일치하지 않는 경우에는 회문이 아님! 으로 판단하도록 구현했었다.
그랬더니, baaba 와 같은 경우에 마지막 a를 지우면 baab로 회문이 되지만, 처음껄 먼저 지우게 되면 aaba가 되어 회문이 아님!으로 판별되어버렸다. 그래서 결국 재귀적으로 solution을 호출하는 방식으로 변경하였다.
코드
import java.io.*;
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
final String string = br.readLine();
System.out.println(solution(string, 0, string.length() - 1, true));
}
}
private static int solution(String string, int i, int j, boolean chance) {
while (i < j) {
char c1 = string.charAt(i);
char c2 = string.charAt(j);
if (c1 == c2) {
i += 1;
j -= 1;
continue;
}
if (chance) {
if (solution(string, i + 1, j, false) == 1) {
return 1;
}
return solution(string, i, j-1, false);
}
return 2;
}
if (chance) return 0;
return 1;
}
}
2. 문자열 뒤집기
첫도전..
입력 > baekjoon online judge
출력 > oonkjeba onnlie ujged참 요상한 결과를 얻었다.
두번째 도전
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringJoiner;
public class Main {
/*
1. 단어 하나만 존재하는 경우 abc -> cba
2. 단어 두개 이상 띄어쓰기로 구분된 경우 abc abc -> cba cba
3. 단어에 <>가 앞에 포함된 경우 -> <hi> abc -> <hi> cba
4. 단어에 <>가 뒤에 포함된 경우 -> abc <hi> -> cba <hi>
5. 단어에 <>가 중간에 포함된 경우 -> abc <hi> abc -> cba <hi> cba
6. <>안에 띄어쓰기가 포함된 경우 -> <ab cd> hi -> <ab cd> ih
7. 단어에 <>가 띄어쓰기 없이 붙은 경우 -> <a>bc<a> -> <a>cb<a>
8. 단어에 <>가 끝나지 않고 띄어쓰기가 따로인 경우 -> <ab cd>ef gh<ij kl> -> <ab cd>fe hg<ij kl>
*/
public static void main(String[] args) throws IOException {
final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
final String inputString = br.readLine();
if (!inputString.contains("<")) {
System.out.println(reverseString(inputString));
return;
}
StringJoiner answer = new StringJoiner(" ");
// 띄어쓰기 기준으로 우선 분리
final String[] strings = inputString.split(" ");
for (String string: strings) {
// <> 다 포함된 경우
if (string.contains("<") && string.contains(">")) {
StringBuilder sb = new StringBuilder();
while (!string.isEmpty()) {
int startIdx = string.indexOf("<");
int endIdx = string.indexOf(">");
if (endIdx != -1 && endIdx < startIdx) {
sb.append(string, 0, endIdx + 1);
string = string.substring(endIdx + 1);
}
if (string.charAt(0) != '<') {
if (startIdx > 0) sb.append(reverseString(string.substring(0, startIdx)));
else {
sb.append(reverseString(string));
break;
}
string = string.substring(startIdx);
}
startIdx = string.indexOf("<");
endIdx = string.indexOf(">");
if (endIdx == -1) {
sb.append(string);
break;
}
sb.append(string, startIdx, endIdx + 1);
string = string.substring(endIdx + 1);
}
answer.add(sb.toString());
continue;
}
// <만 포함된 경우
if (string.contains("<") && !string.contains(">")) {
String[] split = string.split("<");
if (split.length > 1) answer.add(String.join("<", reverseString(split[0]), split[1]));
else answer.add(string);
continue;
}
// >만 포함된 경우
if (string.contains(">") && !string.contains("<")) {
String[] split = string.split(">");
if (split.length > 1) answer.add(String.join(">", split[0], reverseString(split[1])));
else answer.add(string);
continue;
}
// 포함되지 않은 경우
answer.add(reverseString(string));
}
System.out.println(answer);
}
private static String reverseString(String string) {
StringBuilder answer = new StringBuilder();
for (int i = string.length() - 1; i >= 0; i--) {
answer.append(string.charAt(i));
}
return answer.toString();
}
}그 결과는??
결국 다른 분들의 풀이를 봤다. 😵
나는 풀이할 때 모든 케이스에 대해서 일일히 대응을 해줬었다. 일단 빈 문자열 기준으로 분리하고, 그 안에서 <가 하나 있는 경우, <>둘 다 있는 경우, >만 있는 경우, 문자열만 있는 경우, 그 안에서도 index에 따라 경우 처리........
하지만 내가 가져온 분의 풀이는 다음과 같았다.
- stack에 char 하나씩 저장한다.
- "<"를 만나면 stack에 여태껏 모아둔 것들을 위에서부터 출력한다. (역순) 그리고 flag를 true로 열어둔다.
- ">"를 만나면 flag를 false로 바꾼다.
- flag가 true이면 stack에 넣지 않고 바로 출력한다.
- 아니라면 스택에 넣는다.
참으로 간단한 풀이인 것 같다. 후.. 일단 역순을 스택의 LIFO로 생각한 게 굉장히 신기했다. 문제를 좀 더 여러개 풀면서 많은 경험을 해 보면 나아지겠지? ^ㅠ^
코드
import java.util.Scanner;
import java.util.Stack;
public class ac_단어뒤집기 {
static void print(Stack st) {
while (!st.empty()) {
System.out.print(st.peek());
st.pop();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Stack st = new Stack();
String s = sc.nextLine();
boolean check = false;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '<') {
print(st); // <를 만나면 여태껏 저장해둔 문자열 거꾸로 출력
check = true;
System.out.print(s.charAt(i));
} else if (s.charAt(i) == '>') {
check = false;
System.out.print(s.charAt(i));
} else if (check) {
System.out.print(s.charAt(i));
} else {
if (s.charAt(i) == ' ') {
print(st);
System.out.print(s.charAt(i));
} else {
st.push(s.charAt(i));
}
}
}
print(st);
}
}
// 출처: https://1-7171771.tistory.com/27
3. 조건에 맞게 재 정렬하기
data = ['1 A', '1 B', '6 A', '2 D', '4 B']를 뒤의 문자 순으로 정렬하기
StringPair라는 클래스를 하나 만들어서, Sort 기준을 뒤의 문자가 되도록 했다. 그냥 StringPair과 같은 객체를 만들지 않고 빈 문자열 기준으로 분리한 배열을 이용해서 Sort해도 동일할 것이라는 생각이 든다.
코드
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class ac_조건정렬 {
public static void main(String[] args) {
String[] datum = {"1 A", "1 B", "6 A", "2 D", "4 B"};
final List<StringPair> stringPairs = Stream.of(datum)
.map(data -> {
final String[] s = data.split(" ");
return new StringPair(s[0], s[1]);
}).sorted((o1, o2) -> {
if (o1.s2.compareTo(o2.s2) == 0) {
return o1.s1.compareTo(o2.s1);
}
return o1.s2.compareTo(o2.s2);
}).collect(Collectors.toList());
stringPairs.forEach(
s -> System.out.println(s.concat())
);
}
public static class StringPair {
String s1;
String s2;
public StringPair(String s1, String s2) {
this.s1 = s1;
this.s2 = s2;
}
public String concat() {
return s1 + " " + s2;
}
}
}
4. 특정 단어 추출하기
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit"
완전 단순하게 생각해서 빈 문자열 기준으로 분리하고, Map에 key를 단어로, value를 갯수로 하여 집어넣고 가장 큰 값을 구했다.
더 좋은 방법이 없을까 궁금하다..
코드
import java.util.HashMap;
import java.util.Map.Entry;
public class ac_특정단어추출하기 {
public static void main(String[] args) {
String line = "Bob hit a ball, the hit BALL flew far after it was hit";
// 1. 빈 문자열을 기준으로 분리한다.
String[] words = line.split(" ");
// 2. HashMap을 하나 선언한다.
HashMap<String, Integer> map = new HashMap<>();
for (String word : words) {
if (map.containsKey(word)) {
map.put(word, map.get(word) + 1);
} else {
map.put(word, 1);
}
}
// 3. value가 가장 큰 값을 뽑는다.
int max = -1;
String key = "";
for (Entry<String, Integer> entry : map.entrySet()) {
if (entry.getValue() > max) {
max = entry.getValue();
key = entry.getKey();
}
}
System.out.println(key);
}
}
5. 애너그램 (문자를 재배열하여 다른 뜻을 가진 단어로 바꾸기)
내가 생각해낸 방법은, 다음과 같다.
1. target 문자열의 길이만큼 0으로 초기화된 int 배열을 만든다.
2. source 문자열을 순회하며 target 문자열에 해당 char이 존재하는지 확인한다.
3. 존재한다면 int 배열의 해당 자리에 1을 표시한다.
4. 존재하는데, 이미 해당 자리가 1이라면 중복이므로 다른 위치에 해당 char이 있는지 확인한다.
5. 반복
한줄 요약하자면 target 문자열에, source에서 온 char 문자열을 찾았으면 체크하는 것과 같다!
초 획기적이라고 생각했다. 하지만 테스트케이스만 동작하는지 실패한다. ㅠ 테스트케이스는 어떻게하면 잘 만들 수 있을까?
실패 코드
import java.util.Scanner;
public class ac_애너그램 {
private static boolean solveAnagrams(String first, String second) {
if (first.length() != second.length()) {
return false;
}
int[] checkers = new int[first.length()];
for (int i = 0; i < first.length(); i++) {
final char ch = first.charAt(i);
int index = second.indexOf(ch);
if (checkers[index] == 1) {
final long count = second.chars()
.filter(c -> c == ch)
.count();
boolean flag = false;
for (int j = 0; j < count; j++) {
index = second.indexOf(ch, index + 1);
if (checkers[i] == 0) {
if (flag) continue;
checkers[i] = 1;
flag = true;
}
}
if (!flag) return false;
continue;
}
checkers[index] = 1;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int numTests = sc.nextInt();
for (int i = 0; i < numTests; i++) {
String first = sc.next().toLowerCase();
String second = sc.next().toLowerCase();
System.out.println(
first + " & " + second + " are " + (solveAnagrams(first, second) ? "anagrams."
: "NOT anagrams."));
}
}
}
그래서 다른 풀이들을 찾아봤는데, 진짜 내가 뭔가 위에서도 그렇고 매번 복잡하게 생각한다는 것을 깨달았다.
그냥 charArray로 바꾸고, 정렬해서 같은지만 비교하면 되는 것이었다 😂
코드
import java.util.Arrays;
import java.util.Objects;
import java.util.Scanner;
public class ac_애너그램 {
private static boolean solveAnagrams(String first, String second) {
if (first.length() != second.length()) {
return false;
}
final char[] source = first.toCharArray();
Arrays.sort(source);
final char[] target = second.toCharArray();
Arrays.sort(target);
return Arrays.equals(source, target);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int numTests = sc.nextInt();
for (int i = 0; i < numTests; i++) {
String first = sc.next().toLowerCase();
String second = sc.next().toLowerCase();
System.out.println(
first + " & " + second + " are " + (solveAnagrams(first, second) ? "anagrams."
: "NOT anagrams."));
}
}
}
6. 가장 긴 회문 찾기
https://programmers.co.kr/learn/courses/30/lessons/12904
7. 문자열을 count에 따라 조합 구하기
https://seongilman.tistory.com/385
8. 문자열을 count에 따라 순열 구하기
https://yunmap.tistory.com/entry/JAVA-%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%88%9C%EC%97%B4
9. KMP
https://www.acmicpc.net/problem/2902
10. 접미사
https://www.acmicpc.net/problem/11656