[TIL] 2021.12.10 코딩테스트 준비중 - 두번째 시험 : 크레인 인형뽑기 게임 / 그리디 알고리즘 / 면접 질문 대비

두번째 시험을 봤다

못 풀줄 알았지만 의외로 쉽게 풀었다!

오늘 시험은 아무것도 참고하지 않고 내 머리로 다 풀었다

게다가 한 시간만에 풀었다!! 원래는 3시간이 주어진다

 

https://programmers.co.kr/learn/courses/30/lessons/64061

코딩테스트 연습 - 크레인 인형뽑기 게임

 

 

문제를 읽고, 원리를 파악했다

내가 끄적인 내용이다

//4 3 1 1 3 2 0 4

//   0 1 2 3 4  y
//0 [0,0,0,0,0],
//1 [0,0,1,0,3],
//2 [0,2,5,0,1],
//3 [4,2,4,4,2],
//4 [3,5,1,3,1]
//x

//[1,5,3,5,1,2,1,4]
//1 : 4(3,0)
//5 : 3(1,4)
//3 : 1(1,2)
//...

이중포문을 최대한 안 쓰고 싶었지만 어쩔 수 없었다

이차원 배열이기 때문에 그 위치에 있는 원소를 찾으려면 이중포문을 쓸 수 밖에 없었다

moves를 가지고 해당 위치에 있는 원소를 가져오려면 어떻게 해야할까 를 생각했다

moves가 1이면 가장 왼쪽에 있는 세로줄에 있는 원소를 하나하나 확인해야 한다

즉, 

0
0
0
4
3

이 세로줄을 봐야 한다

이 세로줄은 board[0][0], board[1][0], board[2][0], board[3][0], board[4][0]를 하나하나씩 봐야한다

0	//board[0][0]
0	//board[1][0]
0	//board[2][0]
4	//board[3][0]
3	//board[4][0]

이렇게 된다

 

moves가 5이면, 가장 오른쪽에 있는 세로줄을 봐야한다

0
3
1
2
1

이 부분이다

이 부분도 이렇게 찾아야한다

0	//board[0][4]
3	//board[1][4]
1	//board[2][4]
2	//board[3][4]
1	//board[4][4]

이렇게 해서 moves를 가지고 각 원소(인형)를 가져오는 방법은 이것이다

for(int j=0; j<moves.length; j++) {
    for(int i=0; i<boardWidth; i++) {
        int doll = board[i][moves[j]-1];
    }
}

각 원소를 'board[i][moves[j]-1]' 로 가져와서 이 값이 0인지 아닌지 판단해야 한다

값이 0이면 아무 작업을 안 하고 건너뛰어야 하고

0이 아니면 스택에 값을 넣든 빼든 작업을 해줘야 한다 (다른 방법도 있겠지만 나의 풀이에는 스택이 쓰인다)

