22.03.22. 풀었던 문제들

프로그래머스 lv.1

​

1. 직사각형 별찍기

기초문제

​

​

​

2. 체육복

이상한 데서 막혔던 문제.

2개 있는 사람이 나눠주는 걸 기준으로 생각하면 -> 방향에 따라 최적해가 나올 수도, 아닐 수도 있다.

->(03.23. 수정) 일반항을 기준으로 생각하면 그럴 수 있지만, 앞에서 바라보면 동일하다.

​

​

그래서 어려워 했는데 이렇게 생각하지 말고

​

0개 있는 사람이 빌린다고 생각하면 풀리는 것 같다.

탐색을 앞에서부터 진행할 거니까, 0인 사람이 앞사람에게 물어 봤을 때

0인 경우 -> 어차피 못빌려줌 -> 뒷사람에게 물어보면 된다.

1인 경우 -> 앞사람에게 줬을 수도 있다(이 경우에는 '앞 사람'이 앞으로 주나 뒤로 주나 최종값은 동일해진다)

처음부터 1개였을 수도 있고.

2인 경우 -> 앞사람에게 빌려오면 된다. 이렇게 결론지어지는 이유는 앞사람이 2인 경우는, 앞앞사람에게 줄 필요가 없었기 떄문이다. 만약 0인 사람의 뒷사람에게 빌리는 경우 그 뒤가 어떻게 될지 모르기 때문에 어지러워지는데, 앞사람에게 빌리는 경우 앞사람의 자원은 잉여자원이기 때문에 괜찮다.

​

즉, 탐색을 앞에서부터 진행하기 때문에 앞사람에게 먼저 물어보고,

없다면 뒷사람에게 빌려오면 된다.

​

(03.23. 수정)

근데 거꾸로 생각하면 앞에 있는 사람부터 scan하기 때문에 체육복이 2개인 사람을 검색해도 되는 것 아닌가? ... 맞는 것 같다.

괜히 애매하게 일반항을 생각해서 이상해졌다. 체육복이 2개인 사람이 먼저 앞사람에게 물어보고, 뒷사람에게 물어보면 해결된다.

앞사람이 0인 경우 -> 2인 사람은 먼저 앞으로 빌려주면 된다. 뒷사람이 0개라도 뒷사람에게 빌려줄 필요가 없는게, 그 뒷뒷사람이 가진 체육복 개수를 모르기도 하고, 뒷뒷사람이 1개든 2개든 0개든 상관없이 앞사람에게 주면 뒷사람 체육복 0개는 다른 사람이 해결해 줄 거다.

​

​

​

3. K번째 수

vector의 copy와 assign에 대해 알아보자.

​

​

​

4. 모의고사

풀다가 점호시간 되서 감.