BOJ_18269 : Where Am I?_ USACO 2019 December Contest > Bronze

BOJ_18269 : Where Am I?_ USACO 2019 December Contest > Bronze 2번 문제다.

https://www.acmicpc.net/problem/18269

18269번: Where Am I?

영어라서 애먹었음.

문제

Farmer John has gone out for a walk down the road and thinks he may now be lost!

Along the road there are N farms (1≤N≤100) in a row. Farms unfortunately do not have house numbers, making it hard for Farmer John to figure out his location along the road. However, each farm does have a colorful mailbox along the side of the road, so Farmer John hopes that if he looks at the colors of the mailboxes nearest to him, he can uniquely determine where he is.

Each mailbox color is specified by a letter in the range A..Z, so the sequence of N mailboxes down the road can be represented by a string of length N containing letters in the range A..Z. Some mailboxes may have the same colors as other mailboxes. Farmer John wants to know what is the smallest value of K such that if he looks at any sequence of K consecutive mailboxes, he can uniquely determine the location of that sequence along the road.

For example, suppose the sequence of mailboxes along the road is 'ABCDABC'. Farmer John cannot set K=3, since if he sees 'ABC', there are two possible locations along the road where this consecutive set of colors might be. The smallest value of K that works is K=4, since if he looks at any consecutive set of 4 mailboxes, this sequence of colors uniquely determines his position along the road.

입력

The first line of input contains N, and the second line contains a string of N characters, each in the range A..Z.

출력

Print a line containing a single integer, specifying the smallest value of K that solves Farmer John's problem.

예제 입력 1

7 ABCDABC

예제 출력 1

4

농부 존은 길 따라 간거 같았는데 길을 잃었습니다!
길 따라 가는길에 가로로 N개의 농장이 있었고, 농장은 참 거시기 하게도 번호가 없었습니다. 그래서 존아저씨는 자기가 어디있었는지 모르겠어요, 다행히도 농장마다 총천연색 우체통이 길따라 있어서, 이걸로 자기 자신이 어디있는지 알 수도 있겠다는 생각을 했어요.
각각의 우체통은 A부터 Z까지 색이 정해져 잇습니다. N개의 우체통이 N개의 농장 범위를 표현합니다. 어떤 우체통은 색이 같을수도 있어요, 존아저씨는 알고싶었어요 가장 작은 K의 값이 만약 어떤 K개의 우체통을 보면서 순서를 찾을수 있다면요, 그렇게 특별한 방법으로 자기가 어디에 있는지 알고 싶었어요.
예를 들어 ABCDABC라는 우체통색이 정렬되면 농부존아저씨는 K=3이라고 생각못합니다. ABC를 보면 두가지 해석이 가능하니까. 그러지 말고 ABCD 같이 유일한 길을 찾으시오!

입력 : N을 포함한 첫줄이 주어집니다. 두번째는 N의 문자열이 주어지고요, A부터 Z 사이입니다.

출력 : 농부존씨 해결법으로 해결하시오.

 

그니까 문자열 ABCDEABC가 있다고 치면

 

AB... 이렇게 읽다가 ABC 가 나올때 ABC가 두개나 있지 않은가. 이 다음거 긘까 안겹치는거 ABCD를 찾는게 목표다.

그래서

i 는 위치, k는 크기(k=1), 문자열 n, 변수 j까지 만들어줌.
101칸 짜리 배열 arr를 만들고 값을 입력받음.
101칸짜리 배열 temp 만들어줌. 이 배열이 비교군임.

k = 1 ~ 100 까지 반복하는 포문 {
__i = 0 ~ n-k+1까지 반복하는 포문 {
___temp 에 arr[i] ~ arr[i+k-1]까지 입력.
____j=i+1 ~ n-k+1까지 반복하는 포문 {
_____만약 temp == arr [j]~arr[j+k-1]값이랑 같으면
_______ break;
_____만약 j <= n-k+1이면
_______break;

이라고 짜고.

#include <stdio.h>
#include <string.h>
int johnway(char*, int);

int main(void) {
	int n, ret=-1;
	char arr[101];
	
	scanf("%d %s", &n, arr);
	
	ret = johnway(arr, n);
	
	printf("%d\n", ret);
	
	return 0;
}

int johnway(char arr[], int n) {
	int k, i, j;
	char temp[101];
	for(k=1; k<101; k++) {
		for(i=0; i<=n-k+1; i++) { //i는 비교 기준점. 
			//temp에 문자열 복사.
			strncpy(temp, arr+i, k); //문자열을 필요한만큼 복사. 
			for(j=i+1; j<=n-k+1; j++) {
				//문자열 비교.
				if(strncmp(arr+j, temp, k)==0) //+j를 붙여 비교하게.
					break;
			}
			if(j <= n-k+1) {
				break; //i_break
			}
		}
		if(i > n-k+1) {
			break; // k_break
		}
	}
	return k;
}

int johnway(char*, int); //아래 JOHNWAY 라는 함수가 나온다고 미리 힌트 주는 내용.

int main(void) {
int n, ret=-1;  //n  개의 숫자와 배열을 받을꺼고 ret이라는 함수도 하나 만들어줌. 리턴 받기 위해
char arr[101];

scanf("%d %s", &n, arr);

ret = johnway(arr, n);  //존아저씨 식대로 숫자를 넣어줘서

printf("%d\n", ret);  //ret 값 출력.

return 0;
}

int johnway(char arr[], int n) {  //존의길. 존 아조씨 방식대로
int k, i, j;
char temp[101];  //비교를 위한 temp라는 배열 만들어줌. 문자여서 초기화할필요없음.
for(k=1; k<101; k++) {

for(i=0; i<=n-k+1; i++) { //i는 비교 기준점.  i부터 시작해서 좌라라락 뒤에도 대입해볼꺼임 끝까지.
//temp에 문자열 복사.
strncpy(temp, arr+i, k); //문자열을 필요한만큼 복사.  strcpy, 문자열 복사하는 함수인데 n이 붙어서 원하는 글자까지 복사가능.
for(j=i+1; j<=n-k+1; j++) {
//문자열 비교.
if(strncmp(arr+j, temp, k)==0) //+j를 붙여 비교하게.  //strcmp 함수인데 이건 원하는 글자까지 비교가능.
break;
}
if(j <= n-k+1) {  //그래서 순차적으로 가다가 같은 문자열이 뒤에서 나오면 탈출.
break; //i_break
}
}
if(i > n-k+1) {  // 위에 포문에서 돌다가 중간에 나왔네?? 하면 나도 나가야지 하고 나가는 곳.
break; // k_break 
}
}
return k;
}

 

아 어려워.