[1475] 방 번호

[1475] 방 번호

어떠한 사람(기능) 이 필요한가?

항상 설명이 너무 복잡하다면, 일단 문제를 단순화해서 보자. → 조건을 몇개 제거해보자.
(6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다는 조건을 제외해보자.)

만약, 122 라는 숫자를 만들어야 한다면, 플라스틱 세트는 2세트가 필요할 것이다
(2를 2개를 수급하려면, 플라스틱 세트 2세트가 필요할 것이고, 3~9까지 각각 숫자 2개씩은 모두 버려질 것이다. 아깝네)

만약, 9999라는 숫자를 만들어야 한다면, 플라스틱 세트는 4세트가 필요할 것이다.
(9를 4개를 수급하려면, 플라스틱 세트는 4세트가 필요할 것이고, 9를 제외한 나머지 숫자들 각 4개들은 모두 버려질 것이다.)

우리는 여기서, 다음과 같은 결과를 찾을 수 있다.
가장 많이 등장한 수의 "등장 횟수"만큼 플라스틱 세트가 필요하다!

그래서, 필요한 로직들을 몇개 찾을 수 있었다.

1. 각 자릿수의 정보를 파악하는 로직
2. 각 수의 등장 횟수를 기록하는 배열
3. 등장한 수들 중 최댓값을 찾는 로직

이제, 문제를 완성해보자.

추가 기능의 부여

6은 9를 대치할 수 있고, 9는 6을 대치할 수 있다.
그렇다는 것은, 일반성을 잃지 않고 6의 최댓값이 최대이더라도, 남은 9가 존재한다면, 해당 6을 9로 채워줄 수 있다는 것이다.

이는 등장 횟수의 기록을 모두 마친 뒤, 등장한 수들 중 최댓값을 찾는 로직 전에 수행되어야 할 것이다.
두 수를 더한 뒤(9), 2로 나눠서(4.5), 그만큼 양쪽에 균등 분배해주면 되는 것이다. (4, 5)

이대로 문제의 구현을 마쳐도 되지만, 문제에 숨어있는 재밌는 단서를 하나 찾아서 풀어보자.

우리가 구하고자 하는 것이 무엇이었지?

우리가 구하고자 하는 것은, 애초에 등장한 숫자들의 등장 횟수의 최댓값 이었다.
따라서, 최댓값을 제외하곤, 다 의미를 갖지 않는 정보가 되어버린다는 것이다.

해당 테크닉을 이용하고, "우리가 진정으로 구하고자 하는 것이 무엇이었는지" 를 파악하면, 문제를 좀 더 단순하게 풀 수 있다.

기존의 정수 분배 로직. 나머지가 발생할 경우, 임의로 한쪽에 등장횟수를 1회 추가시켜주는 로직이 추가되어야 한다.

 우리는 6과 9의 분배 작업 시, 나머지가 발생하면, 이를 적절하게 한쪽에 배분해야 하는 코드를 작성해야 했다.

하지만, 해당 계산 과정이 문제 결과에 어떠한 영향을 주는가를 생각해보면, 결국 큰 값만이 영향을 끼치고, 나머지 작은 값은 영향을 끼치지 않는다는 것을 파악할 수 있다.
따라서, 양쪽 다 큰 값으로 바꿔버려도 아무런 결과에 영향이 없다!

귀찮아서, 양쪽 다 5개로 지정했다.

항상 "진짜 내가 구하고자 하는 것이 무엇이었는지" 를 명심하는 것은, 가장 효율적인 해답을 도출해낸다는 것을 명심하자.

정답 코드 1: 단순화 이전

정답 코드 2: 단순화 이후