거리두기 확인하기

링크: https://school.programmers.co.kr/learn/courses/30/lessons/81302
문제분류 : 배열
난이도 : Level 2
풀이시간 : 40분
결과: 성공

회고

21년 카카오 인턴십 문제였다.
레벨은 2정도인걸 보니 코테에서 1번 아니면 2번에 나왔을거 같다ㅋ.ㅋ

맨해튼 거리라는 개념이 나왔지만 딱히 어려운 개념은 아니었다.
대기실에서 사람의 위치를 기준으로 오른쪽 직선, 아래쪽 직선, 왼쪽 아래 대각선만 체크하면 될거라 생각했다.

일단 대기실의 개수는 5개, 대기실의 크기는 5X5라고 조건이 주어졌다.
따라서 시간복잡도는 기껏해야 5 25 (2 * 2 + 1) 정도 밖에 안된다.

거리가 1인 경우, 거리가 2인 경우, 거리가 2면서 파티션이 있는 경우를 체크해서 정답을 도출했다.
하지만, 정확도 체크에서 83.3%가 나왔다.

예외 케이스를 생각해봤고, "oopxo", "opooo"과 같은 경우에
두 번째 문자열의 p의 위치에서 첫 번째 문자열의 p의 위치를 감지하지 못했다.
그래서 사방으로 체크하는 방식으로 로직을 변경했다.
시간복잡도는 신경쓰지 않았다. 그래봐야 5 25 (2 4 + 1 4) 밖에 안되기 때문이다.

정답은 나왔지만, 버그를 유발할 수 있는 코드라는 생각이 들어 모범 답안을 찾아서 공부했다.
솔직히 말하면, 구현을 끝내고 디버깅하는데 더 오랜 시간을 들였다...🥲
내 코드를 보면 왜 그런지 이해가 될 것이다.

모범답안은 훨씬 괜찮은 로직이었다. 또한 시간 복잡도도 많이 간소화된 로직이었다.
완전탐색으로 문제를 풀어내는 것도 나쁘지 않지만, 좀 더 논리적인 눈을 길러야겠다.

내 코드

코드가 상당히 복잡하다.
나름 메서드를 분리했지만, 이런 식으로 작성하면 분리 안하는 것만 못하다.

d값이 1인 경우는 상하좌우 거리가 1일 때, 대각선일 때이다.
d값이 2인 경우는 상하좌우 거리가 2일 때이다.

d가 2일 때 주의할 점은 'P'가 발견된더라도 그 사이에 'X'가 있는지 확인해야 된다.
그래서 isDistancedLength 함수에서 if문 안에 if문이 복잡하게 걸려있다.

만일, 조건을 하나라도 만족 못하면 false를 return하도록 만들었다.

답은 맞았으나, 케이스 하나 하나 다 따져가며 푸니 머리가 아팠다.

모범답안

생각보다 굉장히 심플하다.

논리적으로 따져보면 우리가 생각해야할 것은 맨해튼 거리를 기준으로
'P'의 위치에서 또 다른 'P'까지의 경로에 'X'가 있냐 없냐이다.
1) 현재 'P'의 위치에서 인접한 위치에 'P'가 있다면, 맨해튼 거리를 지키지 않은 것이다.
2) 현재 'P'의 위치에서 인접한 거리에 'X'가 있다면, 그 경로에 관해서는 더 따질 필요가 없다.
3) 현재 'P'의 위치에서 인접한 거리에 'O'가 있다면, 'O'의 위치로 이동해 인접한 곳에 'P'가 있는지 따져야 한다.

• 만일 'P'가 없다면 맨해튼 거리를 지킨 것이다.
• 만일 'P'가 인접해 있다면, 맨해튼 거리를 지키지 않은 것이다.

isNextToPlayer 함수에서 exclude는 우리가 왔던 방향 따지는 것은 제외한다는 것이다.
그래야 잘못된 판단을 하지 않는다.

확실히 모범 답안의 코드는 어떤 경우가 와도 컴파일 에러는 안나는 방식인거 같다.
또 논리적인 풀이다 보니, if문을 주구장창 쓰지 않아도 되니 버그 찾기도 쉽다.
시간이 없다면 무조건 구현하는 것도 괜찮겠지만,
코테는 논리적인 코드를 짜는게 중요하니 연습을 더 해야겠다.