문제
머쓱이는 태어난 지 11개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음과 네 가지 발음을 조합해서 만들 수 있는 발음밖에 하지 못하고 연속해서 같은 발음을 하는 것을 어려워합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ babbling의 길이 ≤ 100
- 1 ≤ babbling[i]의 길이 ≤ 30
- 문자열은 알파벳 소문자로만 이루어져 있습니다.
입출력 예
풀이방법
자바 코드(1)
1. 아기가 낼 수 있는 4개의 소리를 배열에 넣는다.
2중 반복문을 돌며 babbling에 baby가 포함된다면 해당 baby 언어를 baby의 인덱스로 바꾼다.
예를 들어 "ayaayayewoo" 라는 단어가 있다면 "0012"로 바뀔 것이다.
"ayam" 이라는 단어는 "0m"으로 바뀔 것이다.
String[] baby = {"aya", "ye", "woo", "ma"};
for(int i=0; i<baby.length; i++){
for(int j=0; j<babbling.length; j++){
if(babbling[j].contains(baby[i])){
babbling[j] = babbling[j].replace(baby[i], i+"");
}
}
}
2. 반복문을 돌며 현재 변경된 단어들이 숫자인지 판별한다. 위의 예시에서 "0012"로 변했다는 것은 아기가 모두 낼 수 있는 소리임을 의미하므로 모두 숫자로 바뀐다.
하지만 "0m"은 아기가 낼 수 없는 소리인 m 도 포함되어 있기 때문에 숫자로 변경될 수 없다.
그래서 isNum(함수 설명은 생략하겠음.) 로 숫자인지를 판단한다.
그리고 연속되는 숫자인지를 판별하기 위해 문자로 잘라서 두 문자를 비교해준다.
for(int i=0; i<babbling.length; i++){
if(isNum(babbling[i])){
char c = babbling[i].charAt(0);
boolean check = true;
for(int j=1; j<babbling[i].length(); j++){
if(c == babbling[i].charAt(j)){
check = false;
break;
}else{
c = babbling[i].charAt(j);
}
}
if(check){
answer++;
}
}
}
코드를 실행했더니 코드는 정상적으로 실행되지만 실행 시간을 줄이고 싶어서 다른 풀이를 참고했다.
자바 코드(2)
1. 반복문을 돌며 만약 연속된 소리가 있다면 넘어간다.
이를 처리해준다면 2중 반복문 없이 1개의 반복문만 사용할 수 있다.
for(int i = 0; i < babblings.length; i++) {
if(babblings[i].contains("ayaaya") || babblings[i].contains("yeye") || babblings[i].contains("woowoo") || babblings[i].contains("mama")) {
continue;
}
}
2. 4개의 소리들이 babblings에 포함되어 있다면 " "로 만들어주고 마지막에 공백을 제거한다.
그리고 길이가 0이라면 아기가 모두 낼 수 있는 소리이므로 answer를 증가한다.
babblings[i] = babblings[i].replace("aya", " ");
babblings[i] = babblings[i].replace("ye", " ");
babblings[i] = babblings[i].replace("woo", " ");
babblings[i] = babblings[i].replace("ma", " ");
babblings[i] = babblings[i].replace(" ", "");
if(babblings[i].length() == 0) answer++;
주의할 점
babblings[i] = babblings[i].replace("aya", "");
babblings[i] = babblings[i].replace("ye", "");
babblings[i] = babblings[i].replace("woo", "");
babblings[i] = babblings[i].replace("ma", "");
처음에는 위의 코드처럼 굳이 " "로 바꾸지 않고 ""로 바꾸면 코드 한 줄 줄일 수 있는거 아닌가? 생각했다.
그치만 왜인지 실패가 떴다. 반례도 없고 이유도 모르겠어서 답답해하던 찰나 반례가 생각났다.
바로 "wayaoo" 와 같은 문자다.
일단 육안으로 봤을 때는 아기가 소리 낼 수 없는 소리인 w, oo가 포함되어 있다.
하지만 위의 코드로 돌려봤을 때,
babblings[i] = babblings[i].replace("aya", ""); 에 의해서 woo가 되고
babblings[i] = babblings[i].replace("woo", ""); 를 만족하기 때문에 아기가 낼 수 있는 소리라고 판단해버린다.
하지만 이것은 woo를 먼저 실행하고 aya를 실행했다면 아기가 낼 수 없는 소리라고 판단할 것이다.
이러한 반례 때문에 ""로 변환하는 것이 아닌 " "로 변환하는 것이었다.
위와 같이 변환할 경우
babblings[i] = babblings[i].replace("aya", " "); 에 의해서 w oo가 되고
babblings[i] = babblings[i].replace("woo", " "); 공백에 의해 w oo 와 woo가 다른 문자로 판별되기 때문에 원하는 결과를 도출할 수 있다.
코틀린 코드는 자바 코드(2)와 동일하므로 생략하겠다.
자바 코드 (1)
class Solution {
public int solution(String[] babbling) {
int answer = 0;
String[] baby = {"aya", "ye", "woo", "ma"};
for(int i=0; i<baby.length; i++){
for(int j=0; j<babbling.length; j++){
if(babbling[j].contains(baby[i])){
babbling[j] = babbling[j].replace(baby[i], i+"");
}
}
}
for(int i=0; i<babbling.length; i++){
if(isNum(babbling[i])){
char c = babbling[i].charAt(0);
boolean check = true;
for(int j=1; j<babbling[i].length(); j++){
if(c == babbling[i].charAt(j)){
check = false;
break;
}else{
c = babbling[i].charAt(j);
}
}
if(check){
answer++;
}
}
}
return answer;
}
public boolean isNum(String s){
try{
Integer.parseInt(s);
return true;
}catch(Exception e){
return false;
}
}
}
자바 코드(2)
class Solution {
public int solution(String[] babblings) {
int answer = 0;
for(int i = 0; i < babblings.length; i++) {
if(babblings[i].contains("ayaaya") || babblings[i].contains("yeye") || babblings[i].contains("woowoo") || babblings[i].contains("mama")) {
continue;
}
babblings[i] = babblings[i].replace("aya", " ");
babblings[i] = babblings[i].replace("ye", " ");
babblings[i] = babblings[i].replace("woo", " ");
babblings[i] = babblings[i].replace("ma", " ");
babblings[i] = babblings[i].replace(" ", "");
if(babblings[i].length() == 0) answer++;
}
return answer;
}
}
자바 코드(1), 자바 코드(2)를 비교했을 때, 반복문을 한 번만 돌리는 자바 코드(2)의 시간이 압도적으로 짧다.
코틀린 코드
class Solution {
fun solution(babbling: Array<String>): Int {
var answer: Int = 0
for(i in 0 until babbling.size){
if(babbling[i].contains("ayaaya") || babbling[i].contains("yeye") || babbling[i].contains("woowoo") || babbling[i].contains("mama")){
continue
}
babbling[i] = babbling[i].replace("aya"," ")
babbling[i] = babbling[i].replace("ye"," ")
babbling[i] = babbling[i].replace("woo"," ")
babbling[i] = babbling[i].replace("ma"," ")
babbling[i] = babbling[i].replace(" ","")
println(babbling[i])
if(babbling[i].length == 0){
answer++
}
}
return answer
}
}
근데 이상하게도 자바 코드(2)와 코틀린 코드는 동일한데 시간이 너무 많이 차이난다.
이유는 모르겠다.
https://school.programmers.co.kr/learn/courses/30/lessons/133499
'Algorithm > java, kotlin' 카테고리의 다른 글
[백준/Java, Kotlin] 1484번 다이어트 (2) | 2024.09.24 |
---|---|
[백준/Java, Kotlin] 2096번 내려가기 (2) | 2024.09.02 |
[백준/Java, Kotlin] 18114번 블랙 프라이데이 (1) | 2024.08.29 |
[백준/Java, Kotlin] 1806번 부분합 (0) | 2024.08.22 |
[백준/Java, Kotlin] 2531번 회전 초밥 (0) | 2024.08.22 |