[Programmers] 2차원 동전 뒤집기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/131703

프로그래머스

 

비트마스킹으로 풀 수 있는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 첨부하는 그림에서 볼 수 있다시피 beginning을 target으로 바꾸기 위해 뒤집을 열과 행을 정하는 것이 중요하지 뒤집는 순서는 중요하지 않습니다.

2. 열과 행의 길이가 각각 최대 10이기 때문에 모든 경우의 수를 구해도 O(2^20 * 20)입니다. 따라서 모든 경우의 수를 테스트한 뒤 답을 구할 수 있습니다.

[부연 설명]

2.1 0과 1로 이루어진 20자리 숫자를 통해 뒤집을 열과 행을 표시할 수 있습니다. 

2.2 앞에 10자리는 뒤집을 열을 의미하고 뒤에 10자리는 뒤집을 행이라고 정의했습니다.

2.3 예를 들어 비트가 10,010,001,000,010,010,001일 때 1, 4, 8번 열을 뒤집고 3, 6, 10번 행을 뒤집는다는 의미입니다.

2.4 여기까지가 2^20가지의 케이스였고 모든 자리가 1일 때 열과 행을 각각 10번씩 뒤집어야 하므로 시간 복잡도가 O(2^20 * 20)라고 생각했습니다.

3. 부연설명에서도 언급했듯이 2^20가지의 케이스를 비트마스킹을 통해 모두 순회하면서 1로 표시된 열과 행을 뒤집은 뒤 target과 동일한지 확인을 합니다. 모두 뒤집은 결과가 target과 동일하면 answer를 업데이트합니다.

4. 3번에서 구한 answer를 반환합니다.

 

 

 

개발환경: Programmers IDE

지적, 조언, 질문 환영합니다! 질문 남겨주세요~