1/31기록 - 백준 1475

설 연휴 시작인 오늘 오전에는 전을 부치고 오후에는 알고리즘 문제를 하나 풀어보았다. 실버 5 라인에서 문득 눈에 띈 문제는 바로 백준 1475번 방 번호 문제였다.

 

 

문제는 이러하다. 총 0~9까지의 숫자 플라스틱으로 한 세트가 구성되고, 6,9의 경우에는 뒤집어서 하나로 퉁칠 수 있다. 입력받은 숫자를 만들 수 있는 최소 세트의 개수를 구하면 되는 문제이다.

 

알고리즘 생각

1. 숫자를 입력받는다. - 6,9를 문자열로 비교하기 위해 문자열 타입으로 입력받는다.

2. 0~9까지의 플라스틱 숫자 세트를 담은 배열 하나를 선언한다.

3. charAt() 메소드를 사용해서 숫자 하나하나를 문자열로 뜯어서 본다.

4. 9의 경우 6을 넣어주고 최종적으로 하나씩 올리면서 입력받은 숫자 개수만큼을 조사하기 위해 배열++해 준다.

5. 6과 9의 개수의 합이 짝수이면 6,9를 하나로 퉁칠 수 있으므로 나누기 2

6. 6과 9의 개수의 합이 홀수이면 6,9 하나 9 or 6이 하나 나와야 하므로 한 세트가 더 필요해서 나누기 2 + 1

7. 플라스틱 배열을 오름차순으로 정렬하고, 가장 큰 값을 출력하면 나올 수 있는 최종 세트 개수가 만들어짐

 

 

이 문제의 핵심은 6,9의 중복을 어떻게 처리할 것인가 이다. 합으로 보는 방법도 있지만, 이미 9에 6을 넣었기 때문에

arr[6] = arr[6]/2 + arr[6]%2로 처리할 수도 있다. 

 

마지막에 나는 오름차순 정렬 후 마지막 인덱스로 최댓값을 출력했지만, Math.max(max, index)로 max값을 출력하는 방법도 있다.

 

중복된 숫자의 경우 합으로 처리해서 나누기 개수를 하는 방법을 항상 생각하자!!!

 

1/31 기록 끝!!!!!!!!