공부 99일차: 백준 12871번 무한 문자열 자바 java

12871 무한 문자열

https://www.acmicpc.net/problem/12871

12871번: 무한 문자열

 

 

 

---

백준 12871번 문제 무한 문자열

---

문제

---

 

 

 

---

과정 생각해보기 & 오답

---

 

1) 오답

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        String s = br.readLine();
        String t = br.readLine();
        int result = 0;
        
        if(s.contains(t) || t.contains(s)) {
            result = 1;
        }
        
        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
    }
 
}
 

 

contains를 사용했으나 "틀렸습니다" 판정 받은 코드

단순히 서로를 포함하고 있으면 무한번 붙인 문자열이 같을 거라고 생각했는데 틀렸다

 

다시 생각해보니까 당연했다

예를 들어,

s = abcdefg

t  = abcdefghi

일 때 t는 s를 포함하고 있지만 무한번 반복된 문자열은 

f(s) = abcdefgabcdefgabcdefgabcdefg..

f(t) = abcdefghiabcdefghiabcdefghiabcdefghi.. 

일 것이기 때문이다

 

그래서 최대 길이가 50이므로, 50자가 넘는 첫 번째 순간까지 서로 포함하거나 같으면 정답일 거라고 생각하여

구현해봤다

하지만 생각해보니 굳이 50까지 가지 않더라도, 두 수 길이의 최소공배수까지만 반복하면 무한히 반복된 문자열이 같을 것이다

 

즉,

1) 최대 길이인 50과 같거나 커질 때까지 반복

2) 최소공배수만큼 반복

 

 

 

---

정답 인정 코드

---

 

1) 50과 같거나 넘었을 때 비교

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        String s = br.readLine();
        String t = br.readLine();
        int result = 0;
        
        
        if(f(s).contains(f(t)) || f(t).contains(f(s))) {
            result = 1;
        }
        
        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
    }
    
    public static String f(String str) {
        while(true) {
            str = str.concat(str);    //str에 str 붙이기
            if(str.length() >= 50) {    //str의 길이가 50이거나 넘으면
                break;                    //반복문 종료
            }
        }
        return str;
    }
 
}

 

위에서 적은대로 길이가 50이 되거나 넘으면 멈춰서 비교하는 코드

 

 

 

2) 최소공배수만큼만 반복하는 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        String s = br.readLine();
        String t = br.readLine();
        String strS = s;
        String strT = t;
        int result = 0;
        
 
        if (s.length() != t.length()) {
            int len = lcm(s.length(), t.length());
 
            while (strS.length() != len) {
                strS += s;
            }
 
            while (strT.length() != len) {
                strT += t;
            }
        }
 
        if(strS.equals(strT)) {
            result = 1;
        }
        
        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
    }
    
    // 최소공배수를 구하기 위한 최대공약수 메서드
    public static int gcd(int x, int y) {
        if(y == 0)
            return x;
        else
            return gcd(y, x%y);
    }
    
    // 최소공배수
    public static int lcm(int x, int y) {
        return x*y/gcd(x,y);
    }
 
}
 

 

concat을 쓰지 않아도 +만으로도 충분히 구현할 수 있었다

사실 result 변수도 딱히 필요치 않았던 것 같다

 

 

 

---

둘 다 시간은 비슷비슷했다