프로그래머스 - 큰 수 만들기 (레벨2, swift)

문제 출처

programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기

 

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

제한 사항

    -  number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.

    -  k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

 

 

✨문제풀이

테스트 케이스 10 이거 하나가 시간초과로 통과가 안되서ㅜㅜ 시간이 엄청 많이 걸린 문제이다.

문제 해결 아이디어는 금방 떠올랐는데 시간 초과때문에 다른 방식으로 구현하는 것을 계속 고민해야 했다.

 

1) 먼저 만들어야 할 수의 자리수는 number.count - k로 구할 수 있다.

number.count - k 의 개수만큼 숫자를 뽑으면 되는데 여기서 주의할 점은 아래와 같다.

 

 - number에 있는 숫자들의 순서는 바꿀 수 없다.

 - 뽑힌 숫자의 앞 숫자들은 이 후에 뽑힐 수 없다

k만큼의 수가 제거되는 것이므로 number에 있는 숫자들의 위치는 변경되지 않는다.

또한 뽑힌 숫자의 앞에 있는 뽑히지 않은 숫자들은 그대로 버려지게 된다. 만약 '4177252841'에서 '7'이 뽑혔다면 그 앞에 있는 '41'은 그대로 버려지게 된다. 따라서 그 다음 수를 뽑을 때 버려지는 수들은 다시 탐색하지 않아도 된다.

 

 

2) 범위 내에서 가장 큰 수를 뽑으면 되는데 여기서 필요한 범위를 적절하게 지정하는 것이 중요하다. 범위를 지정하지 않고 그냥 큰 수를 뽑게되면 남은 수를 모두 뽑을 수 없게 될 수도 있다. 만약, '4177252841' 여기서 가장 큰 수인 8을 뽑게 되면 그 뒤에 '41'만 남게 되어 뽑아야할 수가 2자리가 넘게 될 경우 필요한 수를 모두 뽑을 수 없게 된다. 따라서 범위를 반드시 지정해주고 그 안에서 숫자를 뽑도록 해주어야 한다.

 

 [1] 뽑아야하는 수가 6자리이면 '4177252841' 중 뒤에서부터 5자리를 제외한 '41772'에서 가장 큰 수를 뽑아준다. -> 뽑힌 수 7

  이렇게 미리 마지막 5자리를 제외해두면 여기서 가장 큰 수를 뽑고 남은 숫자들이 없더라도 이후에 5자리를 추가할 수 있게 된다.

 [2] 뽑힌 수 '7' 앞에 있는 '41'은 버려주고 나머지 '7252841'에서 다음 수를 뽑아주면 된다. 5자리를 뽑아야 하므로 뒤에 4자리를 제외한 '725'에서 가장 큰 수인 '7'을 뽑아준다 -> 뽑힌 수 77

 [3] '252841'에서 다음 수를 뽑아준다. 4자리를 더 뽑아야 하므로 뒤에 3자리를 제외한 '252'중 가장 큰 수인 '5'를 뽑고 그 앞에 있는 '2'는 버려준다. -> 뽑힌 수 775

 [4] 똑같은 방식으로 '8'을 뽑아 준다. -> 뽑힌 수 7758

 [5] 만약 남아있는 숫자('41)'와 뽑아야 할 숫자(2자리)가 같다면 남은 수를 모두 뽑아주면 된다. -> 뽑힌 수 775841

 

 

 

첫번째 방법 1)

제일 먼저 구현한 방법은 string을 필요한 범위만큼 잘라내고 그 중 가장 큰 수를 뽑는 메소드(max())를 사용하였다. 또한 가장 큰 수의 index를 알아내서 뽑은 수와 그 앞의 숫자를 버려주어야 했기 때문에 firstIndex(:of) 메소드를 사용하였다. 이렇게 했을 때 테스크 케이스 8, 10이 시간초과로 통과되지 않는다.

 

 

두번째 방법 2)

그 다음으로 구현한 방법은 string을 잘라내지 않고 firstIndex와 endIndex를 저장하는 변수를 두어 탐색할 범위를 지정해주었다. 또한 max메소드를 사용하지 않고 직접 for문을 돌려 가장 큰 숫자를 찾도록 하였다. firstIndex(:of) 메소드도 효율성을 떨어뜨리는 거 같아 index변수를 따로 만들어 주고 for문이 돌아가는 동안 index 변수에 +1을 해주며 가장 큰 수의 index를 찾도록 해주었다. 이렇게 했을 때 테스트 케이스 10만 시간 초과로 통과되지 않았다.

 

세번째 방법 3) 

string을 배열로 만들어주고 두번째 방법과 똑같이 for문으로 가장 큰 숫자를 찾도록 해주었다. startIndex와 endIndex를 Int로 저장해주는 변수를 만들어 가장 큰 숫자는 해당 범위에서 찾도록 해주었고, startIndex와 endIndex가 같은 경우(뽑아야 하는 숫자와 남아있는 숫자가 같은 상황) 더이상 가장 큰 수를 찾지 않고 바로 남아있는 숫자들이 전부 뽑히도록 해주었다. 이렇게 했을 때 모든 테스트 케이스가 통과되었다. 다른 테스트들도 이전 방법들보다 효율성이 훨씬 좋아진 것을 볼 수 있다.

 

 

수정하고 또 수정해도 테스트 케이스 1,2개만 통과되지 않으니 문제를 왜 이렇게까지 하도록 만든걸까 그냥 포기할까 짜증이 조금 났었는데 막상 풀고 나니 꽤 도움이 많이 되었던 문제이다. 내가 간편하다고 생각했던 코드가 사실은 효율이 매우 떨어질 수도 있다는 걸 알았고 또 어떻게 하는 것이 더 효율적인 알고리즘이 될 수 있을 지 사소한 부분이라도 고민해봐야 겠다는 생각이 들었다. 

 

세번째 방법을 코드로 구현하면 아래와 같다.