프로그래머스 2021 카카오커머스 챌린지

문제 설명

서버 n개가 있는 온라인 RPG 게임을 이용하는 한 유저가 각 서버에 새 캐릭터를 생성하려 합니다. 캐릭터 생성 규칙은 다음과 같습니다.

1. 각 서버에는 1부터 n까지 번호가 하나씩 붙어 있습니다.
2. 서버별로 캐릭터는 최대 5개까지 생성 가능합니다.
3. 캐릭터가 이미 5개인 서버에 새 캐릭터를 생성하면, 해당 서버에서 가장 오래된 캐릭터 하나를 삭제하고 빈자리에 캐릭터가 생성됩니다.
4. 해당 서버에 이미 같은 닉네임이 있는 경우 캐릭터가 생성되지 않습니다.
   4-1. 서로 다른 서버에는 닉네임이 같은 캐릭터를 만들 수 있습니다.

단, 다른 유저가 생성한 캐릭터들의 닉네임은 고려하지 않는다고 가정합니다.

서버 개수 n, 유저가 새 캐릭터를 생성한 기록이 담긴 배열 record가 매개변수로 주어집니다. 이때, 각 서버별로 어떤 캐릭터들이 생성됐는지 닉네임을 문자열 배열 형태로 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 1 이상 9 이하인 자연수입니다.
• record는 캐릭터의 생성 기록이 시간 순서대로 담긴 문자열 배열입니다.
• record의 길이(=캐릭터 생성 기록 개수)는 1 이상 1,000 이하입니다.
• record의 각 원소는 캐릭터 생성 기록을 나타냅니다.
  • 캐릭터 생성 기록은 N nickname 형태입니다.
  • N은 서버 번호를 나타내며 n(서버 개수) 이하인 한 자리 자연수입니다.
  • nickname은 해당 서버에 생성한 캐릭터의 닉네임을 나타냅니다.
  • N과 nickname은 공백(스페이스) 하나로 구분되어 있습니다.
  • 닉네임의 길이는 1 이상 6 이하이며 알파벳 소문자로만 이루어져 있습니다.
• return 하는 문자열 배열은 서버별 닉네임을 다음 기준에 따라 정렬해 return 해주세요.
  • 번호가 더 작은 서버에 있는 닉네임이 더 앞에 옵니다.
  • 서버 번호가 같을 경우 해당 서버에서 더 오래된 닉네임이 더 앞에 옵니다.
  • 캐릭터가 하나도 생성되지 않은 서버는 무시해도 됩니다.

---

입출력 예

nrecordresult

1	["1 fracta", "1 sina","1 hana","1 robel","1 abc", "1 sina", "1 lynn"]	["sina", "hana", "robel", "abc", "lynn"]
4	["1 a","1 b","1 abc","3 b","3 a","1 abcd","1 abc","1 aaa","1 a","1 z","1 q", "3 k", "3 q", "3 z", "3 m", "3 b"]	["abc", "abcd", "aaa", "z", "q", "k", "q", "z", "m", "b"]

입출력 예 설명

입출력 예 #1

1번 서버에 다음과 같이 캐릭터가 생성됩니다.

record1번 서버설명

1 fracta	[fracta]	1번 서버에 fracta를 생성합니다.
1 sina	[fracta, sina]	1번 서버에 sina를 생성합니다.
1 hana	[fracta, sina, hana]	1번 서버에 hana를 생성합니다.
1 robel	[fracta, sina, hana, robel]	1번 서버에 robel을 생성합니다.
1 abc	[fracta, sina, hana, robel, abc]	1번 서버에 abc를 생성합니다.
1 sina	[fracta, sina, hana, robel, abc]	1번 서버에 이미 sina가 있으므로 무시합니다.
1 lynn	[sina, hana, robel, abc, lynn]	1번 서버에서 가장 오래된 닉네임 fracta를 삭제하고 새 닉네임 lynn을 생성합니다.

입출력 예 #2

캐릭터 생성 기록을 모두 처리한 후 각 서버별 닉네임 상태는 다음과 같습니다.

