[C++] 백준 1235번 학생 번호

1. 문제이해

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

1235번: 학생 번호

 

학생의 수(N)와 각 학생들의 번호가 주어진다.

번호를 뒤에서 k자리만 남겨놓았을 때, 모든 번호를 다르게 만들 수 있는 k의 최솟값을 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

입력받은 학생 번호를 뒤에서 k만큼 남겨놓을 때, 모든 번호를 다르게 만드는 최솟값을 구하는 문제이다.

아래 예제 입력 1을 통해 풀이 방법을 자세히 알아보자.

 

---

 

<예제 입력 1>

N = 3

1212345

1212356

0033445

 

3명의 학생의 학생번호가 위와 같이 주어진다.

뒤에서부터 k자리를 확인해야 하므로, 필자는 편의를 위해 번호를 뒤집었다.

 

5432121

6532121

5443300

 

번호를 뒤집은 뒤, 길이(length)가 1인 경우부터 번호를 자른다.

길이(length)가 1인 경우, 번호는 5 6 5 . 번호가 모두 다르지 않으므로 길이를 늘려서 다시 연산한다.

번호가 모두 달라질때까지 길이를 늘려 위와 같은 연산을 반복,

번호가 모두 달라졌을 때의 길이가 문제에서 구하려고 하는 최솟값이다.

 

---

 

그렇다면, 번호가 모두 다른지는 어떻게 판별할까?

필자는 set container 를 이용했다.

set은 key라 불리는 원소의 집합으로, 중복을 자동으로 제거하고 삽입이 되면 자동으로 정렬된다.

필자는 set은 중복을 자동으로 제거한다는 이 점을 이용해 다음과 같은 순서로 연산했다.

 

1. 길이가 1인 경우부터 번호를 잘라 set에 저장

2 - 1. set의 size와 학생번호의 수(N)가 같다면, 모든 번호가 다른 것이므로 해당 길이가 최솟값

 2 - 2. set의 size와 학생번호의 수(N)가 다르다면, 같은 번호가 있는 것이므로 길이를 늘려서 재연산

 

위와 같은 순서에 따라 작성한 코드는 아래와 같다.

 

 

 

3. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main() {
	int N;
	string input;
	vector <string> student_num;
	int length = 1;
	int result;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> input;
		// 편의를 위해 입력된 번호를 뒤집어서 저장
		reverse(input.begin(), input.end());
		student_num.push_back(input);
	}

	while (1) {
		set <string> s;  // set은 중복허용 X

		// length 만큼 번호를 잘라 set s에 삽입
		for (int i = 0; i < N; i++) {
			s.insert(student_num[i].substr(0, length));
		}

		// 1. s의 크기와 입력받은 번호의 개수(N)가 같다면, 모두 다른 값인 것
		//    -> 모든 학생 번호가 다르므로 해당 길이가 최솟값
		if (s.size() == N) {
			break;
		}

		// 2. s의 크기와 입력받은 번호의 개수(N)가 다르다면, 같은 값이 있는 것
		//    -> 모든 학생의 번호가 달라야하므로, 길이를 늘려서 다시 연산
		else {
			length++;
		}

	}

	result = length;
	cout << result;

	return 0;
}

2. 문제풀이에서 도출한 방식에 따라 작성한 코드는 위와 같다.

먼저 학생번호 수(N)와 각 번호를 입력받는다. (번호는 입력받은 뒤, 뒤집어서 벡터 student_num에 저장)

이후, while 문을 통해 2. 문제풀이에서 도출한 순서에 따라 번호를 모두 다르게 만들 수 있는 최솟값을 찾는다.

 

1. 길이가 1인 경우부터 번호를 잘라 set에 저장

: for문에서 substr 함수를 이용해 각 학생번호를 length 만큼 잘라 set s에 저장한다.

 

2 - 1. set의 size와 학생번호의 수(N)가 같다면, 모든 번호가 다른 것이므로 해당 길이가 최솟값

: set s의 size와 학생번호의 수 N이 같다는 것은,

set 저장 시 중복이 없었다는 것. 모든 번호가 다른 값이었다는 것. 이므로,

해당 length가 모든 학생의 번호를 다르게 만드는 길이의 최솟값이 된다.

: if (s.size() == N) { break; } 

 

 2 - 2. set의 size와 학생번호의 수(N)가 다르다면, 같은 번호가 있는 것이므로 길이를 늘려서 재연산

: set s의 size와 학생번호의 수 N이 다르다는 것은,

set 저장 시 중복이 있었다는 것. 같은 번호가 있었다는 것. 이므로,

length값을 늘려 다시 연산하도록 한다.

: else { length++; } 

 

 

주석 없는 코드는 왼쪽 아래 더보기 참고바랍니다.😊

<주석 없는 코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main() {
	int N;
	string input;
	vector <string> student_num;
	int length = 1;
	int result;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> input;
		reverse(input.begin(), input.end());
		student_num.push_back(input);
	}

	while (1) {
		set <string> s; 

		for (int i = 0; i < N; i++) {
			s.insert(student_num[i].substr(0, length));
		}

		if (s.size() == N) {
			break;
		}

		else {
			length++;
		}

	}

	result = length;
	cout << result;

	return 0;
}

 

 

---

실버 4라는 난이도에 비해 나에게는 생각보다 어려웠던 문제였다..😥

문제이해는 잘 됐는데, 코드로 막상 구현하려니 어려웠다.

아마 substr을 쓰지 않았으면 한참을 고민했을 것 같다..ㅎㅎ

 

문제에 대한 질문이나 지적은 언제나 감사히 받고 있습니다.😊