오늘은 프로그래머스 코딩테스트 연습에 있는 탐욕법 문제를 풀어보았다. 1레벨 단계의 문제이다보니 어렵지 않았지만, 탐욕법을 적용하여 풀려고하니 조금 꼬이는 부분이 생기긴 했다.
문제풀어보기
밑은 정답 코드이다. 탐욕법 문제이니만큼 매순간 최적의 선택을 하여야 하고, 처음 내가 문제를 풀었을 땐, flag기법으로 각 배열의 위치로 boolean 배열을 만들어 사용하였지만, 그렇게 되면, 가능은 하겠지만, 여벌의 옷이 있지만 받지 못하는 경우를 처리하기에 힘들어서 정수배열로 만들어 처리하였다. 만약 1,3이 lost에 들어잇고, 2,4가 reserve에 들어잇고 n이 5명 이상일 때, 처음 코드에서는 3번이 4번의 옷을 가져가게되면 2번이 옆의 옷이 없다는 것으로 가정하여 옷을 받지 못하는 경우가 생긴다. 이럴 경우를 위하여 위의 코드로 처리하였다.

오늘 배운 것 탐욕법은 매 순간 최선의 선택을 하여야하고 다른 것은 절대 신경쓰면 안된다. 그렇기 때문에, 최선의 선택이 전체적으로 봤을 때 올바른 선택이 되어야 한다. 문제를 풀 때 매순간이 최선의 선택인지 확인하고 혹시 빠진 것이 없는지를 주의하며 문제를 풀어나가야하겠다.