1번 서버2번 서버3번 서버4번 서버

[abc, abcd, aaa, z, q]

없음

[k, q, z, m, b]

없음

2번과 4번 서버에는 캐릭터가 하나도 없습니다. 따라서, 1번, 3번 서버에 생성된 캐릭터만 조건에 맞게 배열에 담아 return 하면 됩니다.

• solution.js

 

 

 

 

 

실행 결과

실행 결과가 여기에 표시됩니다.

테스트 케이스 추가하기

채점 기록코드 초기화

코드 실행

제출 후 채점하기

종료까지

 

 

function solution(n, record) {
	var answer = [];
	const servers = Array.from({length: n+1}, ()=>[]);
	for(const info of record){
		let [serverNum, nickName] = info.split(' ');
		serverNum=parseInt(serverNum, 10);
		if(servers[serverNum].includes(nickName)) continue;
		servers[serverNum].push(nickName);
		if(servers[serverNum].length > 5) servers[serverNum].shift();
	}
	for(const server of servers){
		if(server.length===0) continue;
		answer.push(...server);
	}
    return answer;
}

 

 

문제 설명

미니 테트리스는 테트리스와 유사한 게임으로, 규칙이 약간 다릅니다. 이 게임에서 등장하는 모든 블록은 높이가 1인 가로 일자형 블록이며, 회전할 수 없습니다. 블록은 위에서부터 아래로 내려오며 보드 공간의 가장 낮은 층부터 쌓입니다. 주어진 블록을 모두 쌓았을 때 그 높이를 최대한 낮추는 것이 게임의 목표입니다. 단, 미니 테트리스는 보드 공간의 한층이 블록으로 꽉 차더라도 그 층을 지우지는 않습니다.

당신은 게임에서 승리하기 위해 다음과 같은 간단한 알고리즘을 사용합니다.

• 보드 공간의 가장 낮은 층의 왼쪽부터 블록을 쌓습니다.
• 내려오는 블록의 길이보다 보드 공간의 어떤 층 오른쪽에 남은 공간이 더 작아서 통과할 수 없다면, 그 층위에 블록을 쌓습니다.

보드의 가로길이 m과 내려올 블록의 길이가 순서대로 들어 있는 배열 v가 매개변수로 주어집니다. 위의 알고리즘을 따라 블록을 쌓았을 때, 쌓인 블록의 층 수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

• m은 1 이상 1,000 이하인 자연수입니다.
• 배열 v의 길이는 1 이상 100,000 이하입니다.
• 배열 v의 원소는 1 이상 m 이하인 자연수입니다.

입출력 예

mvresult

4	[2,3,1]	2
4	[3,2,3,1]	3

입출력 예 설명

입출력 예 #1
보드의 가로길이가 4이고, 길이가 2, 3, 1인 블록이 차례로 내려옵니다. 첫 번째 블록은 1층에 쌓입니다(가장 낮은 층이 1층입니다). 두 번째 블록은 길이가 3이고 1층의 남은 공간이 2이기 때문에 1층에 쌓이지 못하고 2층에 쌓입니다. 세 번째 블록은 길이가 1이기 때문에 2층을 통과하고 1층으로 내려가서 왼쪽으로 이동합니다.
아래 그림은 블록을 쌓는 과정을 나타냅니다.

총 2개 층이 쌓였기 때문에 2를 return 합니다.

입출력 예 #2
보드의 가로길이가 4이고, 길이가 3, 2, 3, 1인 블록이 차례로 내려옵니다. 첫 번째 블록이 1층에 쌓입니다. 두 번째 블록은 길이가 2이고 1층의 남은 공간이 1이기 때문에 1층에 쌓이지 못하고 2층에 쌓입니다. 세 번째 블록은 길이가 3이기 때문에 2층을 통과하지 못하고 3층에 쌓입니다. 네 번째 블록은 길이가 1이므로 3층과 2층을 통과하여 1층에 쌓입니다. 1층이 꽉 찼지만, 블록을 지우지 않습니다.
아래 그림은 블록을 쌓는 과정을 나타냅니다.

