[BOJ 9028: Iris] 구현, 문자열 | C언어

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

9028번: Iris (비밀번호)

 

문자열에 특정 word가 몇 번 등장하는지, 어디에 등장하는지를 찾는 문제이다.

 

word

- 중복 문자 X

- 문자들이 연속으로 등장할 필요 없음 

- word의 등장위치는 txt상에서 마지막 문자의 위치로 판단함

- 문자의 위치는 0이 아닌 1부터 시작한다 

- 대소문자 구별하지 않는다 

 

 

 

sol1) 스택 이용 (실패염)

---

처음에는 스택에 단어를 넣으면 되겠다고 생각했다. 

 

txt를 앞에서부터 순회하면서 word의 첫번째 문자를 만나면 스택에 넣고, 두번째 문자를 만나면 또 넣고, ... 마지막 문자를 만나면 다 pop 시켜서 counting을 하려했다. 

 

만약 word = "abc" 이고 txt = "apppblllc" 라면, 

stack에 'a'를 push,

'p'는 단어 상에 존재하지 않으므로 pass,

'b'는 단어 상에 있는 문자이면서, 현재 스택의 최상위 문자가 'b'의 바로 전 문자 'a'이므로 push,

 그 다음 'b'는 스택의 최상단 원소와 인덱스 차이가 나지 않기 때문에 pass, 

'l'도 단어 상에 없으므로 pass, 

'c'는 단어 상에 있는 문자이면서, 현재 스택의 최상위 문자 'b' 바로 다음 문자이므로 push.

 

이때 'c'는 word의 마지막 문자이므로 'c' -> 'b' -> 'a' 순으로 pop을 한 후,

counting ++

그리고 현재 txt 상에서의 위치를 기록했다.

 

맞았다고 생각했으나.. 고려하지 못한 것이 있었다. 

txt상에 word 문자들이 반복해서 등장하고 여러 번 등장하는 경우에는 오류가 발생한다. 

 

예를 들어, word="boy", txt = "bbboooyyy"의 경우에는

stack에 b -> bb -> bbb -> bbbo -> bbboy -> bb 가 들어가게 되고,

첫번째, 두번째 'b' 뒤에 올 수 있는 'o'를 무시하게 된다. 

스택 하나로는 여러 word 쌍들을 세기에는 무리가 있다.

 

 

sol2) word 문자별로 등장 횟수 카운팅

---

그래서 다음으로 생각한 방법은,

txt상에 문자들이 출현한 횟수를 기록하되, 순서대로 카운트를 하는 것이다. 

 

txt를 차례대로 순회할 때, 만약 현재 순회하는 문자가 word 상의 문자라면,

word상에서 이 문자보다 앞의 문자의 출현횟수가 더 많아야 카운트가 가능하다.

 

이렇게 하면 word의 각 문자별 출현 횟수를 기록할 int[10] 짜리 배열만 있으면 된다. 

word의 등장위치를 저장할 pos 배열은 문제에서 최대 40000번 등장할 수 있다고 해서 [40000] 배열로 선언함

int cnt = 0;
int pos[40000];
int idx;
char* c;
int len = (int)strlen(word) - 1;
int char_appear[10] = {0,}; // word의 문자들이 출현한 횟수를 기록한다. word의 문자 순서를 고려함.  
int detect;

for(int i = 0; i < len; i++) {
	if(word[i] >= 65 && word[i] <= 90) // 대문자
		word[i] += 32; //소문자 치환
}

for(int i = 0; txt[i] != '\0'; i++) {
	detect  = FALSE;

	if(txt[i] >= 65 && txt[i] <= 90) // 대문자
		txt[i] += 32; //소문자 치환


   	// word의 앞의 문자가 이미 등장했으면 counting한다 
	// 현재 문자보다 하나 앞의 문자가 등장한 횟수가 더 많으면 counting 
	// 첫번째 문자는 무조건 카운팅한다
	if(txt[i] == word[0]) {
		char_appear[0]++;
                
        if(len == 1) {           //만약 마지막 문자라면 플래그 설정 
        	detect = TRUE;
        }
	}
    
    // 만약 word 상의 문자라면
	else if((c = strchr(word, txt[i])) != NULL) {
    	// word내에서 특정 문자의 위치는 주소 값을 뺴서 계산한다. 
		idx = c - word; 

		// 현재 문자보다 word 상의 앞의 문자가 더 많이 등장했다면 카운팅한다
		if(char_appear[idx]  < char_appear[idx - 1]) {
			char_appear[idx]++;
			if(idx == len - 1) { //만약 마지막 문자라면 플래그 설정 
				detect = TRUE;
            }
        }
	}

	// 현재 문자에서 word가 다 완성되었다면 cnt 증가시키고, 위치를 저장한다. 
	if(detect == TRUE) {
		pos[cnt++] = i + 1;
	}
}

 

 

+ 입출력

입출력 때문에 틀렸습니다를 많이 받았다..

 

char word[15];   // '\n' '\0' 을 고려해서 넉넉하게 크기를 잡읍 
char txt[400005];
    
fgets(word, sizeof(word), stdin); // scanf로는 공백 포함 문자열 받을 수 없다.
fgets(txt, sizeof(txt), stdin);

word의 최대길이는 10, txt 최대 길이는 400000이다.  

그래서 배열 크기를 여기에 딱 맞춰 설정했는데 입력을 fgets로 받았다는 걸 고려해야 한다

 

fgets

'\n'을 만날 때까지 문자열을 읽어 들인다. 이 때 이 개행문자도 문자열로 받아온다.

그리고 문자열의 마지막에 \0 널문자도 추가함.

그럼 [10] 버퍼에 단어 10개짜리 스트링을 저장할 수 없다

그래서 그냥 넉넉하게 버퍼를 +5 해버렸다.

 

 

 

scanf 

scanf는 공백이 포함된 문자열을 입력받을 수 없다.

scanf("%[^\n]", str); 이렇게 하면 엔터를 제외한 모든 문자들을 입력으로 받을 수 있다고 한다.

근데 저는 그냥 fgets 쓰겠습니다ㅏ

 

 

%d

문제에서 출력 형식을 숫자로 지정했다. 

근데 아무 생각 없이 맞는 게 없으면 0을 출력하라고 해서 

printf("0\n"); 으로 출력했다^,^ 

형식에 맞춰서 출력하자 printf("%d\n", 0); 

 

문제 조건을 잘 읽 자