๐ ํ๋ก๊ทธ๋๋จธ์ค / Greedy / Level 2 / ํฐ ์ ๋ง๋ค๊ธฐ
๐ ๋ฌธ์
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
๐ซ ์ ํ ์ฌํญ
- number๋ 2์๋ฆฌ ์ด์, 1,000,000์๋ฆฌ ์ดํ์ธ ์ซ์์ ๋๋ค.
- k๋ 1 ์ด์ number์ ์๋ฆฟ์ ๋ฏธ๋ง์ธ ์์ฐ์์ ๋๋ค.
๐ ์ ์ถ๋ ฅ ์
| number | k | return |
| "1924" | 2 | "94" |
| "1231234" | 3 | "3234" |
| "4177252841" | 4 | "775841" |
๐ค ํ์ด ๋ฐฉ๋ฒ
1๏ธโฃ ๋ฐฉ๋ฒ (1)
โ ์์ด๋์ด
/*
โก๏ธ ๋งจ ์ n ์๋ฆฌ๋ฅผ ์์์ผ๋ก ํด์ ํ๋์ฉ ๋น๊ตํ๋ฉฐ ๋๋ ค์ฃผ๊ธฐ
ex) 4177252841 -> [4, 1, 7, 7, 2, 5, 2, 8, 4, 1] / k = 4
(1) ์ด๊ธฐ ์ธํ
(10-4 = 6) : [4, 1, 7, 7, 2, 5]
(2) ์์์๋ถํฐ ๋น๊ต
(a) index 0 & 1 ๋น๊ต : 4 > 1 -> ๊ทธ๋๋ก
(b) index 1 & 2 ๋น๊ต : 1 < 7 -> ์์ผ๋ก ํ๋ ์์ผํจ
=> [4, 7, 7, 2, 5, 2]
(3) ์์์๋ถํฐ ๋น๊ต
(a) index 0 & 1 ๋น๊ต : 4 < 7 -> ์์ผ๋ก ํ๋ ์์ผํจ
=> [7, 7, 2, 5, 2, 8]
(4) ์์์๋ถํฐ ๋น๊ต
(a) index 0 & 1 ๋น๊ต : 7 = 7 -> ๋ค์ ๋น๊ต
(b) index 1 & 2 ๋น๊ต : 7 > 2 -> ๋ค์ ๋น๊ต
(c) index 2 & 3 ๋น๊ต : 2 < 5 -> ์์ผ๋ก ํ๋ ์์ผํจ
=> [7, 7, 5, 2, 8, 4]
(5) ์์์๋ถํฐ ๋น๊ต
(a) index 0 & 1 ๋น๊ต : 7 = 7 -> ๋ค์ ๋น๊ต
(b) index 1 & 2 ๋น๊ต : 7 > 2 -> ๋ค์ ๋น๊ต
(c) index 2 & 3 ๋น๊ต : 5 > 2 -> ๋ค์ ๋น๊ต
(d) index 3 & 4 ๋น๊ต : 2 < 8 -> ์์ผ๋ก ํ๋ ์์ผํจ
=> [7, 7, 5, 8, 4, 1]
*/
โก ์ฝ๋
class Solution {
public String solution(String number, int k) {
String answer = "";
// ๋ฐฐ์ด ์์ฑ ๋ฐ ์ด๊ธฐํ
int [] numArr = new int[number.length() - k];
for (int i=0; i<numArr.length; i++) {
numArr[i] = i;
}
// ์์์๋ถํฐ ํ์
while (true) {
if (numArr[numArr.length-1] ==number.length()-1) {
break;
}
for (int i=0; i<numArr.length-1; i++) {
char a = number.charAt(numArr[i]);
char b = number.charAt(numArr[i+1]);
if (a < b) {
for (int j=i; j<numArr.length-1; j++) {
numArr[j] = numArr[j+1];
}
numArr[numArr.length-1] = numArr[numArr.length-2] + 1;
break;
}
}
}
// ๋ฌธ์์ด ์กฐํฉ
for (int i=0; i<numArr.length; i++) {
answer += number.charAt(numArr[i]);
}
return answer;
}
}
โข ๊ฒฐ๊ณผ


โก๏ธ ๋ชจ๋ ์ผ์ด์ค์ ๋ถํฉํ ํ์ด ๋ฐฉ์์ ์๋์๋ค.
2๏ธโฃ ๋ฐฉ๋ฒ (2)
โ ์์ด๋์ด
โก๏ธ ์กฐํฉ์ ์ฌ์ฉ
โก ์ฝ๋
class Solution {
public static String[] numArr;
public static long max = 0;
public static String[] strArr;
public static boolean[] visited;
public static int k;
public String solution(String number, int k) {
// ์ชผ๊ฐ์ ๋ฐฐ์ด๋ก ๋ง๋ค๊ธฐ
numArr = number.split("");
// ๋ฐฐ์ด ์์ฑ
strArr = new String[number.length()-k];
visited = new boolean[number.length()];
k = k;
search(0, -1);
return String.valueOf(max);
}
public static void search(int cnt, int last) {
if (cnt == strArr.length) {
String tmp = "";
for (String s : strArr) {
tmp += s;
}
if (max < Long.valueOf(tmp)) {
max = Long.valueOf(tmp);
}
return;
}
for (int i=0; i<numArr.length; i++) {
if (!visited[i] && last < i) {
visited[i] = true;
strArr[cnt] = numArr[i];
search(cnt+1, i);
visited[i] = false;
}
}
}
}
โข ๊ฒฐ๊ณผ


