💫 오늘의 목표
1. PS 2문제 이상 풀기
앞으로 PS는 기출문제 모음에서 풀어보려고 한다!
1) 가장 많이 받은 선물
30분 내에 끝내고 싶었는데 33분 정도 걸렸다
그런데 이게 과연 Lv1이 맞는지..
선물을 주고 받고, 이름과 이름으로 주어진다는 점에서
Map<이름, 인덱스 번호>를 선언해서 바로 꺼낼 수 있도록 하고 그 인덱스로 그래프를 표현하면 될 듯 싶었음
그런데 인접리스트에 익숙해져있는 터라 당연히 인접리스트로 구현해야지 했는데
어떻게 A가 보낸 선물의 수, A가 받은 선물의 수를 쉽게 구할 수 있을지 막막했다
자료형을 더 가져오기엔 나조차도 로직을 잊을 것 같아서... 실제로 풀다가 잊었음
그래서 문제에서 보여준 풀이를 봤는데 인접행렬로 표현했음
그래서 받은 개수와 준 개수를 같이 저장하면 될 것 같았다
이걸 그려놓고 했다면 좀 더 명확했을까..
그래서
1. `Map` 자료형에 `<이름, 인덱스>` 세팅
2. 서로 주고받은 선물의 수를 인접행렬에 저장
3. 각각 최댓값과 최솟값을 저장
4. 인접행렬을 보면서 누가 많이 받았는지를 보고 받을 선물의 수를 저장한다.
4-1. 같은 양을 받았다면 저장한 최대/최솟값으로 선물지수를 계산해 받을 선물의 수를 저장한다.
5. 전체를 보면서 최댓값을 저장하고 리턴로직으로 작성했다.
다음 달에 선물을 받을 친구들 중 최댓값을 출력해야하는데, 이를 제대로 못보고 이번 달 선물의 수를 합해서 한번 틀렸음. 그걸 고치니 solved를 얻긴했다
또한.. 아쉬웠던 점은 주석으로 로직을 구체화한 뒤 코드로 구현한 것이 아니라 반대로 했다는 점이다. 게다가 시간복잡도도 따로 생각하지 않았음.
2) 도넛과 막대 그래프
1시간이 지나도 결국 풀지 못했다.
문제를 풀다가 간과했던 부분은
이 두가지 경우이다.
내가 판단했던 부분은
도넛 : 처음으로 돌아오고 나가는 간선은 1개
막대 : 처음으로 못오고 나가는 간선은 0~1개
8자 : 처음으로 돌아오고 나가는 간선은 1~2개
즉, 나가는 간선이 2개가 있다면 8자로 return
나가는 간선이 0개가 있다면 막대로 return
나머지는 도넛이었는데,
1번 그림에서 ?노드에서 방문처리 후 위쪽 루트로 먼저 ?로 왔을 때 간선이 2개로 갈라지지 않아서 아직 8자임을 모른다.
또한, 밑의 루트로 갔던 노드도 중간노드에서 갈 수 있는 루트가 없기 때문에 8자임을 판단할 수 가 없다.
그래서 결국 방문에 관계없이 간선이 2개 이상 존재하는 노드가 있다면 8자로 판단하게끔 했고 이 경우는 통과하는 듯 했음
2번의 경우 여기선 생성한 정점을 찾기가 어렵다는 점이다.
기존엔 들어오는 간선이 없고 나가는 간선만 있는 정점을 생성한 정점이라 판단했었는데, 막대그래프의 시작정점 또한 같은 특성을 띄기 때문이었다.
물론, 막대그래프는 한 노드당 나가는 간선이든 들어오는 간선이든 하나씩 존재한다는 특징이 있지만, 생성된 정점과
...
..적다보니 조건을 빠트렸음을 깨달았다.
도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.라는 조건으로 될 수 없구나.
그러면 생성된 정점은
1. 2개 이상의 나가는 간선을 가진다.
2. 들어오는 간선이 없다.
로 구분할 수 있음이 명확해졌다.
혹시나 해서 해당 조건을 추가해 제출해봤는데
맞았다..!!
이게 어떻게 Lv2인지 싶지만.. 실제 코테에서도 못풀었던 문제인데 풀어서 상당히 뿌듯하다!
물론 다음에 꼭 풀어볼 것이고 그땐.. 30분안에 풀리라
결과
한문제를 더 풀어볼까 했지만 Lv3이고 지금 1시라 포기했다.
내일 풀 주사위 고르기문제는 빠르게 풀 수 있기를...
2. CS - 요약노트
최근 인프런에서 CS 책 10회독 스터디를 계속 구인하길래 신기해서 참여했다.
정말 다들 열심히 3일에 1회독을 실천하고 계셔서 나도 10회독을 해보고 싶어 책을 사고 배송 온 시점부터 진행하기로 했는데 어제 도착했다.
열심히 필기하면서 내것으로 만들어야지.
크 7장 필기했다.
이제 싸피 퇴근하고 집가서 Spring 공부해야지~~
마무리
환경 세팅에 생각보다 시간이 오래 걸려서
공부는 많이 못했음
내일도 화이팅이다!
