1971 - 소트

문제

• https://www.acmicpc.net/problem/1071

풀이

• 경우의 수를 생각해보면 그리디적으로 해결 할 수 있다.
• 중복된 수들을 없애고 유니크한 수들을 정렬한 상태에서 시작한다.

수가 1개일 경우

• 해당 원소가 가지고 있는 개수만큼 원소를 출력
• break

수가 2개일 경우

• 현재 수 + 1 == 다음 수

  • 다음 수를 먼저 출력하고 난 다음 현재 수를 출력

• 현재 원소 + 1 != 다음 원소

  • 현재 수를 먼저 출력하고 난 다음 다음 수를 출력

• break

수가 3개이상일 경우

• 현재, 다음, 다음다음 수에서 가능한 경우

  • 현재 원소 + 1 != 다음 원소

    • 현재 원소를 출력하고 난 다음 continue

  • 현재 원소 + 1 == 다음 원소

    • 현재 원소를 출력하고 난 다음 다음다음 수를 1개 출력하고 continue

느낀점

• 가장 작은 수를 우선적으로 배치할 수 있도록 구현할 수 있어서 위의 규칙을 기반으로 로직을 구현하면 해결할 수 있다.

• 다음다음 수를 1개 출력하고, 만약 다음다음 수가 없다면 없애줘야한다.

• 분류

  • 구현, 그리디

• 다른 분들의 풀이를 보니 위의 규칙을 간단하게 만들어서 해결한 것 같다.