백준 10096 세 친구 풀이 python, java

문제로이동

10096번: 세 친구

---

목차

 

---

pypy3

java8

---

테스트케이스

 

백준에서는 첫 번째 테스트케이스만 제공됩니다. NOT IMPOSSIBLE과 NOT 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());		
	}
}