총 3개 층이 쌓였기 때문에 3을 return 합니다.

 

 

function solution(m, v) {
	var answer = 0;
	const boardInfo = Array.from({ length: 1000000+1 }, () => m);
    let highestFloor = 1;
	for (const blockSize of v) {
        let availableFloor = highestFloor;
        
		while(availableFloor>0 && boardInfo[availableFloor]>=blockSize){
            availableFloor--;
        }
        // console.log(`${blockSize}를 ${availableFloor}층에서 뻄`)
        boardInfo[availableFloor+1] -= blockSize;
        highestFloor++;
	}
    
    
    // console.log(boardInfo)
	answer = boardInfo.filter((info) => info !== m && info>=0).length;
	return answer;
}

 

 

문제 설명

중학교 영어교사인 현미는 방학동안 영단어 암기 카드를 만들어서 학생들에게 돌려 보면서 익히도록 하려 합니다. 각 학생들은 한 장씩 영단어 카드를 만들어 1번 학생은 자신이 만든 카드를 2번 학생에게, 2번 학생은 자신이 만든 카드를 3번 학생에게, 즉 모든 학생들이 자신의 다음 번호의 학생에게 카드를 전달했습니다. 마지막 번호인 학생은 자신이 만든 카드를 1번 학생에게 전달했습니다. 그 후에는 이 카드에 적힌 단어를 암기하고 나서 또 같은 방식으로 카드를 전달했고, 한 바퀴를 모두 돌아 이미 자신이 암기한 카드가 돌아오면 전달을 종료했습니다.

이렇게 했더니, 모든 학생이 모든 카드를 회람할 수 있다는 점은 좋았지만, 집이 멀다든지 앞뒤 번호 학생과 잘 만나지 않는 경우가 있다든지 해서 카드들이 한 바퀴 회람되는 데 걸리는 시간이 너무 길었습니다. 그래서 이번 학기에 현미는 아이디어 하나를 제시했습니다. 모든 학생들이 자신이 이번에 암기한 카드를 다음 번에 전달해 주고 싶은 학생을 한 명씩 지정하여, 다음 번호의 학생이 아니라 자신이 지정한 학생에게 카드를 전달하기로 한 것입니다. 단,카드를 전달하고 싶은 학생이 없다면 자신에게 돌아온 카드에 적힌 단어를 암기한 후 카드를 버리기로 했습니다. 또, 이미 한번 암기한 카드가 자신에게 다시 돌아오면 그 카드도 버리기로 했습니다.

예를 들어, 열 세 명의 학생으로 이루어진 학급에서 각 학생이 자신이 카드를 전달하고 싶은 학생을 지정한 표가 아래와 같다고 가정하겠습니다. 학생들은 모두 번호로만 표시합니다. 아무에게도 카드를 전달하지 않을 학생은 0 이 표기되어 있습니다.

학생 번호전달할 학생 번호

1	5
2	9
3	13
4	1
5	0
6	0
7	11
8	1
9	7
10	12
11	9
12	9
13	2

이러한 새로운 규칙을 적용했더니, 카드가 전달되는 데 걸리는 시간을 줄일 수는 있었습니다. 그러나, 모처럼 학생들이 만든 카드들을 모든 학생들이 회람할 수 있도록 할 수는 없었습니다. 예를 들어 위 표에 따라 카드를 전달하는 과정을 그림으로 표시하면 다음과 같습니다.

학생들의 번호를 동그라미 안에 적어 표시하였고, 동그라미들 사이에 그어진 화살표는 카드의 전달 경로를 나타냅니다. 각 학생이 만든 카드가 자신을 포함하여 몇 명에게 전달되어 영단어 암기에 활용될 수 있었는지를 동그라미 주위에 붉은 숫자로 표시했습니다.

