반응형
10096번: 세 친구
준규, 해빈, 진욱이는 다음과 같은 게임을 한다. 먼저, 준규가 문자열 S를 고른다. 그 다음, 해빈이는 S의 뒤에 S를 붙인 새로운 문자열 T를 만든다. 마지막으로 진욱이는 문자열 T의 어딘가(시작이
www.acmicpc.net
목차


테스트케이스

백준에서는 첫 번째 테스트케이스만 제공됩니다. 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());
}
}
반응형
'OnlineJudge' 카테고리의 다른 글
SWEA 2805 농작물 수확하기 풀이 java (0) | 2021.02.03 |
---|---|
백준 1018 체스판 다시 칠하기 풀이 python, java (0) | 2021.01.30 |
백준 1002 터렛 풀이 python, java (0) | 2021.01.27 |
백준 2589 보물섬 풀이 python, java (0) | 2021.01.21 |
백준 2217 로프 풀이 python, java (0) | 2021.01.20 |