강승현입니다
article thumbnail
반응형

문제로이동

 

10096번: 세 친구

준규, 해빈, 진욱이는 다음과 같은 게임을 한다. 먼저, 준규가 문자열 S를 고른다. 그 다음, 해빈이는 S의 뒤에 S를 붙인 새로운 문자열 T를 만든다. 마지막으로 진욱이는 문자열 T의 어딘가(시작이

www.acmicpc.net


목차

     


    pypy3
    java8

    테스트케이스

     

    백준에서는 첫 번째 테스트케이스만 제공됩니다. NOT IMPOSSIBLENOT UNIQUE 조건이 명시는 되어있는데 뭔가 이상해서 찾아보니 입력이 안된건지 더 있길래 가져왔습니다. 참고하시면 됩니다.


    문제 설명

    자세한 풀이 방법은 소스코드 Python의 주석처리를 참고하시기 바랍니다.

    처음엔 모든 알파벳이 같은 경우를 생각하지 않고 아니 이게 맞는데 왜 틀려?? 라고 생각했다가 3번의 WA를 받고 깨우쳤습니다..

     

    Python 위주로 풀었으며 Java로는 그대로 옮겨썼습니다.

    하지만 아이러니하게도 출력 초과를 받았고 알고보니 반복문의 범위를 잘못 설정해서 벌어진 일이었습니다.

     


    소스 코드

    Python

    ulen은 네이밍 실수 입니다. slen이 맞습니다. 참고하세요!

    import sys
    input = sys.stdin.readline
    
    def solution():    
        N = int(input())
        U = input().rstrip()
        #홀수가 아닌 경우(2*len(S)+1(T)를 생각하면 무조건 홀수개)
        if N%2==0:return 'NOT POSSIBLE'
    
        ulen = N//2 #S의 크기        
        # 모든 알파벳이 같은 경우
        if U[0]*N == U:return U[:ulen]
    
        # 유일하지 않은 경우
        # 1. ABABA
        # 2. ABCABCA
        if U[:ulen]==U[ulen:-1] and U[1:ulen+1]==U[ulen+1:]:
            return "NOT UNIQUE"
        
        # 왼쪽~가운데에 T가 있는 경우
        # 1. TABAB
        # 2. ATBAB
        # 3. ABTAB
        for i in range(ulen):
            if U[i]!=U[ulen+1+i]:#다른 경우, 한칸 앞을 비교
                # print(U[i+1:ulen+1],U[ulen+1+i:])
                if U[i+1:ulen+1]==U[ulen+1+i:]:#앞에건 같으니까 뒤에 남은거만 비교
                    return U[ulen+1:]
                else:break#이건 오른쪽에 위치한단 뜻                
        else:#정확히 중간에 T가 위치함
            return U[:ulen]
    
        # 오른쪽~끝에 T가 있는 경우
        # 1. ABATB
        # 2. ABABT
        for i in range(ulen):
            if U[i]!=U[ulen+i]:            
                # print(U[i:ulen],U[ulen+i+1:])
                if U[i:ulen]==U[ulen+i+1:]:#오른쪽으로 한칸
                    return U[:ulen]
                else:
                    return 'NOT POSSIBLE'
        else:#맨 끝에 T가 위치하는 경우
            return U[:ulen]
    
    if __name__ == "__main__":
        print(solution())

    Java8

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class Main {
    	static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));	
    	public static StringBuilder solve() throws NumberFormatException, IOException {
    		StringBuilder sb = new StringBuilder();		
    		int N = Integer.parseInt(bf.readLine());
    		int i = 0;
    		String U = bf.readLine();
    		
    		if(N%2==0)return sb.append("NOT POSSIBLE");
    		
    		int slen = N/2;
    		for(i = 0; i<U.length();i++)
    			if(U.charAt(0)!=U.charAt(i))break;
    		if(i==U.length())return sb.append(U.substring(0, slen));
    		if(U.substring(0,slen).equals(U.substring(slen,N-1))&&U.substring(1, slen+1).equals(U.substring(slen+1)))return sb.append("NOT UNIQUE");
    		
    		int right = slen+1;		
    		for(i =0; i<slen;i++) {
    			if(U.charAt(i)!=U.charAt(right+i))
    				if(U.substring(i+1, right).equals(U.substring(right+i))) {return sb.append(U.substring(right));}
    				else break;
    		}
    		if(i==slen)return sb.append(U.substring(0, slen));
    		
    		right = slen;
    		for(i=0;i<slen;i++) {
    			if(U.charAt(i)!=U.charAt(right+i))
    				if(U.substring(i, slen).equals(U.substring(right+i+1)))return sb.append(U.substring(0, slen));
    				else return sb.append("NOT POSSIBLE");
    		}
    		if(i==slen)return sb.append(U.substring(0, slen));
    		return null;
    	}
    	public static void main(String[] args) throws IOException {
    		System.out.println(solve());		
    	}
    }
    
    반응형
    profile

    강승현입니다

    @CODe_

    포스팅에 대한 피드백을 환영합니다!
    피드백 작성자를 존중하며, 함께 공유하고 성장할 수 있는 기회가 되기를 기대합니다.의견이나 조언이 있다면 언제든지 자유롭게 남겨주세요!

    article prev thumbnail
    article next thumbnail
    profile on loading

    Loading...