1019: 숫자 바꿔치기

Link : judge.koreatech.ac.kr/problem.php?id=1019

---

1. 문제

• 손코딩뇌컴파일눈디버깅 회사의 직원 송영준(미남)은 프로그래밍 문제를 만들어서 판매하는 일을 하고 있다.
  똑똑한 영준이는 거래처 KUT의 김교수와 자신의 회사 사장 하모씨가 숫자에 둔감한 것을 알고는 단가를 조작해서 부당이익을 취하고는 한다.
  김교수와 하사장은 숫자 자릿수가 변하는 것은 기가 막히게 알아채지만, 자릿수가 같을 때는 두 숫자의 위치가 바뀌는 것은 잘 알아채지를 못한다. 이를 이용하여, 김교수에게는 단가를 크게 만들어서 많은 돈을 받고, 하사장에게는 단가를 작게 만들어서 적은 돈을 주고 남은 차액은 본인이 챙긴다.
  단가가 주어질 때 영준이의 부당이익을 계산하는 프로그램을 작성하라.

 

---

2. 문제의 조건

• 0 <= n <= 999999999 (9자리)
• 자리수가 같아야 한다.

 

---

3. 문제 접근

• 시간 복잡도
  
  시간제한 1초에 범위은 약 10억이지만 자리수가 9이므로 사실상 O(N^5)이내의 시간만 풀면 괜찮다고 생각하였습니다.
  
  
  
• 아이디어
  
  123이 주어졌을 때, 만들 수 있는 경우의 수는
  [1, 2, 3], [2, 1, 3], [3, 2, 1], [1, 3, 2]로 총 4가지입니다. [선택정렬 for와 같음]
  하지만 120이 주어졌을 때는
  [1, 2, 0], [2, 1, 0], [0, 2, 1], [1, 0, 2] 이지만 3번재의 0 2 1는 자리수가 바뀌므로 조건과 맞지 않습니다.
  이런식으로 모든 경우의 수들을 list에 넣고 정렬을 한다면
  O(N^2) + N long(N) = O(N^2)의 시간복잡도로 해결할 수 있게 됩니다.

 

---

4. 풀이 방법

• 각각 스왑가능한 모든 경우의 수를 계산한다.
• 맨 앞자리가 0이 아닌 경우에 list에 만든 number를 담아둔다.
• 정렬한다.
• 정렬 후 맨 끝 원소 - 첫번째 원소를 계산하면 답이된다.
  맨 끝 원소 = 만들 수 있는 최대값
  첫 번째 원소 = 만들 수 있는 최소값

 

---

5. 소스코드

• cjw-git.tistory.com/28

 

---

 

cjw.git@gmail.com