Level 2
[3차] 파일명 정렬
이름 순으로 정렬된 파일 목록은 보기가 불편했다.
파일을 이름 순으로 정렬하면 나중에 만들어진 ver-10.zip이 ver-9.zip보다 먼저 표시되기 때문이다.
파일명은 크게 HEAD, NUMBER, TAIL의 세 부분으로 구성된다.
HEAD는 숫자가 아닌 문자로 이루어져 있으며, 최소한 한 글자 이상이다.
NUMBER는 한 글자에서 최대 다섯 글자 사이의 연속된 숫자로 이루어져 있으며, 앞쪽에 0이 올 수 있다.
0부터 99999 사이의 숫자로, 00000이나 0101 등도 가능하다.
TAIL은 그 나머지 부분으로, 여기에는 숫자가 다시 나타날 수도 있으며, 아무 글자도 없을 수 있다.
파일명은 우선 HEAD 부분을 기준으로 사전 순으로 정렬한다. 이때, 문자열 비교 시 대소문자 구분을 하지 않는다. MUZI와 muzi, MuZi는 정렬 시에 같은 순서로 취급된다.
파일명의 HEAD 부분이 대소문자 차이 외에는 같을 경우, NUMBER의 숫자 순으로 정렬한다. 9 < 10 < 0011 < 012 < 13 < 014 순으로 정렬된다.
숫자 앞의 0은 무시되며, 012와 12는 정렬 시에 같은 같은 값으로 처리된다.
두 파일의 HEAD 부분과, NUMBER의 숫자도 같을 경우, 원래 입력에 주어진 순서를 유지한다.
MUZI01.zip과 muzi1.png가 입력으로 들어오면, 정렬 후에도 입력 시 주어진 두 파일의 순서가 바뀌어서는 안 된다.
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function solution(files) {
// 각각의 입력 문자열을 head, num, tail로 나눕니다.
let arr = files.map((x) => {
let num = x.match(new RegExp("\\d{1,5}", ""))[0];
let headIndex = x.indexOf(num);
let tailIndex = headIndex + num.length;
let [head, tail] = [x.slice(0, headIndex), x.slice(tailIndex)];
return [head, num, tail];
});
arr.sort((a, b) => {
// localeCompare 메서드 활용
if (a[0].toLowerCase().localeCompare(b[0].toLowerCase()) == 0) {
// 숫자 앞 0 삭제
let numA = +a[1];
let numB = +b[1];
// 오름차순 정렬
return numA - numB;
} else {
let wordA = a[0].toLowerCase();
let wordB = b[0].toLowerCase();
return wordA.localeCompare(wordB);
}
});
return arr.map((x) => x.join(""));
}
2개 이하로 다른 비트
양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.
x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수를 return하는 solution을 작성하라.
풀이
- 입력 수를 이진 수로 변환합니다.
- 다음 수부터 이진 수로 변환한 후 둘 중 긴 값에 맞춰 적은 문자열 앞에 0을 추가해줍니다.
- 위치를 비교해 다르면 cnt를 올립니다.
- 2보다 작은 경우 answer에 담습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function solution(numbers) {
var answer = [];
for (let num of numbers) {
let numBit = num.toString(2);
let i = num + 1;
while (1) {
let curBit = i.toString(2);
let max = Math.max(numBit.length, curBit.length);
let A = [...numBit.padStart(max, "0")];
let B = [...curBit.padStart(max, "0")];
let cnt = 0;
for (let i = 0; i < A.length; i++) {
if (A[i] !== B[i]) cnt++;
if (cnt > 2) break;
}
if (cnt <= 2) break;
i++;
}
answer.push(i);
}
return answer;
}
=> 시간초과 발생
다른 풀이
- 짝수의 경우 마지막 비트가 항상 0 이므로 다음 수가 반환값입니다.
- 홀수의 경우 마지막 비트부터 0을 찾아 해당 값이 1이 될때가 해당 수 입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function solution(numbers) {
var answer = [];
for (let num of numbers) {
// 짝수이면 다음 수 push
if (num % 2 == 0) answer.push(num + 1);
else {
// 홀수이면 이진수로 변환
// 전부 1일 경우를 대비해 앞에 '0' 붙여주기
let str = "0" + num.toString(2);
// 변환된 이진수를 뒤에서부터 탐색할 index
let index = str.length - 1;
for (let i = 0; i <= index; i++) {
// 이진수를 뒤에서부터 탐색
if (str[index - i] == 0) {
// i 값은 0이 발견된 위치
// 1로 바꿔주고 2^i 더하기
// 이전 위치를 0으로 2^(i - 1) 뺴기
answer.push(num + 2 ** i - 2 ** (i - 1));
break;
}
}
}
}
return answer;
}
숫자 변환하기
자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.
- x에 n을 더합니다
- x에 2를 곱합니다.
- x에 3을 곱합니다.
자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요.
이때 x를 y로 만들 수 없다면 -1을 return 해주세요.
풀이
첫 시도 DFS로 풀어보기.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function solution(x, y, n) {
var answer = -1;
function DFS(result, L) {
if (result >= y) {
if (result == y) {
answer = answer == -1 ? L : Math.min(L, answer);
}
return;
}
DFS(result + n, L + 1);
DFS(result * 2, L + 1);
DFS(result * 3, L + 1);
}
DFS(x, 0);
return answer;
}
=> 시간초과
=> DFS로 시간초과 날 경우 DP로 풀어보기!
다른 풀이
=> DP 메모리제이션 활용해보자
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function solution(x, y, n) {
var answer = -1;
// dp 값을 저장할 배열
// 인덱스 값까지 최소 연산 수
let dp = new Array(y + 1).fill(-1);
// x값까지 온 연산 횟수는 0
dp[x] = 0;
for (let i = x; i <= y; i++) {
if (dp[i] == -1) continue;
// 시작 값인 x 에서 뻗어나감
if (i + n <= y) {
// x까지의 연산 + 1과 먼저 있던 값 비교, 최솟값 저장
dp[i + n] = dp[i + n] == -1 ? dp[i] + 1 : Math.min(dp[i] + 1, dp[i + n]);
}
if (i * 2 <= y) {
dp[i * 2] = dp[i * 2] == -1 ? dp[i] + 1 : Math.min(dp[i] + 1, dp[i * 2]);
}
if (i * 3 <= y) {
dp[i * 3] = dp[i * 3] == -1 ? dp[i] + 1 : Math.min(dp[i] + 1, dp[i * 3]);
}
}
return dp[y];
}