[해시알고리즘] python - 위장

SEUNGJUN·2022년 2월 27일
0

위장

문제 이해

이번 문제는 2차원 배열로 주어진 리스트에서 [의상의 이름], [의상의 종류] 라는 식으로 주어진다면 이때 옷을 종류 별로 어떻게 입을수 있는가? 단 최소 한개의 의상은 입니다.
첫번째 예제를 확인해 본다면 "yellowhat", "headgear" / "bluesunglasses", "eyewear" / "green_turban", "headgear" 가 주어졌는데 이렇게 본다면 headgear가 두가지 eyewear가 한가지로 일단 한가지씩만 입는다고 가정하면 3가지 그다음에 이제 섞어서 입는다고 하면 eyewear에다가 headgear한가지씩 섞어서 2가지가 나오니깐 결과는 5가지가 나오게 된다.

문제 해결

처음에 문제를 풀때는 생각 했던게 일단 개별로 입을때 한가지씩 갯수를 구하고 그다음에 서로 다른 옷들의 갯수끼리 곱해서 나온 값과 더하면 구하려고 하는 값이 나올거라고 생각 했다. 그런데 여기서 예시 문제만 가지고 풀다보니깐 놓치는게 있었다. 예제에서는 두가지 종류일때 계산을 하다보니깐 저렇게 결과가 쉽게 결과를 해결할수 있었는데 만약에 의상의 종류가 2가지가 아니라 3가지 4가지라면 그렇게 되면 단순히 의상의 종류의 value 갯수끼리 곱하는게 아니라 2가지 입을때도 있고 3가지 입을때도 있고 4가지 입을때도 있는경우를 모두 구해줘야한다는 결과가 나왔다. 이렇게 생각 하니깐 너무 복잡해져서 문제를 다시 이해해 보려고 했다.

그러다가 드는생각이 결론적으로 의상을 입을수있는 모든상황을 구해보자 라는 것이였습니다. 이때 한가지 상황이 추가 되어야 하는데 예를들어 geadgear가 두가지 의상을 가지고 있다고 해볼때 두가지 모두 사용할 경우 + 두가지 모두를 사용하지 않을 경우 이 값을 추가해 주면 된다는 결론이 나오게 되었습니다.

일단 아까 value에 리스트값에 append를 해서 len을 따로 구할거 없이 그냥 의상의 갯수를 value값으로 구해주고 여기에서 의상의 갯수에다가 안입는 상황 1을 더해서 모두 곱해주고 난후 마지막에 -1을 해주면 된다고 생각이 들었습니다. -1을 해주는 이유는 headgear에도 안입는 상황이 걸리고 eyewear에도 안입는 상황이 생기면 그 두가지가 만나면 이 사람은 옷을 하나도 안입는 상황이 걸리기 때문에 그걸 피하는 방법이 -1을 해주면 된다고 생각했습니다.

결과

profile
RECORD DEVELOPER

0개의 댓글