각 학생이 만든 카드가 가능한 많은 학생들에게 회람되도록 하고 싶었던 현미는 한 가지 아이디어를 냈습니다. 가장 많은 학생들에게 회람된 카드를 작성한 학생에게 상을 주겠다는 것입니다. 위 예에서는 3번 학생이 작성한 카드가 (3번 학생 본인을 포함하여) 여섯 명에게 회람되어 가장 높은 횟수를 기록했습니다.

각 학생이 자신이 만든 또는 받은 카드를 전달할 다음 학생의 번호가 담긴 배열 next_student가 매개변수로 주어질 때, 몇 번 학생이 만든 카드가 가장 많은 학생들에게 회람될지 return 하도록 solution 함수를 완성해주세요. 만약, 가장 많은 학생들에게 회람되는 카드가 두 장 이상이라면, 그 중 큰 번호를 가진 학생이 작성한 카드를 선택합니다.

제한사항

• next_student는 각 학생이 카드를 전달할 다른 학생의 번호를 나열한 배열입니다.
  • 학생 수가 n명이라면, 학생들에게는 1번부터 n번까지 번호가 매겨져 있습니다.
  • next_student의 k번째 원소는 k번 학생이 카드를 전달할 다른 학생의 번호입니다.
• next_student의 길이는 1 이상 1,000,000 이하입니다.
  • next_student의 길이가 n 일때, 학생 수는 n 명입니다.
  • next_student의 원소는 0 이상 (next_student 의 길이) 이하인 정수입니다.
  • next_student의 k 번째 원소가 k인 경우 (자기 자신을 다른 학생으로 지목한 경우)는 없습니다.
  • 원소가 0인 경우 그 학생은 자신이 만든카드와 받은 카드 모두 다른 학생에게 전달하지 않습니다.

입출력 예

next_studentanswer

[5, 9, 13, 1, 0, 0, 11, 1, 7, 12, 9, 9, 2]	3
[6, 10, 8, 5, 8, 10, 5, 1, 6, 7]	9

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

다음 그림과 같은 방식으로 영단어 암기 카드가 전달됩니다. 각 학생이 작성한 카드를 회람하게 되는 학생들의 수를 붉은 색으로 표시했습니다.

이 예에서는 1, 5, 6, 7, 8, 10 번 학생의 카드는 각각 여섯 명씩에게 회람되며, 나머지 학생들인 2, 3, 4, 9 번 학생의 카드는 각각 일곱 명씩에게 회람됩니다. 일곱 명씩에게 회람되는 (가장 많은 학생들이 암기하게 되는) 카드를 작성한 학생들 중 가장 큰 번호를 가진 학생은 9 번입니다.

 

function solution(next_student) {
	var answer = 0;
	let maxCount = 0;
	next_student.unshift(-1);
	const studentLength = next_student.length;
	const dp = Array.from({ length: studentLength + 1 }, () => 0);
	const dfs = (visited, currStudent, currCount) => {
		// console.log(`curr: ${currStudent}`)
		if (next_student[currStudent] === 0 || visited[next_student[currStudent]])
			return currCount;

		visited[next_student[currStudent]] = 1;
		// console.log(`next: ${next_student[currStudent]}`)
		if (dp[next_student[currStudent]] > 0) return dp[currStudent]+dp[next_student[currStudent]];
		return dfs(visited, next_student[currStudent], currCount + 1);
	};

	for (let student = 1; student < studentLength + 1; student++) {
		// console.log(`**start: ${student}`)
		if (dp[student] > 0) continue;
		if (next_student[student] === 0) continue;
		const visited = Array.from({ length: studentLength + 1 }, () => 0);
		visited[student] = 1;
		const count = dfs(visited, student, 0);

		dp[student] = Math.max(dp[student], count);
	}

	console.log(dp);
	let [maxValue, maxIndex] = [-1, -1];
	dp.forEach((v, i) => {
		if (maxValue <= v) {
			maxValue = v;
			maxIndex = i;
		}
	});
	answer = maxIndex;
	return answer;
}

console.log(solution([5, 9, 13, 1, 0, 0, 11, 1, 7, 12, 9, 9, 2]));

 

 

100

100

63점