코딩테스트 준비 - 크면서 작은 수

혼자서 다시푸는 코딩테스트 준비 일지 - 68

백트래킹

25 days ago

5 min read

다시푸는 코딩 테스트 준비 일지

응시 사이트 : BOJ
문제 : 2992.크면서 작은 수
사용언어 : C#
난이도 : Easy - Middle
풀이시간 : 29m
유형 : 백트래킹

문제

정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다.

수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 같다. 하지만, 123과 432는 구성이 같지 않다.

입력

첫째 줄에 X가 주어진다. (1 ≤ X ≤ 999999) X는 0으로 시작하지 않는다.

출력

첫째 줄에 결과를 출력한다. 만약 그러한 숫자가 없는 경우에는 0을 출력한다.

예제 입력 1 복사

예제 출력 1 복사

예제 입력 2 복사

예제 출력 2 복사

예제 입력 3 복사

예제 출력 3 복사

문제 풀이 접근

이 문제를 보고나서, 가장 먼저 떠오른 접근 방법은 정수 X를 분해한 뒤에, 리스트에 넣고, 모두 구성이 같고, 초기 X 보다 클 경우, 현재 저장된 _ret 값 보다 작을 경우를 출력하는쪽으로 생각했다.

모든 내용이 문제에서 요구하는 요구 조건이라 당연한 얘기 일 수도 있으나, List를 사용함과 동시에 중복 제거를 하기위해 HashSet도 사용하는 약간의 최적화도 고려하였다.

바로 구상해서 빠르게 푸는 연습을 하다보니, 정리되어 있지도 않았고, 생각할 때, 중복수를 뽑는 처리라던가 더 최적화할 요소가 더 있었긴 했다.

그래서 당연히 효율성에서 걸려서 시간초과 뜰줄 알았는데, 통과했다.

이 문제의 플로우는
1. X의 수를 분해한다. %10, /10 을 사용하면서 분해한 뒤, List에 담는다.
2.거꾸로 담겨져 있기 때문에 Reverse를 한번 수행해준다.
3. 그 뒤 내 분해된 수를 조합 배열로 생각한 뒤 하나씩 뽑는 조합을 만들어 준다.
4. 중복을 배제한다. (HashSet에 담는다. )
5. 모든 순열에서 자릿수를 곱하면서 X보다 크며 순열중 가장 작은 값을 수로 만들어서 출력해준다.
6. 조건이 맞는게 골라지지 않았다면 0 을 출력한다.

작성 코드 (C#)

using System;
using System.Collections;
using System.Collections.Generic;
using System.Xml.Linq;
using static CodingTestProj.Program;
using System.Text;

///*
// * Difficulty : Easy ~ Middle
// * URL : https://www.acmicpc.net/problem/2992
//  * Time : 29m
// */

namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solu = new Solution();
            solu.solve();
        }
    }

    public class Solution
    {
        public int _n;
        public int _m;
        public int[] _arr;
        public bool[] _visit;
        public int _Count; // 자릿수

        public int[] _c;

        public List<int> _Lt_= new List<int>();
        public HashSet<int> _hs_ret = new HashSet<int>();

        public void solve()
        {
            _Count = 0;
            _n = int.Parse(Console.ReadLine());
            int _copyN = _n;

            while(true)
            {
                if (_copyN == 0)
                    break;

                int _val = _copyN % 10;
                _copyN /= 10;
                _Lt_.Add(_val);
                ++_Count;
            }

            _Lt_.Reverse();
            _c = new int[_Lt_.Count];
            _m = _Lt_.Count;

            BT(0, ref _c);

            List<int> _a = new List<int>();
            int _ret = 1000000;

            foreach(var pair in _hs_ret)
            {
                if(pair > _n)
                {
                    _a.Clear();

                    int _v = pair;
                    while (true)
                    {
                        if (_v == 0)
                            break;

                        int _val = _v % 10;
                        _v /= 10;
                        _a.Add(_val);
                    }

                    for(int i = 0; i < _Lt_.Count; ++i)
                    {
                        if (_a.Contains(_Lt_[i]) == true)
                        {
                            _a.Remove(_Lt_[i]);
                        }
                    }

                    if (_a.Count != 0)
                        continue;

                    if(_n < _ret && _ret > pair)
                    {
                        _ret = pair;
                    }
                }
            }

            _ret = _ret == 1000000 ? 0 : _ret;
            Console.WriteLine(_ret);
        }

        public void BT(int cnt, ref int[] _c)
        {
            if(cnt == _m)
            {
                int val = (int)Math.Pow(10, _Count-1);
                int _retVal = 0;

                for(int i = 0; i < cnt; ++i)
                {
                    _retVal += _c[i] * val;
                    val /= 10;
                }

                if(!_hs_ret.Contains(_retVal))
                    _hs_ret.Add(_retVal);
            }
            else
            {
                for(int i = 0; i < _Lt_.Count; ++i)
                {
                    _c[cnt] = _Lt_[i];
                    BT(cnt + 1, ref _c);
                }
            }
        }
    }
}

코드 결과