[백준 BOJ] 1235번 학생 번호 (C++/cpp)

문제 설명

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

1235번: 학생 번호

 

접근 방법 - 문자열 연산의 응용문제

백준의 1235번 문제는 문자열 연산에 있어 다소 심화적인 원리를 다루고 있는 문제이다.

해당 문제는, 주어진 학생 번호에 대하여 학생들을 구분하는 데에 필요한 최소 번호 자릿수를 출력해야 하는 문제이다.

이 문제에 있어 중요한 점은 중복만 없는 선에서 번호의 자릿수를 최소화해야 한다는 점이다.

이를 통해 필자는 첫 번째 자릿수부터 시작하여 조금씩 길이를 늘려가며 번호들끼리 비교해보는 방법을 사용해보았다.

(사실 이건 이거대로 노가다였다 카더라)

이때 필자는 이 과정에서 아래의 함수를 사용해보았는데 함께 참고해보길 바란다.

st.substr([start_substring], [length_substring])
// 문자열 중 일부를 잘라 부분 문자열을 만들어주는 함수

해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

위 함수가 어색하다면, 이에 대한 설명과 코드도 있기 때문에 함께 참고해보아도 좋을 것 같다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 학생의 번호들을 저장할 배열(arr)을 전역 변수로 미리 선언해둔다.

 

2) 학생의 수(n)와 학생 번호들(arr)을 순차적으로 입력받는다.

 

3) 최소 문자열 길이를 연산하는 데에 사용할 변수 cnt를 0으로 초기화하여 선언한다.

cnt는 첫 번째 자릿수부터 시작하여 문자열의 길이를 저장할 예정이다.

 

4) arr에 있어 첫 번째 학생 번호의 길이만큼 하여 반복문을 실행하며 아래의 연산을 취한다.

(이때, 번호의 첫 번째 자릿수부터, 즉 가장 오른쪽 자릿수부터 시작하여 비교할 예정이다.)

- cnt의 크기를 1씩 증가하여 부분 문자열을 만들 길이를 조정하도록 한다.

- 부분 문자열들끼리 동일한 것이 있는지를 판별하기 위해 equal 변수를 0으로 초기화하여 선언한다.

- 이중 반복문을 통해 2개의 문자열을 선별하여 cnt의 크기에 따른 부분 문자열을 만들어 서로 동일한지 비교한다.

만일 동일하다면, 현재 길이로는 번호로 학생들을 구분할 수 없다는 것을 뜻한다. 따라서 이 경우에는 cnt의 길이를 1 증가하여 다시 처음부터 연산을 수행하도록 한다.

다만 equal의 값이 그대로 0이라면, 동일한 번호가 없음을 뜻하며 이대로 학생들을 구분할 수 있음을 뜻한다. 이 경우에는 4)의 모든 반복문을 탈출하도록 한다.

 

5) 최종적으로 연산 완료된 cnt의 값을 출력한 뒤, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <string>
#define endl '\n'
using namespace std;

//백준 1235번 코드
string name[1001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> name[i];
	}

	int cnt = 0;
	for (int i = 1; i <= name[0].length(); i++) {
		cnt++;
		int equal = 0;
		for (int j = 0; j < n; j++) {
			for (int k = j + 1; k < n; k++) {
				string a = name[j].substr(name[j].length() - i, cnt);
				string b = name[k].substr(name[k].length() - i, cnt);
				if (a == b) {
					equal++;	break;
				}
			}
			if (equal != 0) { break; }
		}
		if (equal != 0) {
			continue;
		}
		else { break; }
	}

	cout << cnt << endl;
}

 

제출 결과

(2022.07.14 백준 1235번 문제 제출 결과)