[SW Expert Academy][코딩테스트] 20955. XY 문자열 1

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=1&problemLevel=2&problemLevel=3&problemLevel=4&contestProbId=AY_gm8_6NjcDFAVF&categoryId=AY_gm8_6NjcDFAVF&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1

미해결

• 어떤게 문제가 되서 안풀리는지 모르겠다. set 때문에 메모리 과다로 그런줄 알고 파이썬으로 set지우고 풀이를 해봤는데도 여전히 오류...

python 풀이

from collections import deque

for tc in range(1,int(input())+1):

    s=input()
    e=input()
    q=deque()
    k_set=set()
    q.append(s)
    k_set.add(s)
    tf=False
    while q:
        now=q.popleft()
        
        if now==e:
            print("#"+str(tc)+" Yes")
            tf=True
            break
        if len(now)>=len(e) or len(now)>1000:
            continue
        next1=now+"X"
        next2=now[::-1]+"Y"
        if next1 not in k_set:
            q.append(next1)
            k_set.add(next1)
        if next2 not in k_set:
            q.append(next2)
            k_set.add(next2)
    if not tf:
        print("#"+str(tc)+" No")

java 풀이

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc=sc.nextInt();
        for(int i=1;i<=tc;i++){
            String s=sc.nextLine();
            String target=sc.nextLine();
            Queue<String> q=new LinkedList<>();
            Set<String> set=new HashSet<>();

            int target_length=target.length();

            q.add(s);
            set.add(s);
            boolean tf=false;
            while(!q.isEmpty()){
                String now=q.poll();
                if(now.length()>target_length){
                    continue;
                }
                if(now.equals(target)){
                    System.out.println("Yes");
                    tf=true;
                    break;
                }
                String case1=changeString1(now);
                String case2=changeString2(now);
                if(!set.contains(case1)){
                    q.add(case1);
                    set.add(case1);
                }
                if(!set.contains(case2)){
                    q.add(case2);
                    set.add(case2);
                }
            }
            if(!tf){
                System.out.println("No");
            }
        }
    }
    public static String changeString1(String s){
        return s+"X";
    }
    public static String changeString2(String s){
        StringBuilder sb=new StringBuilder(s);
        sb.reverse();
        sb.append("Y");
        return sb.toString();
    }
}