학생 번호(문자열)
문제
이번에는 학생들을 더욱 효율적으로 관리하기 위해 학생마다 고유한 학생 번호를 부여하기로 하였다. 학생 번호는 0부터 9 사이의 숫자로 이루어진 문자열로, 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같다.
학생들의 번호를 부여해 놓고 보니, 김진영 조교는 어쩌면 번호가 지나치게 긴 것은 아닌가 싶은 생각이 들었다. 예를 들어 아래와 같은 7자리의 학생 번호를 보자.
| 이름 | 번호 |
|---|---|
| 오민식 | 1212345 |
| 김형택 | 1212356 |
| 이동호 | 0033445 |
이처럼 학생 번호를 굳이 7자리로 하지 않고, 뒤에서 세 자리만을 추려서 남겨 놓아도 모든 학생들의 학생 번호를 서로 다르게 만들 수 있다.
| 이름 | 번호 |
|---|---|
| 오민식 | 345 |
| 김형택 | 356 |
| 이동호 | 445 |
하지만 세 자리보다 적게 남겨 놓아서는 모든 학생들의 학생 번호를 서로 다르게 만들 수 없다.
학생들의 번호가 주어 졌을 때, 뒤에서 k자리만을 추려서 남겨 놓았을 때 모든 학생들의 학생 번호를 서로 다르게 만들 수 있는 최소의 k를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 학생의 수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 학생 번호가 순서대로 주어진다. 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같으며, 0부터 9 사이의 숫자로 이루어진 문자열이 주어진다. 문자열의 길이는 100보다 작거나 같다.
출력
첫째 줄에 구하고자 하는 가장 작은 k값을 출력한다.
예제 입력
3
1212345
1212356
0033445예제 출력
3Code
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const N = +input[0]; // 학생의 수
let studentNumber = []; // 각 학생 번호
for (let i = 1; i <= N; i += 1) studentNumber.push(input[i]);
const numberLen = studentNumber[0].length; // 학생 번호 길이
let minLen = 1; // 학생 번호 다르게 만들 수 있는 번호 최소길이
// 각 다른 번호나올 때까지 반복문 수행
while (minLen <= numberLen) {
let numbers = []; // 같은 번호가 있는지 확인하기 위해 배열
for (let student = 0; student < N; student += 1) {
const num = studentNumber[student].slice(numberLen - minLen); // 끝부터 minLen만큽 번호 추출
if (!numbers.includes(num)) numbers.push(num); // 같은 번호가 없을 떄만 배열에 넣기
}
// 배열의 길이가 N개만큼 존재하지 않을 경우는 같은 번호가 존재하므로 최소길이가 될 수 없음
// 반면, N개만큼 존재하면 셋 다 다른 번호를 가진다는 의미이므로 최소길이가 됨 => 반복문 수행 종료
if (numbers.length === N) break;
minLen += 1;
}
console.log(minLen);풀이 및 해설
- 구하고자 하는 것 = N명의 학생 번호를 짧게 만들 때 각각의 학생을 구분 가능한 최소 길이 구하기
- 문자열
slice이용- 뒤부터 각 학생 번호를 잘라 배열에 넣기
- 자른 번호가 배열에 이미 존재하면 넣지 않기
- 존재하지 않을 때만 배열에 넣기
- 배열의 길이가 N이면 각 학생들을 구분할 수 있으므로 반복문 종료
걸그룹 마스터 준석이(해시)
문제
정우는 소문난 걸그룹 덕후이다. 정우의 친구 준석이도 걸그룹을 좋아하지만 이름을 잘 외우지 못한다는 문제가 있었다. 정우는 친구를 위해 걸그룹 개인과 팀의 이름을 검색하여 외우게 하는 퀴즈 프로그램을 만들고자 한다.
입력
첫 번째 줄에는 총 입력 받을 걸그룹의 수 N(0 < N < 100)과 맞혀야 할 문제의 수 M(0 < M < 100)을 입력받는다.
두 번째 줄부터는 각 걸그룹마다 팀의 이름, 걸그룹의 인원 수, 멤버의 이름을 한 줄씩 차례대로 입력받는다. 팀과 멤버의 이름은 최대 100글자이며, 모든 글자는 알파벳 소문자이다. 하나의 걸그룹이나 서로 다른 두 걸그룹에 이름이 같은 두 멤버가 있는 경우는 없다.
그 다음 줄부터는 M개의 퀴즈를 입력받는다. 각각의 퀴즈는 두 줄로 이루어져 있으며, 팀의 이름이나 멤버의 이름이 첫 줄에 주어지고 퀴즈의 종류를 나타내는 0 또는 1이 두 번째 줄에 주어진다. 퀴즈의 종류가 0일 경우 팀의 이름이 주어지며, 1일 경우 멤버의 이름이 주어진다.
출력
첫 번째 줄부터 차례대로 퀴즈에 대한 답을 출력한다. 퀴즈의 종류가 0일 경우 해당 팀에 속한 멤버의 이름을 사전순으로 한 줄에 한 명씩 출력한다. 퀴즈의 종류가 1일 경우 해당 멤버가 속한 팀의 이름을 출력한다.
예제 입력
3 4
twice
9
jihyo
dahyeon
mina
momo
chaeyoung
jeongyeon
tzuyu
sana
nayeon
blackpink
4
jisu
lisa
rose
jenny
redvelvet
5
wendy
irene
seulgi
yeri
joy
sana
1
wendy
1
twice
0
rose
1예제 출력
twice
redvelvet
chaeyoung
dahyeon
jeongyeon
jihyo
mina
momo
nayeon
sana
tzuyu
blackpinkCode
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [N, M] = input[0].split(' ').map(Number); // N: 걸그룹 수, M: 문제 수
const girlGroup = new Map(); // 해시 알고리즘 사용을 위해 Map 이용
let index = 1;
let groupCnt = 1;
while (groupCnt <= N) {
const groupName = input[index];
const memberCnt = +input[index + 1];
let members = [];
for (let i = index + 2; i < index + 2 + memberCnt; i += 1) {
members.push(input[i]); // 멤버 이름 넣기
}
girlGroup.set(groupName, members.sort()); // [그룹명, 멤버리스트] 향테러 Map에 넣기
index += memberCnt + 2; // 다음 걸그룹 입력 값으로 이동
groupCnt += 1; // 저장해야할 그룹 수 카운트
}
let answer = '';
for (let quiz = index; quiz < index + M * 2; quiz += 2) {
const name = input[quiz];
const number = +input[quiz + 1];
// 퀴즈 0번
if (number === 0) {
// 해당 그룹 멤버들 answere에 넣기
girlGroup.get(name).map((n) => (answer += n + '\n'));
}
// 퀴즈 1번
else if (number === 1) {
// 각 그룹에 해당 멤버 이름이 존재하는 경우 그룹 이름 answer에 넣기
[...girlGroup.keys()].map((group) => {
if (girlGroup.get(group).includes(name)) answer += group + '\n';
});
}
}
answer = answer.trimEnd();
console.log(answer);
풀이 및 해설
- 구하고자 하는 것 = 걸그룹 퀴즈 프로그램
- 퀴즈 종류가 0일 때, 해당 팀에 속한
멤버 이름 사전순으로 출력 - 퀴즈 종류가 1일때, 해당 멤버가 속한
팀출력
- 퀴즈 종류가 0일 때, 해당 팀에 속한
- 해시 테이블 이용
{팀이름 : [멤버1, 멤버2, …]}이런 형태로 저장- 이때 멤버 이름 사전순으로 정렬해놓기