...
for(int j=0; j<moves.length; j++) {
    //count : board의 해당 열(세로줄)로 이동해서 작업을 한번 했으면 
    //작업을 그만하도록 제어하는 용도
    count = 0;
    for(int i=0; i<boardWidth; i++) {
        int doll = board[i][moves[j]-1];
        if(doll !=0 && count == 0) {
        ...

먼저 스택이 비어있는 지 확인한다

비어있지 않으면 가장 위에 있는 값을 peek해와 doll 값과 비교한다

값이 같으면 pop한다 

같은 인형이 만난다면 라스트팡? 아니 터뜨려야한다

터뜨리는 걸 스택에서 pop하는 걸로 대신한다

그리고 한번 터뜨렸으니 answer를 1 증가시킨다

count라는 변수를 썼는데, 쓴 이유는 현재 가리키고 있는 세로줄에서 스택에 넣든 빼든 작업을 한번 했으면

다른 세로줄로 이동해야 한다

하지만 이걸 어떻게 표현해줘야할 지 잘 몰랐다

그래서 그냥

'count변수를 써서 count가 0일 때 스택에 작업을 해주고 0이 아닐 때는 이미 작업을 끝낸거니까 건너뛰도록 하자'

라고 생각하여 사용한 것이다

...
if(!basket.empty()) {
    if(basket.peek() == doll) {
        basket.pop();
        answer++;
        count++;
        ...

인형을 스택에 쌓든 빼든 작업을 했으면 해당 세로줄에서 빼줘야 한다

...
board[i][moves[j]-1] = 0;
...

0으로 초기화해주면 된다

어차피 로직에서 'board[i][moves[j]-1]' 이것이 0이면 아무 작업을 안 하도록 되어있기 때문이다

위의 작업을 다 해줬으면 두번째 반복문에서 빠져나가야 한다

...
break;
...

스택이 비어있거나

스택에서 peek한 값과 doll값이 다르면

스택에 doll값을 push한다

그리고 스택에 작업을 해줬으니 count를 1 증가 시키고

인형이 있었던 위치를 0으로 만들어준다

...
basket.push(doll);
count++;
board[i][moves[j]-1] = 0;
...

마지막으로 answer * 2를 리턴한다

answer는 인형을 터뜨린 횟수를 센 값인데

인형을 한번 터뜨릴 때 2개가 같이 터지기 때문이다

return answer * 2;

---

내가 생각한 흐름을 끄적여봤는데

이해 못할 수도 있다..ㅎ

내가 짠 전체 코드를 봐서 혼자 분석해보거나 위에 적은 내용과 같이 보면 될 것 같다..

 

https://github.com/NayoungBae/oneday-onesolve/commit/41a56739f8b8cb538604a6ac92b96a03fa0f52fd?short_path=074dc2f#diff-074dc2ffd31dd818e19e39c4985836900a1a69eb9a636c675b3964aa4a9685f8 

Create Test) 크레인 인형뽑기 게임(2021-12-10).md · NayoungBae/oneday-onesolve@41a5673

---

아마 2년 전일 것이다

2년 전에도 이 문제를 본 적이 있다

그 때는 이 어려운걸 어떻게 푸나 하면서 구경만 했었던 기억이 있다

근데 지금은 온전히 내 힘으로 풀었다는 것에 뿌듯하기도 하면서

그때보단 나아지긴 했구나 성장하긴 했구나

라는 생각이 들었다

잘 하고 있는거겠지

---

chapter3은 '그리디 알고리즘, 브루트포스, 정수론 및 조합론'의 주제를 다룬다

그 중 '그리디 알고리즘'에 대한 문제를 풀었는데

?????? 그리디 알고리즘이 대체 뭔데 했다

 

그리디 알고리즘(Greedy Algorithm)

말 그대로 탐욕 알고리즘이다

'매 번의 선택에서 가장 좋아보이는 선택을 해 적절한 답을 찾아가는 것'이다

 

 

실생활에서 비유하자면

시험이 얼마 안 남았는데 공부해야 할 과목은 많다?

그럼 대부분의 사람들은 가장 효율적인 선택을 하기 위해

계획을 세운다

더 자세한 내용은 아래 글을 참고하면 될 것 같다

 

https://st-lab.tistory.com/143

[백준] 11047번 : 동전 0 - JAVA [자바]

https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕법(그리디) 알고리즘

---

Chapter3 : 정수론 및 조합론, 그리디 알고리즘, 브루트포스

- A) 잃어버린 괄호

https://github.com/NayoungBae/oneday-onesolve/commit/aa4f72ead8217d73bfc622f0bae0d019ea565588?short_path=be7a67c#diff-be7a67c1da98521a9078faec602208d26ab789bc7de15b3f72c16e32ee191258 

Update A) 잃어버린 괄호(2021-12-10).md · NayoungBae/oneday-onesolve@aa4f72e

 

- B) 동전 0

https://github.com/NayoungBae/oneday-onesolve/commit/6ccfcfd2624832a53df1ca643faae827118d566b?short_path=c83bec6#diff-c83bec6119b6ce35b98d1393fbf16ed0204c356e1f4c473ef7080a51ba692e71 

Create B) 동전 0(2021-12-10).md · NayoungBae/oneday-onesolve@6ccfcfd

 

---

면접 질문 대비

https://nazero.tistory.com/162

2021.12.10 면접 질문 준비 - Part 1. 전산 기초 자료구조