[ Baekjoon - 10/24 ] - 17218번: 비밀번호 만들기

• 문제 링크 : https://www.acmicpc.net/problem/17218

17218번: 비밀번호 만들기

 

• 소요 시간 : LCS 학습하는 시간 포함해서 2시간 반

 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 256MB
   • 문제
     
     • 수형이가 입력한 난수의 길이(1≤길이≤40)
     • 최장공통수열을 구하라는 문제
   • 이해
     • 문제 읽자마자 최장공통수열(LCS) 쓰라는 문제구나 싶었는데, 듣기만 들었지 제대로 학습해 본적이 없어 자료를 찾아보았다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 문제 이해에 어려움은 없고 전형적인 LCS였지만, 입출력 예제1을 보며 어떤 구성인지 확인했다.
3. 문제를 어떻게 해결할 것인가
   
   • 1st 접근 - 전형적인 LCS - 숫자로 dp배열 끝까지 갔다가 돌아오며 문자열을 구하는 방법)
     • LCS를 공부하고 돌아오니, 크게 아래 사진순서와 같이 구할 수 있다는 것을 학습했다.

     • 

     • 우선 각 문자열의 길이를 가로, 세로로 하는 dp 배열을 생성하고, 행의 인덱스가 0이거나 열의 인덱스가 0인 좌표에 0을 넣는다 -> 점화식에 오류가 없도록 하기위함

     • 

     • 왼쪽상단의 0이 아닌 지점부터(1,1)오른쪽으로 쭉 진행하며 <풀이>에 적힌 점화식을 그대로 수행한다.
     • 점화식을 간단히 설명하자면,
       dp[i][j]는 현재 i와 j까지의 최장공통수열의 길이라고 생각하면 된다.
       점화식은 크게 두가지인데, i와j가 가르키는 값이 같거나, 다를때 이다.
       1. 같을때
       서로 문자값이 같다면 최장공통수열에 추가될 것이다. 기존문자열 뒤에 "하나의"문자가.
       즉, 길이가 +1이 된다. 그런데 어느 칸에서 +1을 해야할지 생각해보면 행과 열이 각각 1씩 감소한 위치라는 것을 알 수 있다. (한번 생각해보자)
       2. 다를때
       서로 문자값이 다르다면 최장공통수열에 다른 두 문자가 동시에 추가될 순 없다.
       즉, 다른 문자가 각각 A와 B라면, 현재 시점에서 가능할 수도 있는 공통수열은 
        1) [지금까지 구한 공통수열]
        2) [지금까지 구한 공통수열 + A]
        3) [지금까지 구한 공통수열 + B]
       이렇게 3가지의 경우일 것이다. 하지만 우리는 "최장"공통 수열을 찾아야 하므로 위 셋중에서 가장 큰 값을 넣어줘야하므로 Max연산을 통해 구해주어야한다.
     • 문자가 같을때는 ㄱ으로, 다를때는 ㄴ으로 수행했다는것을 숫자옆에 남겨두었으니 한번 따라가 보길 바란다.
     • 바로 위 사진까지 수행했으면 맵의 가장 우측하단 칸에 최장공통수열의 길이가 저장될 것이다. 하지만 위 문제는 길이가 아닌 내용물을 출력해야 하므로 밑의 과정이 더 필요하다.

     • 

     • 최장공통수열의 형태를 알기위해선 우측하단부터 시작한다.
     • ㄱ이 같은 부분이라 최장공통수열을 만드는데 기여한 부분이므로, 이를 찾아 올라가면 구할 수 있다.
     • ㄴ연산을 한 부분에서 ㄱ연산을 한 부분을 찾아 올라가기 위해서는, 현재 포지션의 맵 값과 같은 아이가 위나 왼쪽에 더있다면 최대한 끝까지 가야한다. 더 이상 왼쪽이나 위쪽에 같은 값이 없다면 ㄱ연산을 한 위치이거나, 처음에 0으로 세팅해주었던 부분일 것이다.
   • 2nd 접근 - 바로 문자열가지고 놀며 한번 배열 끝까지가면 바로 구해지도록 하는 방법)
     • 최장공통수열의 길이를 구하기위해 맵 끝까지 한번가고, 안의 내용물을 얻기위해 다시 끝에서부터 처음위치로 올라오는것에 비효율적이라 느껴, 맵의 각 칸을 정수형이 아닌 문자열로 만들어서 이어붙이는 식으로 한번 진행하면 구해지지않을까 해서 접근하게되었다... 어려웠음

     • 

     • 위와 같은 방식으로 구해보았다.
     • 우선 규칙성을 찾기위해 왼쪽과 위가 같은 문자인 영역에 색칠을 해보았고, 해당 칸을 기준으로 위 점화식처럼 진행해보았다.
     • A와 BCUA의 최장공통수열은 A일꺼고
       A와 BCUAM의 최장공통수열도 A,
       A와 BCUAME의 최장공통수열도 A.... 이므로 A로 전부 세팅했다. 
     • 그리고 다음행에서는 U가 같은 구역이어서 U를 넣고, U와 A가 만나는(1,3) 지점은 U아니면 A중 길이가 가장 긴 아이를 선택해야하는데 둘다 1이라서 U 또는 A가 가능하므로 쭉 넣어주었다.
     • 이와 같은 방식으로 구해보니 마지막 칸에 최장공통수열을 구할 수 있었다!
4. 위 계획을 검증
   • 3번에서 검증까지 마쳤다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main {
            static int lenS1, lenS2;
            static String s1,s2;
            static boolean check;
            static String[][] dpMap;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
                s1 = br.readLine();
                s2 = br.readLine();
                lenS1 = s1.length();
                lenS2 = s2.length();
        
                dpMap = new String[lenS1][lenS2];
                for (int ls1 = 0; ls1 < lenS1; ls1++) {
                    if(s1.charAt(ls1) == s2.charAt(0) || check){
                        dpMap[ls1][0] = s2.charAt(0)+"";
                        check=true;
                    }
                }
        
                check = false;
                for (int ls2 = 0; ls2 < lenS2; ls2++) {
                    if(s1.charAt(0) == s2.charAt(ls2) || check){
                        dpMap[0][ls2] = s1.charAt(0)+"";
                        check=true;
                    }
                }
        
                for (int ls1 = 1; ls1 < lenS1; ls1++) {
                    for (int ls2 = 1; ls2 < lenS2; ls2++) {
                        // 같은 문자라면 추가함
                        if(s1.charAt(ls1) == s2.charAt(ls2)){
                            dpMap[ls1][ls2] = dpMap[ls1-1][ls2-1] + s1.charAt(ls1);
                        } // 다른 문자라면 문자열 길이가 더 긴것을 가져옴
                        else{
                            if(dpMap[ls1-1][ls2] == null){
                                dpMap[ls1-1][ls2] = "";
                            }
                            if(dpMap[ls1][ls2-1] == null){
                                dpMap[ls1][ls2-1] = "";
                            }
                            dpMap[ls1][ls2] = dpMap[ls1-1][ls2].length() > dpMap[ls1][ls2-1].length() ? dpMap[ls1-1][ls2] : dpMap[ls1][ls2-1];
                        }
                    }
                }
                System.out.println(dpMap[lenS1-1][lenS2-1]);
            }
        }

 

• 결과

2번째 방식으로 구현하려다보니, 자바 특성상 String을 선언하기만 하면 ""이 아닌 null이라서 처리에 조금 애를 먹었다. 변수명도 몇번 혼동해서 잘못써서 인덱스 에러도 많이 나고... ㅎㅎ 

다음에 다시 꼭 풀어봐야할것같다..