백준 Swift 알고리즘, 감소하는수 1038 큐 문제풀이

 

 

 

안녕하세요. 저는 iOS Developer, 멍구입니다. 🤗
오늘은 백준의 알고리즘 문제, 감소하는 수 1038 문제를 스위프트 언어로 풀어보도록 하겠습니다. 바로 시작하겠습니다!

 

 

---

백준 알고리즘 감소하는수 1038

감소하는 수 1038 문제 풀기 시작

감소하는 수_1038 문제는 solved.ac 기준 골드5의 티어를 갖고 있습니다. 정답 비율은 30%입니다. 이어서 문제에 대한 설명을 보도록 하겠습니다. 

 

 

해당 문제는 N번째 감소하는수를 구하는 문제입니다. 여기서 감소하는 수란, 가장 큰 자릿수부터 가장 작은 자릿수까지 감소하는 수입니다.

예를들면, 0은 0번째 감소하는 수, 1은 1번째 감소하는 수입니다. 2은 2번째 감소하는 수 겠죠. 감소하는 수는 가장 큰 자리수부터 가장 작은 자리수까지 가면서 감소하는 수여야 합니다.

322는 3 > 2 >= 2 로 끝에서 감소하지 않습니다. 9 > 5 < 8 은 마지막에 5에서 8로 증가했습니다. 이 또한 감소하는 수가 아니죠. 3 > 2 >1 은 계속 감소하였기에 감소하는 수입니다. 만약 N번째 감소하는 수가 없다면 -1을 출력해야합니다.

해당 문제는 어떻게 접근하여 풀 수 있을까요? 🤔
이어서 입력 / 출력 방식을 보도록 하겠습니다. 

 

 

N은 1,000,000이며, 작거나 같은 자연수 또는 0 이라고 합니다. 이후 출력은 N번째 감소하는 수를 출력합니다. 
예를 들면 N == 18 이라면, 18번째 감소하는 수, 42를 출력하면 됩니다.

해당 문제는 다양한 접근방법이 있겠지만, 그중에서 저는 큐를 활용해서 풀어보겠습니다. 해당 문제를 어떻게 큐의 방식으로 접근할 수 있을까요? 이어서 바로 Swift를 사용해서 풀이 가보도록 하겠습니다. 👨🏻‍💻

 

 

---

감소하는 수 알고리즘 문제 Swift 풀이

먼저 N번째 감소하는 수를 구하기 전 입력을 받고 준비를 하겠습니다.
- N : Int로 값을 받았습니다. N번째 감소하는 수를 구하는데 사용 됩니다.
- cnt : 현재 구한 감소하는 수가 몇번째 감소하는 수인지를 확인하기 위해 사용합니다. 
- Q : 그자체가 큐로서 사용됩니다. 큐의 pop위치를 의미하는 커서를 사용해서 배열을 큐로서 사용할 것입니다.
  - 여기서 (1...9)는 1 ~ 9 번째 감소하는 수를 미리 저장해 둔 것입니다. 
- cur : 위의 Q 배열의 pop 위치를 기억할 변수입니다. 

이어서 감소하는 수를 구하는 메서드를 보겠습니다.

 

 

check 메서드는 N번째 감소하는 수를 구하는 메서드입니다. 각 라인 별 해설을 해보겠습니다.

- if N == 0 { return 0 } : N이 0이면 0번째 감소하는 수, 0을 그대로 리턴하고 종료합니다.
- cur < Q.count : Q에 값이 존재하는지 유무를 확인하는 조건입니다.
  - cur가 Q.count보다 작다는 것은 아직 Q에 값이 존재함을 의미합니다. 
- let now = Q[cur] : now에 상수로 Q[cur] 값을 가져옵니다. 이는 큐의 front 값을 가져오는 것입니다. 즉, 현재 탐색 중인 감소하는 수를 받아오는 작업입니다.
- let last = now % 10 : last는 현재 얻은 감소하는 수, now의 끝 자리 수를 저장합니다. 해당 값은 이후의 감소하는 수를 구해서 큐에 누적할 때 사용 됩니다.
- cur += 1 : 해당 동작은 Q 큐의 pop() 동작과 같습니다.
- N == cnt : 현재 순회한 감소하는 수가 N번째 감소하는 수인지 확인하고 그렇다면 현재의 감소하는 수를 반환합니다. 
- now == 9876543210 { return -1 } : 9876543210보다 큰 감소하는 수는 존재하지 않습니다. -1를 반환합니다. 

★ 이후 for문이 핵심 부분입니다.
-> 현재 순회중인 감소하는 수의 가장 작은 자리수 이전까지의 한자리 수를 현재 감소하는 수 뒤에 붙여서 큐에 넣습니다. 이는 초기 값 기준으로 보자면 1 ~ 9의 값이 탐색 된 후의 추가적으로 먼저 탐색되어야 하는 감소하는 수를 큐에 미리 넣어주는 작업이 됩니다.

예를들면, 맨 처음에는 1에 대해서 10이, 2에 대해서 20 / 21이, 3에 대해서 30 / 31 / 32가 큐에 들어갑니다. 이렇게 감소하는 수에 대해서 차근하근 순회하며 N번째 감소하는 수를 구할때까지 연산합니다. 최종적으로 N번째 감소하는 수를 구할 수 있게 됩니다. 

이렇게 check() 메서드의 연산이 끝났습니다. 그럼 이제 해줘야할 것은 단 하나, 해당 반환값을 출력해주는 것입니다. 😊

 

 

이렇게 N번째 감소하는 수를 출력하고 문제를 해결할 수 있게 됩니다.

 

 

---

이렇게 오늘은 백준의 감소하는수 알고리즘 문제를 스위프트 언어로 풀어봤습니다.
최종적으로 위와 같이 큐의 원리를 활용해서 해당 문제를 풀 수 있었습니다. 다양한 문제 풀이 및 의견 등 환영합니다. 즐거운 하루 되세요 ~ 🥰