โก๏ธ ์ฃผ์ด์ง ํ ์คํธ ์ผ์ด์ค๋ ๋ชจ๋ ํต๊ณผํ์ง๋ง ์ ํ์ฑ ํ ์คํธ์์ ๊ฑฐ์ ์คํจํ์๋ค. ๋ค๋ฅธ ์ผ์ด์ค๋ค์ ๋ฃ์ด๋ณด์๋ ๋ฌธ์ ๊ฐ ์๋๋ฐ ์ ์๋์๊ฐ๋์ง๋ ๋ชจ๋ฅด๊ฒ ๋ค.
3๏ธโฃ ๋ฐฉ๋ฒ (3)
โ ์์ด๋์ด
/*
โก๏ธ ์ฃผ์ด์ง ๊ธธ์ด์์ ๊ฐ์ฅ ํฐ ์๋ฅผ ๊ฐ์ง๋ ์ธ๋ฑ์ค๋ฅผ ํ์ธํ๋ฉด์ ๋ฒ์๋ฅผ ์ค์ฌ๋๊ฐ ์ธ๋ฑ์ค ๋ฐฐ์ด์ ํ๋ํ๋ค.
ex) "4177252841" / k = 4
(1) n-k ํฌ๊ธฐ์ ๋ฐฐ์ด ์์ฑ int[] idxArr = new int[number.length()-k]
(2) index 0 ๋ถํฐ +k(4) = 4 ๊น์ง ํ์ธ
417725(0) vs 177252(1) vs 772528(2) vs 725284(3) vs 252841(4)
โก๏ธ index 2 ์ผ ๋ ๊ฐ์ฅ ํผ => idxArr[0] = 2
(3) index 3 ๋ถํฐ +k'=k-2(2) = 5 ๊น์ง ํ์ธ
72528(3) vs 25284(4) vs 52841(5)
โก๏ธ index 3 ์ผ ๋ ๊ฐ์ฅ ํผ => idxArr[1] = 3
(4) index 4 ๋ถํฐ +k''=k'-0(2) = 6 ๊น์ง ํ์ธ
2528(4) vs 5284(5) vs 2841(6)
โก๏ธ index 5 ์ผ ๋ ๊ฐ์ฅ ํผ => idxArr[2] = 5
(5) index 6 ๋ถํฐ +k'''= k''-1(1) = 7 ๊น์ง ํ์ธ
284 (6) vs 841 (7)
โก๏ธ index 7 ์ผ ๋ ๊ฐ์ฅ ํผ => idxArr[3] = 7
(6) index 8 ๋ถํฐ +k'''' = k'''-1(0) = 8 ๊น์ง ํ์ธ
โก๏ธ ๋๋จธ์ง ๋ค ๋ค์ด๊ฐ์ผํจ => idxArr[4] = 8 / idxArr[5] = 9
*/
โก ์ฝ๋
class Solution {
public String solution(String number, int k) {
// ์ ๋ต ๋ฌธ์์ด
String answer = "";
// ๊ตฌํด์ผํ ๋ฌธ์์ด์ ๊ธธ์ด
int len = number.length() - k;
// ์์ ์ธ๋ฑ์ค
int idx = 0;
long max = 0;
int maxIdx = 0;
int count = len;
// ์ซ์๋ค์ ๋ค ๋บ ๋๊น์ง ๋ฐ๋ณต๋ฌธ ์ํ
while (k != 0) {
// ๋น๊ตํ์ฌ ์ต๊ณ ๊ฐ ์ฐพ๊ธฐ
for (int i=idx; i<=idx+k; i++) {
long comp = Long.valueOf(number.substring(i,i+count));
if (comp > max) {
max = comp;
maxIdx = i;
}
}
// ์ ๋ต ๋ฌธ์์ด์ ์ถ๊ฐ
answer += number.charAt(maxIdx);
// ๋ค์ ๋ฐ๋ณต๋ฌธ ๋ ์ค๋น
k = k-(maxIdx - idx);
idx = maxIdx + 1;
count--;
max = 0;
}
// ๋๋จธ์ง ์ฑ์ฐ๊ธฐ
int gap = len - answer.length();
for (int i=idx; i<idx+gap; i++) {
answer += number.charAt(i);
}
return answer;
}
}
โข ๊ฒฐ๊ณผ


โก๏ธ ๋ฐฉ๋ฒ (2) ์ ์ํฉ์ด ๋น์ทํ๋ค.