문자열을 다루는 알고리즘 문제를 해결해본다.
모든 코드는 깃허브 (링크)의 테스트 코드로 정리해두었다.
문자열 관련 알고리즘 문제는 Ascii 코드를 자주 활용해야 하므로 아래의 Ascii 코드를 참고한다.
문자 찾기
한 개의 문자열을 입력받고, 특정 문자를 입력받아 해당 특정문자가 입력받은 문자열에 몇 개 존재하는지 알아내는 프로그램을 작성하세요.
대소문자를 구분하지 않습니다.
문자열의 길이는 100을 넘지 않습니다.
- 입력설명
첫 줄에 문자열이 주어지고, 두 번째 줄에 문자가 주어진다. 문자열은 영어 알파벳으로만 구성되어 있습니다. - 출력설명
첫 줄에 해당 문자의 개수를 출력한다. - 입력예제 1
Computercooler c - 출력예제 1 2
public class FindCharacter {
// for 문을 활용한 풀이 방법
public int solution1(String characters, char targetChar) {
int answer = 0;
// 대소문자를 구분하지 않으므로 전부 소문자로 변경한다.
characters = characters.toLowerCase();
// 찾으려는 문자도 대문자가 입력될지 소문자가 입력될지 알 수 없으므로 소문자로 변경한다.
targetChar = Character.toLowerCase(targetChar);
for (char c : characters.toCharArray()) {
if (c == targetChar) {
answer++;
}
}
return answer;
}
// Stream을 활용한 풀이 방법
public int solution2(String characters, char targetChar) {
characters = characters.toLowerCase();
char finalTargetChar = Character.toLowerCase(targetChar);
return (int) CharBuffer.wrap(characters.toCharArray()).chars()
.filter(i -> i == finalTargetChar)
.count();
}
@Test
@DisplayName("문자 찾기")
public void main() {
int answer1 = solution1("Computercooler", 'c');
assertEquals(2, answer1);
int answer2 = solution2("Computercooler", 'c');
assertEquals(2, answer2);
}
}대소문자 변환
대문자와 소문자가 같이 존재하는 문자열을 입력받아 대문자는 소문자로 소문자는 대문자로 변환하여 출력하는 프로그램을 작성하세요.
- 입력설명
첫 줄에 문자열이 입력된다. 문자열의 길이는 100을 넘지 않습니다. 문자열은 영어 알파벳으로만 구성되어 있습니다. - 출력설명
첫 줄에 대문자는 소문자로, 소문자는 대문자로 변환된 문자열을 출력합니다. - 입력예제 1
StuDY - 출력예제 1
sTUdy
public class CaseChange {
// Character의 isLowerCase를 사용한 풀이
public String solution1(String input) {
StringBuilder answer = new StringBuilder();
for (char inputChar : input.toCharArray()) {
answer.append(
Character.isLowerCase(inputChar)
? Character.toUpperCase(inputChar)
: Character.toLowerCase(inputChar));
}
return answer.toString();
}
// ascii를 사용한 풀이, 대문자에 32를 더하면 소문자가 된다.
// A ~ Z = 65 ~ 90
// a ~ z = 97 ~ 122
public String solution2(String input) {
StringBuilder answer = new StringBuilder();
for (char inputChar : input.toCharArray()) {
if (inputChar >= 65 && inputChar <= 90) {
answer.append((char) (inputChar + 32));
} else if (inputChar >= 97 && inputChar <= 122) {
answer.append((char) (inputChar - 32));
}
}
return answer.toString();
}
@Test
@DisplayName("대소문자 변환")
public void main() {
String answer1 = solution1("StuDY");
assertEquals("sTUdy", answer1);
String answer2 = solution2("StuDY");
assertEquals("sTUdy", answer2);
}
}문장 속 단어
한 개의 문장이 주어지면 그 문장 속에서 가장 긴 단어를 출력하는 프로그램을 작성하세요. 문장속의 각 단어는 공백으로 구분됩니다.
- 입력설명
첫 줄에 길이가 100을 넘지 않는 한 개의 문장이 주어집니다. 문장은 영어 알파벳으로만 구성 되어 있습니다. - 출력설명
첫 줄에 가장 긴 단어를 출력한다. 가장 긴 단어가 여러개일 경우 문장속에가 가장 앞쪽에 위 치한 단어를 답으로 합니다. - 입력예제 1
it is time to study - 출력예제 1
study
public class WordInSentence {
public String solution1(String sentence) {
int maxLength = Integer.MIN_VALUE;
int maxLengthWordIndex = Integer.MIN_VALUE;
String[] words = sentence.split(" ");
for (int i = 0; i < words.length; i++) {
if (words[i].length() > maxLength) {
maxLength = words[i].length();
maxLengthWordIndex = i;
}
}
return words[maxLengthWordIndex];
}
// indexOf를 사용한 방법
public String solution2(String sentence) {
String answer = "";
int maxLength = Integer.MIN_VALUE;
int position;
while ((position = sentence.indexOf(" ")) != -1) {
String tmp = sentence.substring(0, position);
if (tmp.length() > maxLength) {
answer = tmp;
maxLength = tmp.length();
}
// 공백 부분까지 지워줘야 하므로 +1
sentence = sentence.substring(position + 1);
}
// while 조건에 의해 가장 마지막 문자는 while의 로직을 타지 않으므로 따로 처리
if (sentence.length() > maxLength) {
answer = sentence;
}
return answer;
}
@Test
@DisplayName("문장 속 단어")
public void main() {
String answer1 = solution1("it is time to study");
Assertions.assertEquals("study", answer1);
String answer2 = solution2("it is time to study");
Assertions.assertEquals("study", answer2);
}
}단어 뒤집기
N개의 단어가 주어지면 각 단어를 뒤집어 출력하는 프로그램을 작성하세요.
- 입력설명
첫 줄에 자연수 N(3<=N<=20)이 주어집니다.
두 번째 줄부터 N개의 단어가 각 줄에 하나씩 주어집니다. 단어는 영어 알파벳으로만 구성되 어 있습니다. - 출력설명
N개의 단어를 입력된 순서대로 한 줄에 하나씩 뒤집어서 출력합니다. - 입력예제 1
3
good
Time
Big - 출력예제 1
doog
emiT
giB
public class FlipWord {
// StringBuilder의 reverse() 함수를 사용하는 방법
public String[] solution1(String... words) {
List<String> answer = new ArrayList<>();
for (String word : words) {
answer.add(new StringBuilder(word).reverse().toString());
}
return answer.toArray(new String[0]);
}
// 직접 뒤집는 방식
public String[] solution2(String... words) {
List<String> answer = new ArrayList<>();
for (String word : words) {
char[] chars = word.toCharArray();
int left = 0;
int right = chars.length - 1;
while (left < right) {
char tmp = chars[left];
chars[left] = chars[right];
chars[right] = tmp;
left++;
right--;
}
answer.add(String.valueOf(chars));
}
return answer.toArray(new String[0]);
}
@Test
@DisplayName("단어 뒤집기")
public void main() {
String[] expectedAnswer = {"doog", "emiT", "giB"};
String[] answer1 = solution1("good", "Time", "Big");
assertArrayEquals(answer1, expectedAnswer);
String[] answer2 = solution2("good", "Time", "Big");
assertArrayEquals(answer2, expectedAnswer);
}
}특정 문자 뒤집기
영어 알파벳과 특수문자로 구성된 문자열이 주어지면 영어 알파벳만 뒤집고, 특수문자는 자기 자리에 그대로 있는 문자열을 만들어 출력하는 프로그램을 작성하세요.
- 입력설명
첫 줄에 길이가 100을 넘지 않는 문자열이 주어집니다. - 출력설명
첫 줄에 알파벳만 뒤집힌 문자열을 출력합니다. - 입력예제 1
a#b!GE*T@S - 출력예제 1
S#T!EG*b@a
public class FlipSpecificWord {
public String solution1(String word) {
char[] chars = word.toCharArray();
int left = 0;
int right = chars.length - 1;
while (left < right) {
if (Character.isAlphabetic(chars[left]) && Character.isAlphabetic(chars[right])) {
char tmp = chars[left];
chars[left] = chars[right];
chars[right] = tmp;
}
left++;
right--;
}
return String.valueOf(chars);
}
@Test
@DisplayName("특정 문자 뒤집기")
public void main() {
String answer1 = solution1("a#b!GE*T@S");
Assertions.assertEquals("S#T!EG*b@a", answer1);
}
}중복 문자 제거
소문자로 된 한개의 문자열이 입력되면 중복된 문자를 제거하고 출력하는 프로그램을 작성하세요.
제거된 문자열의 각 문자는 원래 문자열의 순서를 유지합니다.
- 입력설명
첫 줄에 문자열이 입력됩니다. 문자열의 길이는 100을 넘지 않는다. - 출력설명
첫 줄에 중복문자가 제거된 문자열을 출력합니다. - 입력예제 1
ksekkset - 출력예제 1
kset
public class RemoveDuplicatedWord {
public String solution1(String word) {
StringBuilder answer = new StringBuilder();
for (int i = 0; i < word.length(); i++) {
// word.indexOf("a")라고 가정하였을 때 word의 문자열 중 가장 앞의 a의 index를 return한다.
// 만약 i와 word.indexOf(word.charAt(i))가 일치한다면 해당 char는 word중 가장 첫번째 문자다.
// 만약 i와 word.indexOf(word.charAt(i))가 일치하지 않는다면 해당 char는 앞에서 이미 존재했던 char가 된다.
// log.info("{}, {}, {}", word.charAt(i), i, word.indexOf(word.charAt(i)));
if (i == word.indexOf(word.charAt(i))) {
answer.append(word.charAt(i));
}
}
return answer.toString();
}
@Test
@DisplayName("중복 문자 제거")
public void main() {
String answer1 = solution1("ksekkset");
Assertions.assertEquals("kset", answer1);
}
}회문 문자열
앞에서 읽을 때나 뒤에서 읽을 때나 같은 문자열을 회문 문자열이라고 합니다.
문자열이 입력되면 해당 문자열이 회문 문자열이면 "YES", 회문 문자열이 아니면 “NO"를 출력 하는 프로그램을 작성하세요.
단 회문을 검사할 때 대소문자를 구분하지 않습니다.
- 입력설명
첫 줄에 길이 100을 넘지 않는 공백이 없는 문자열이 주어집니다. - 출력설명
첫 번째 줄에 회문 문자열인지의 결과를 YES 또는 NO로 출력합니다. - 입력예제 1
gooG - 출력예제 1
YES
public class RoundSentence {
// StringBuilder의 reverse를 사용한 방법
public String solution1(String sentence) {
String lowerCaseSentence = sentence.toLowerCase();
StringBuilder answer = new StringBuilder(lowerCaseSentence);
return answer.reverse().toString().equals(lowerCaseSentence)
? "YES"
: "NO";
}
// 직접 문자열을 뒤집는 방법
public String solution2(String sentence) {
String lowerCaseSentence = sentence.toLowerCase();
char[] lowerCaseSentenceChars = lowerCaseSentence.toCharArray();
for (int i = 0; i < lowerCaseSentenceChars.length; i++) {
if (lowerCaseSentenceChars[i] != lowerCaseSentenceChars[lowerCaseSentenceChars.length -1 -i]) {
return "NO";
}
}
return "YES";
}
@Test
@DisplayName("회문 문자열")
public void main() {
String expectedAnswer = "YES";
String answer1 = solution1("gooG");
assertEquals(expectedAnswer, answer1);
String answer2 = solution2("gooG");
assertEquals(expectedAnswer, answer2);
}
}유효한 팰린드룸
앞에서 읽을 때나 뒤에서 읽을 때나 같은 문자열을 팰린드롬이라고 합니다.
문자열이 입력되면 해당 문자열이 팰린드롬이면 "YES", 아니면 “NO"를 출력하는 프로그램을 작성하세요.
단 회문을 검사할 때 알파벳만 가지고 회문을 검사하며, 대소문자를 구분하지 않습니다. 알파벳 이외의 문자들의 무시합니다.
- 입력설명
첫 줄에 길이 100을 넘지 않는 공백이 없는 문자열이 주어집니다. - 출력설명
첫 번째 줄에 팰린드롬인지의 결과를 YES 또는 NO로 출력합니다. - 입력예제 1
found7, time: study; Yduts; emit, 7Dnuof - 출력예제 1 YES
public class Palindrome {
// 정규식을 통한 ReplaceAll과 StringBuilder의 reverse를 사용하는 방법
public String solution1(String sentence) {
sentence = sentence.toLowerCase().replaceAll("[^a-z]", "");
StringBuilder reversedSentence = new StringBuilder(sentence).reverse();
return reversedSentence.toString().equals(sentence)
? "YES"
: "NO";
}
// 직접 문자열을 하나씩 비교하는 방법
public String solution2(String sentence) {
String lowerSentence = sentence.toLowerCase();
char[] chars = lowerSentence.toCharArray();
for (int i = 0; i < chars.length / 2; i++) {
char left = chars[i];
char right = chars[chars.length -i -1];
if (Character.isAlphabetic(left) && Character.isAlphabetic(right)) {
if (left != right) {
return "NO";
}
}
}
return "YES";
}
// ascii 코드를 활용하여 직접 문자열을 하나씩 비교하는 방법
public String solution3(String sentence) {
char[] chars = sentence.toLowerCase().toCharArray();
for (int i = 0; i < chars.length / 2; i++) {
char left = chars[i];
char right = chars[chars.length -1 -i];
if (left >= 97 && right >= 97 && left <= 122 && right <= 122) {
if (left != right) {
return "NO";
}
}
}
return "YES";
}
@Test
@DisplayName("유효한 팰린드롬")
public void main() {
String expectedAnswer = "YES";
String answer1 = solution1("found7, time: study; Yduts; emit, 7Dnuof");
assertEquals(expectedAnswer, answer1);
String answer2 = solution2("found7, time: study; Yduts; emit, 7Dnuof");
assertEquals(expectedAnswer, answer2);
String answer3 = solution3("found7, time: study; Yduts; emit, 7Dnuof");
assertEquals(expectedAnswer, answer3);
}
}숫자만 추출
문자와 숫자가 섞여있는 문자열이 주어지면 그 중 숫자만 추출하여 그 순서대로 자연수를 만 듭니다.
만약 “tge0a1h205er”에서 숫자만 추출하면 0, 1, 2, 0, 5이고 이것을 자연수를 만들면 1205 이 됩니다.
추출하여 만들어지는 자연수는 100,000,000을 넘지 않습니다.
- 입력설명
첫 줄에 숫자가 썩인 문자열이 주어집니다. 문자열의 길이는 100을 넘지 않습니다. - 출력설명
첫 줄에 자연수를 출력합니다. - 입력예제 1 g0en2T0s8eSoft
- 출력예제 1 208
public class ExtractNumber {
// ascii 코드를 활용하여 숫자만 추출하는 방법
public int solution1(String sentence) {
char[] chars = sentence.toCharArray();
StringBuilder answer = new StringBuilder();
for (char c : chars) {
if (c >= 48 && c <= 57) {
answer.append(c);
}
}
return Integer.parseInt(answer.toString());
}
// Character의 isDisit() 함수를 활용한 방법
public int solution2(String sentence) {
char[] chars = sentence.toCharArray();
StringBuilder answer = new StringBuilder();
for (char c : chars) {
if (Character.isDigit(c)) {
answer.append(c);
}
}
return Integer.parseInt(answer.toString());
}
@Test
@DisplayName("숫자만 추출")
public void main() {
int expectedAnswer = 208;
int answer1 = solution1("g0en2T0s8eSoft");
assertEquals(expectedAnswer, answer1);
int answer2 = solution2("g0en2T0s8eSoft");
assertEquals(expectedAnswer, answer2);
}
}가장 짧은 문자거리
한 개의 문자열 s와 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소거리를 출력하는 프로그램을 작성하세요.
- 입력설명
첫 번째 줄에 문자열 s와 문자 t가 주어진다. 문자열과 문자는 소문자로만 주어집니다. 문자열의 길이는 100을 넘지 않는다. - 출력설명
첫 번째 줄에 각 문자열 s의 각 문자가 문자 t와 떨어진 거리를 순서대로 출력한다. - 입력예제 1
teachermode e - 출력예제 1
10121012210
public class ShortestWordDistance {
public int[] solution1(String sentence, char target) {
int[] distances = new int[sentence.length()];
int position = 100;
// 정방향으로 순회하며 target과 떨어진 거리를 구하여 distances 배열에 넣는다.
for (int i = 0; i < sentence.length(); i++) {
if (sentence.charAt(i) == target) {
position = 0;
} else {
position++;
}
distances[i] = position;
}
// position 값을 최대 문자열의 길이인 100으로 초기화한다.
position = 100;
// 역방향으로 순회하며 target과 떨어진 거리를 구하여 distances 배열에 넣는다.
// 이때 정방향으로 구한 거리보다 짧은 경우에만 distances 배열을 업데이트 한다.
for (int i = sentence.length() - 1; i >= 0; i--) {
if (sentence.charAt(i) == target) {
position = 0;
} else {
position++;
distances[i] = Math.min(distances[i], position);
}
}
return distances;
}
@Test
@DisplayName("가장 빫은 문자거리")
public void main() {
int[] expectedAnswer = {1, 0, 1, 2, 1, 0, 1, 2, 2, 1, 0};
int[] answer1 = solution1("teachermode", 'e');
Assertions.assertArrayEquals(expectedAnswer, answer1);
}
}문자열 압축
알파벳 대문자로 이루어진 문자열을 입력받아 같은 문자가 연속으로 반복되는 경우 반복되는 문자 바로 오른쪽에 반복 횟수를 표기하는 방법으로 문자열을 압축하는 프로그램을 작성하시 오. 단 반복횟수가 1인 경우 생략합니다.
- 입력설명
첫 줄에 문자열이 주어진다. 문자열의 길이는 100을 넘지 않는다. - 출력설명
첫 줄에 압축된 문자열을 출력한다. - 입력예제 1
KKHSSSSSSSE - 출력예제 1
K2HS7E
public class SentenceCompression {
public String solution1(String sentence) {
StringBuilder answer = new StringBuilder();
// 입력받은 문자열의 마지막 문자열을 위해 가장 마지막에 공백을 하나 추가한다.
char[] chars = String.format("%s ", sentence).toCharArray();
int count = 1;
for (int i = 0; i < chars.length - 1; i++) {
if (chars[i] == chars[i + 1]) {
count++;
} else {
answer.append(chars[i]);
if (count > 1) {
answer.append(count);
}
count = 1;
}
}
return answer.toString();
}
@Test
@DisplayName("문자열 압축")
public void main() {
String expectedAnswer = "K2HS7E";
String answer1 = solution1("KKHSSSSSSSE");
assertEquals(expectedAnswer, answer1);
}
}암호
현수는 영희에게 알파벳 대문자로 구성된 비밀편지를 매일 컴퓨터를 이용해 보냅니다. 비밀편지는 현수와 영희가 서로 약속한 암호로 구성되어 있습니다.
비밀편지는 알파벳 한 문자마다 # 또는 이 일곱 개로 구성되어 있습니다.
만약 현수가 “#****#”으로 구성된 문자를 보냈다면 영희는 현수와 약속한 규칙대로 다음과 같이 해석합니다.
- “#*****#”를 일곱자리의 이진수로 바꿉니다. #은 이진수의 1로, *이진수의 0으로 변환합 니다. 결과는 “1000001”로 변환됩니다.
- 바뀐 2진수를 10진수화 합니다. “1000001”을 10진수화 하면 65가 됩니다.
- 아스키 번호가 65문자로 변환합니다. 즉 아스크번호 65는 대문자 'A'입니다.
참고로 대문자들의 아스키 번호는 'A'는 65번, ‘B'는 66번, ’C'는 67번 등 차례대로 1씩 증가 하여 ‘Z'는 90번입니다.
현수가 4개의 문자를 다음과 같이 신호로 보냈다면
#**###############**
이 신호를 4개의 문자신호로 구분하면
#**## --> 'C'
##### --> 'O'
##### --> 'O'
###** --> 'L'
최종적으로 “COOL"로 해석됩니다.
현수가 보낸 신호를 해석해주는 프로그램을 작성해서 영희를 도와주세요.
- 입력설명
첫 줄에는 보낸 문자의 개수(10을 넘지 안습니다)가 입력된다. 다음 줄에는 문자의 개수의 일 곱 배 만큼의 #또는 * 신호가 입력됩니다. 현수는 항상 대문자로 해석할 수 있는 신호를 보낸 다고 가정합니다. - 출력설명
영희가 해석한 문자열을 출력합니다. - 입력예제 1
4 #**###############** - 출력예제 1 COOL
public class Code {
public String solution1(String code, int count) {
StringBuilder answer = new StringBuilder();
for (int i = 0; i < count; i++) {
String tmp = code.substring(i * 7 , (i * 7) + 7);
tmp = tmp.replace("#", "1");
tmp = tmp.replace("*", "0");
// Binary 문자열 -> Decimal Integer -> Ascii Char
answer.append((char) Integer.parseInt(tmp, 2));
}
return answer.toString();
}
@Test
@DisplayName("암호")
public void main() {
String expectedAnswer = "COOL";
String answer1 = solution1("#****###**#####**#####**##**", 4);
assertEquals(expectedAnswer, answer1);
}
}'Algorithm' 카테고리의 다른 글
| [Algorithm] Stack (0) | 2022.02.23 |
|---|---|
| [Algorithm] HashMap (0) | 2022.02.22 |
| [Algorithm] Sliding window (0) | 2022.02.21 |
| [Algorithm] Two Pointers (0) | 2022.02.21 |
| [Algorithm] 배열 다루기 (0) | 2022.02.20 |
