패턴은 주어진 수열 순서대로 그려집니다. 즉, 인접 여부는 바로 그 직전 수만 확인해야 합니다.
추가로 놓치고 계신 게 있습니다. 어떤 두 수 사이에 다른 수가 존재해도, 그 가운데에 있는 수를 먼저 사용했다면 두 수를 이후에 사용하는 것이 가능합니다.
예제 첨부합니다.
17300번 - 패턴
패턴은 주어진 수열 순서대로 그려집니다. 즉, 인접 여부는 바로 그 직전 수만 확인해야 합니다.
추가로 놓치고 계신 게 있습니다. 어떤 두 수 사이에 다른 수가 존재해도, 그 가운데에 있는 수를 먼저 사용했다면 두 수를 이후에 사용하는 것이 가능합니다.
예제 첨부합니다.
사실 인접하다는 것이 숫자 사이에는 아무 의미가 없습니다.
작성자 분께서 "두 수가 다른 수를 거치지 않고 연결 가능한 것 == 인접한 것"이라고 정의하고 계신 것 같아 그대로 설명해드린 겁니다.
문제에서 말하는 '인접하다'는, 주어진 수열에서의 인접입니다.
즉 수열 [3, 5, 7, 9]가 있다면, 3과 5, 5와 7, 7과 9는 서로 인접이고, 그 외의 어떠한 인접도 없습니다.
수열 상에서 붙어서 등장만 한다면 인접한 것입니다.
[1 5 9 6 4]에서 6 4 는 인접합니다. 3*3 칸에서 6과 4를 이으면 5번 점을 지나가게 되는데, 이 5번 점은 이미 이전에 (두 번째에) 사용했기 때문에 괜찮은 것입니다.
[5 1 3]에서 1과 3은 인접이고, 1과 3을 이으면 2를 지나게 되는데, 2를 이전에 쓴 적이 없기 때문에 안 되는 것입니다.
혹시 더 도움이 필요하면 말씀해주세요.
우선 저는 특정 숫자의 위치에서 다른 숫자로의 연결이 가능한 범위는 다음과 같이 생각하고 있었습니다.
1 : 2,4,5,6,8
2 : 1,3,4,5,6,7,9
3 : 2,4,5,6,8
4 : 1,2,3,5,7,8,9
5 : 1,2,3,4,6,7,8,9
6 : 1,2,3,5,7,8,9
7 : 2,4,5,6,8
8 : 1,3,4,5,6,7,9
9 : 2,4,5,6,8
즉,
1. 상하좌우
2. 대각선
3. 상하좌우에서 대각선 방향입니다.
그래서 말씀주신
3
5 1 3
의 경우
5 -> 1 (대각선 이동이므로 가능)
1 -> 3 (이미 이전에 사용했던 5를 중간에 거쳐 이동)
이라고 생각하여
YES가 나오는 코드를 짯던 것인데,
이미 사용했던 숫자를 지날때는 꺽임(패턴상)이 안되므로 1 에서 5를 거쳐 3을 갈 수 없다고 이해하면 될까요?
실제로 핸드폰 패턴을 해보니 5 1 (5) 9 는 되도, 5 1 (5) 3은 안되는걸 확인했습니다...
어디서 그런 생각을 하셨는지는 모르겠지만
이미 쓴 수를 거쳐서 이동하는 건 불가능합니다.
지문에서도 인접한 두 수를 순서대로 연결한다고 적혀있으니까요.
다만 그 과정에서 중간에 다른 수를 지나게 된 경우, 그 수는 이미 사용되었어야 한다는 조건이 붙어있는 것 뿐입니다.
(1 - 9 연결 시 5, 1-3 연결 시 2)
이 조건을 만족하면 1부터 9까지의 모든 쌍이 서로 인접할 수 있습니다.
얘기 해주신 내용을 기반으로 다시 한번 풀어봐야 될것 같습니다..
제가 이해를 잘 못했음에도 끝까지 답변 달아주셔서 감사합니다!
좋은 하루 되세요!
댓글을 작성하려면 로그인해야 합니다.
unool 1년 전
각 숫자마다 인접하여 이동가능한 숫자를 Set에 담고, 각 숫자를 Key값으로 하여 Value에 해당 Set을 넣어주었습니다.
그리하여, 패턴의 숫자들을 하나씩 참조하여 이전 패턴의 숫자 중 인접한것이 있는지 확인 하였습니다..
그런데, 3%에서 실패가 뜨네요... 고수분들의 답변 부탁드립니다..