[c++] 코딩인터뷰 완전분석 - 배열과 문자열 7

문제

M x N 행렬을 순회하면서 0인 원소를 발견하면, 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성하라.

 

풀이

1. 비트 벡터 사용

배열을 순회하면서 0이 들어간 행과 열을 각각 정수형 변수에 비트로 위치를 기록해두고 이를 바탕으로 배열의 값을 바꿔주면 됩니다.

 

2. 배열의 첫 번째 행과 첫 번째 열을 기록용 배열로 사용

첫 번째 행과 첫 번째 열에 0이 포함되어있는지를 기록하는 boolean형 변수 두 개에 각각 기록해두고

첫 번째 행과 열을 제외한 나머지 위치를 순회하면서 0의 위치를 첫 번째 행과 첫 번째 열에 기록해둡니다.

 

기록해둔 첫 번째 행과 열을 참고하여 나머지 배열의 0이 들어가는 위치를 모두 바꿔주고

앞에서 기록해둔 boolean형 변수를 참고하여 첫 번째 행과 첫 번째 열을 0으로 바꿔주면 됩니다.

 

 

구현 코드