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