스마트폰 패턴 판별기
스마트폰 패턴은
한번지나온자리는 다시 지날수없으며 마주볼수있는 점끼리만 이을수있다
어떤수 n 을입력했을때 이것이 참이 될 수있는 패턴인지 판별할수있는 판별기를만들어보자
위에서 왼쪽부터 오른쪽으로 123
중간 왼쪽부터 오른쪽으로 456
아래 왼쪽부터 오른쪽으로 789
input
n
output
bool
ex
input : 1,2,5,6,4 output : True
input : 1,2,3,6 output : True
input : 3,8,4,1,7 output : True
input : 2,8,4,6 output : False
input : 5, 1, 9 의 경우는 True인가요, False인가요?
-
최상혁,
2019/05/22 21:14
true입니다
스마트폰 패턴창에서 확인해보시면됩니다
-
leak,
2019/05/27 16:43
2846은 왜 false인지...
-
Noname,
2019/07/05 11:57
2에서8로가는길에 5가있어서 25846이되야 True 입니다.
-
leak,
2019/07/22 09:51
감사합니다.
-
Noname,
2019/07/22 13:39
12564와 38417은 각각 5와 4를 두번 지나가는데 왜 True인지요?
-
김준우,
2020/12/31 16:26
12개의 풀이가 있습니다.
파이썬입니다.
def check_pattern_code():
n = input().replace(' ', '').split(",")
if len(set(n)) != len(n):
return False
check = {'13': False, '17': False, '19': False, '28': False, '37': False, '39': False, '46': False, '79': False}
for i in range(len(n)-1):
if n[i] == '2':
check['13'] = True
elif n[i] == '4':
check['17'] = True
elif n[i] == '5':
check['19'] = True
check['28'] = True
check['37'] = True
check['46'] = True
elif n[i] == '6':
check['39'] = True
elif n[i] == '8':
check['79'] = True
if n[i] < n[i+1]:
i_2 = n[i] + n[i+1]
else:
i_2 = n[i+1] + n[i]
if i_2 in check.keys() and not check[i_2]:
return False
return True
print(check_pattern_code())
Ruby
인덱스 차이 절대값으로 확인
def valid(nums)
idx = [*1..9].zip([*0..2].product [*0..2]).to_h
invalid_gaps, passed = [[0, 2], [2, 0], [2, 2]], []
nums.map(&idx).each_cons(2).all? do |(r1, c1), (r2, c2)|
passed << [r1, c1]
!invalid_gaps.any?([r1 - r2, c1 - c2].map &:abs) ||
passed.any?([(r1 + r2) / 2, (c1 + c2) / 2])
end
end
def check_patterns
patterns = (1..gets.to_i).map { gets.split(",").map &:to_i }
puts patterns.map { |nums| "input : #{nums.inspect}, output : #{valid nums}" }
end
Test
input = <<-eos
4
1, 2, 5, 6, 4
1, 2, 3, 6
3, 8, 4, 1, 7
2, 8, 4, 6
eos
result = <<-eos
input : [1, 2, 5, 6, 4], output : true
input : [1, 2, 3, 6], output : true
input : [3, 8, 4, 1, 7], output : true
input : [2, 8, 4, 6], output : false
eos
$stdin = StringIO.new(input)
expect { check_patterns() }.to output(result).to_stdout
def valid(nums) idx = [1..9].zip([0..2].product [*0..2]).to_h invalid_gaps, passed = [[0, 2], [2, 0], [2, 2]], [] nums.map(&idx).each_cons(2).all? do |(r1, c1), (r2, c2)| passed << [r1, c1] !invalid_gaps.any?([r1 - r2, c1 - c2].map &:abs) || passed.any?([(r1 + r2) / 2, (c1 + c2) / 2]) end end
def check_patterns patterns = (1..gets.to_i).map { gets.split(",").map &:to_i } puts patterns.map { |nums| "input : #{nums.inspect}, output : #{valid nums}" } end
파이썬 3.7 사용. 재밌는 문제라서 이왕 푸는거 3x3뿐만 아니라 NxN에서 판별할 수 있도록 짜봤는데 코딩실력이 부족하여 너무 지저분하게 길어진것 같네요;;
# N x N에서도 사용할 수 있게 확장해보기(N>1)
#정수a,b를 받아서 양수화 하고, 최대공약수를 반환하는 함수
def GCD(a, b): # The greatest common divisor, int 입력
if a*b==0: #둘중 0이 있는 경우
return 0
else: #둘다 0이 아니다
a=abs(a) #양수화
b=abs(b)
if a==b: #계산 횟수를 줄이기 위해.
return a
elif a>b:
a,b=b,a #a에 더 작은 수를 배치
div_a=[] #a의 약수리스트, 1은 생략
middle_a=a//2 #a/2 이하의 최대정수
for i in range(2, middle_a+1):
if a%i==0:
div_a.append(i) #약수 리스트에 넣기
div_a.append(a) #자기 자신 추가
result=1 #반환할 값
for i in div_a:
if b%i==0: #b가 a의 약수로 나누어 떨어지는지 확인
result=i
return result
def isNum(n): #n이 자연수이면 True 아니면 False
try:
if float(n)-int(n)==0 and n>0:
return True
else:
return False
except:
return False
class SmartPhone_Pattern:
def __init__(self, N): #N=격자의 크기
if isNum(N):
self.N=N
self.log=[] #로그 초기화
self.Last_p_num=N**2 #마지막 점 번호(3x3의 경우 9)
else:
print('Input Error, 자연수 N을 입력하세요')
def _NumToCoo(self, p_num): #점 번호를 받으면 [x,y]좌표로 변환해서 반환, N x N 격자
#1번점이 0,0이고 오른쪽으로 한칸 가면 x+=1, 아래쪽으로 한칸 가면 y+=1
if p_num in range(1,self.Last_p_num+1): #입력범위 확인
if p_num%self.N == 0:
x=self.N-1
y=p_num//self.N-1
else:
x=p_num%self.N-1
y=p_num//self.N
return [x,y]
else:
print('_NumToCoo Error. p_num 범위 오류, p_num=', p_num)
def _CooToNum(self, Coo): #[x,y]를 받으면 점 번호를 반환, N x N 격자
if len(Coo)!=2:
print('_CooToNum Error')
else:
x=Coo[0]
y=Coo[1]
if x==self.N-1:
return int(self.N*(y+1))
else:
return int(self.N*y+(x+1))
def _log_point(self, p_num): #점 번호를 받아서, 로그 리스트(self.log)에 저장
self.log.append(p_num)
def _check_log(self, p_num): #점 번호를 받아서 log에 있으면 Fasle. 없으면 True
if p_num in self.log: #이미 지난점
return False
else: #한번도 지난적 없는점
return True
def _Find_middle_Points(self, p_num1, p_num2): #점 번호 2개를 받아서, 두 점사이 경로상에 존재하는 격자점들을 리스트로 반환
p1=self._NumToCoo(p_num1) #좌표로 변환
p2=self._NumToCoo(p_num2)
delta_x=p2[0]-p1[0] #x, y축 변화량 계산
delta_y=p2[1]-p1[1]
result=[]
GCD_delta=GCD(delta_x,delta_y) #delta_x와 delta_y의 최대공약수
if GCD_delta==0: #delta_x 또는 delta_y가 0 == 수직 또는 수평이동
distance=abs(delta_x+delta_y) #이동한 거리
if distance==1: #수직 또는 수평으로 1칸이동
return result #빈 리스트 반환
else:
unit_x=delta_x/distance #unit_x 와 unit_y 중 하나는 0
unit_y=delta_y/distance
for i in range(1, distance):
result.append(self._CooToNum([p1[0]+i*unit_x, p1[1]+i*unit_y]))
return result
elif GCD_delta==1: #delta_x 와 delta_y가 서로소이면 빈 리스트 반환
return result
else: #경로 사이의 모든 격자점을 점 번호로 반환
unit_x=delta_x/GCD_delta
unit_y=delta_y/GCD_delta
for i in range(1, GCD_delta):
result.append(self._CooToNum([p1[0]+i*unit_x, p1[1]+i*unit_y]))
return result
def isValid(self, pattern): #입력받은 패턴이 True인지 False인지 판별.
self.log=[] #로그 초기화
for i, p in enumerate(pattern):
if p not in range(1, self.Last_p_num+1): # 무효한 입력이 섞여있는 경우 False
return False
elif i==0: #첫번째 입력
self._log_point(p) #로그만하고 다음으로 넘어감
else:
if self._check_log(p): #중복확인. True=지난적 없는 점
self._log_point(p) #로그
middle_points=self._Find_middle_Points(pattern[i-1], p) #이전 입력과 현재 입력, 두점 사이에 존재하는 격자점들 리스트. 없으면 빈 리스트
for a in middle_points: #두점 사이에 격자점이 존재할때만 루프 실행
if self._check_log(a): #두점 사이에 존재하는 격자점이 이미 지난 점이 아니면 False처리
return False
else:
return False #중복입력
return True #모든 입력을 검사했지만 도중에 한번도 False처리 되지않으면 True
if __name__=="__main__":
a=SmartPhone_Pattern(3) #격자 크기가 3 x 3 (1부터 9까지)
pattern_list=[[1,2,5,6,4],[1,2,3,6],[3,8,4,1,7],[2,8,4,6],[5, 1, 9]]
for pattern in pattern_list:
print('input={}, output={}'.format(pattern, a.isValid(pattern)))
출력결과
input=[1, 2, 5, 6, 4], output=True input=[1, 2, 3, 6], output=True input=[3, 8, 4, 1, 7], output=True input=[2, 8, 4, 6], output=False input=[5, 1, 9], output=True
+1
isNum() 대신 쓸 수 있는 float 클래스의 is_integer() 함수가 있습니다.
예) 1.0.is_integer()
f = 1.5
f.is_integer()
비슷하게 str 클레스에 isdigit(), isnumeric() isdecimal() 등이 있습니다.
-
Noname,
2019/07/22 16:31
class Program
{
static void Main(string[] args)
{
Pattern(new List<int> { 1, 2, 5, 6, 4});
Pattern(new List<int> { 1, 2, 3, 6});
Pattern(new List<int> { 3, 8, 4, 1, 7});
Pattern(new List<int> { 2, 8, 4, 6});
}
static void Pattern(List<int> input)
{
List<int> temp = new List<int> { };
bool possible = true;
bool overlap = false;
for (int i = 0; i < input.Count - 1; i++)
{
for (int e = i + 1; e < input.Count; e++)
{
if (input[i] == input[e])
{
overlap = true;
break;
}
}
}
if (overlap == false)
{
for (int i = 0; i < input.Count - 1; i++)
{
temp.Add(input[i]);
if (input[i] % 2 != 0 && input[i + 1] % 2 != 0 && input[i] != 5 && input[i + 1] != 5 && temp.Contains((input[i] + input[i + 1]) / 2) == false)
{
possible = false;
}
else if (input[i] % 2 == 0 && input[i + 1] % 2 == 0 && (input[i] + input[i + 1]) / 2 == 5 && temp.Contains(5) == false)
{
possible = false;
}
}
Console.WriteLine(possible);
}
else
{
Console.WriteLine(false);
}
}
}
저만 어렵게 했네요 ㅠㅠ
import java.util.Scanner;
public class smartphonepattern{
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int u = 1;
int b;
int t = 0;
int j = 0;
int a[] = new int[100];
int c[][] = new int[20][20];
for(int i = 0; i < 100; i++){
a[i] = 0;
}
while(true){
System.out.print("How many: ");
b = input.nextInt();
if(b >= 1)
break;
}
while(true){
System.out.printf("put integer number: ");
a[u] = input.nextInt();
if(u == b)
break;
if(a[u] < 1 && a[u] > 9)
continue;
u++;
}
while(true){
switch(a[t]){
case 1 : if(c[1][a[t+1]] == 1)
j++;
if(c[a[t+1]][1] == 1)
j++;
c[1][a[t+1]] = 1;
c[a[t+1]][1] = 1;
if(a[t+1] == 3 && c[1][2] != 1 && c[2][1] != 1)
j++;
if(a[t+1] == 7 && c[1][4] != 1 && c[4][1] != 1)
j++;
if(a[t+1] == 9 && c[1][5] != 1 && c[5][1] != 1)
j++;
break;
case 2 : if(c[2][a[t+1]] == 1)
j++;
if(c[a[t+1]][2] == 1)
j++;
c[2][a[t+1]] = 1;
c[a[t+1]][2] = 1;
if(a[t+1] == 8 && c[2][5] != 1 && c[5][2] != 1)
j++;
break;
case 3 : if(c[3][a[t+1]] == 1)
j++;
if(c[a[t+1]][3] == 1)
j++;
c[3][a[t+1]] = 1;
c[a[t+1]][3] = 1;
if(a[t+1] == 1 && c[3][2] != 1 && c[2][3] != 1)
j++;
if(a[t+1] == 7 && c[3][5] != 1 && c[5][3] != 1)
j++;
if(a[t+1] == 9 && c[3][6] != 1 && c[6][3] != 1)
j++;
break;
case 4 : if(c[4][a[t+1]] == 1)
j++;
if(c[a[t+1]][4] == 1)
j++;
c[4][a[t+1]] = 1;
c[a[t+1]][4] = 1;
if(a[t+1] == 6 && c[4][5] != 1 && c[5][4] != 1)
j++;
break;
case 5 : if(c[5][a[t+1]] == 1)
j++;
if(c[a[t+1]][5] == 1)
j++;
c[5][a[t+1]] = 1;
c[a[t+1]][5] = 1;
break;
case 6 : if(c[6][a[t+1]] == 1)
j++;
if(c[a[t+1]][6] == 1)
j++;
c[6][a[t+1]] = 1;
c[a[t+1]][6] = 1;
if(a[t+1] == 4 && c[5][6] != 1 && c[6][5] != 1)
j++;
break;
case 7 : if(c[7][a[t+1]] == 1)
j++;
if(c[a[t+1]][7] == 1)
j++;
c[7][a[t+1]] = 1;
c[a[t+1]][7] = 1;
if(a[t+1] == 1 && c[7][4] != 1 && c[4][7] != 1)
j++;
if(a[t+1] == 3 && c[7][5] != 1 && c[5][7] != 1)
j++;
if(a[t+1] == 9 && c[7][8] != 1 && c[8][7] != 1)
j++;
break;
case 8 : if(c[8][a[t+1]] == 1)
j++;
if(c[a[t+1]][8] == 1)
j++;
c[8][a[t+1]] = 1;
c[a[t+1]][8] = 1;
if(a[t+1] == 2 && c[8][5] != 1 && c[5][8] != 1)
j++;
break;
case 9 : if(c[9][a[t+1]] == 1)
j++;
if(c[a[t+1]][9] == 1)
j++;
c[9][a[t+1]] = 1;
c[a[t+1]][9] = 1;
if(a[t+1] == 1 && c[9][5] != 1 && c[5][9] != 1)
j++;
if(a[t+1] == 3 && c[9][6] != 1 && c[6][9] != 1)
j++;
if(a[t+1] == 7 && c[9][8] != 1 && c[8][9] != 1)
j++;
break;
default : break;
}
t = t + 1;
if( t == b)
break;
}
if(j == 0)
System.out.printf("true\n");
else
System.out.printf("false\n");
}
}
그래프 방문 문제의 변형으로 보고 풀었습니다.
# (x, y)로 바꿔서 중점을 구함
def sandwiched(p, q):
p, q = divmod(p-1, 3), divmod(q-1, 3)
mx, my = (p[0] + q[0]) / 2, (p[1] + q[1]) / 2
if mx.is_integer() and my.is_integer():
return int(mx) * 3 + int(my) + 1
# 전체 노드 집합을 만들고 방문한 노드는 제거한다.
# p~~>q 경로 상에서 q가 이미 방문한 노드이거나,
# 끼인 노드가 있고 이 노드가 아직 제거되지 않았으면 유효하지 않은 경로이다.
def is_valid(pattern):
nodes = set(range(1, 10))
path = [int(x) for x in pattern]
nodes.remove(path[0])
for p, q in zip(path, path[1:]):
if q not in nodes or sandwiched(p, q) in nodes:
return False
else:
nodes.remove(q)
return True
def isValid(L):
S = set(range(1, 10))
for x, y in zip(L, L[1:]):
t = (x+y)/2
if t==5 and t in S: return False
if x%2 and y%2 and not t%2 and t in S: return False
S.remove(x)
return True
L = list(map(int, input().split()))
print(isValid(L))
그냥 무식하게 풀었습니다..
public class 스마트폰패턴 {
boolean[] visited;
public 스마트폰패턴() {
visited=new boolean[9];
Arrays.fill(visited, false);
}
public boolean GetResult(int[] patterns) {
for(int i=0;i<patterns.length-1;i++) {
if(!isPossible(patterns[i],patterns[i+1]))
return false;
}
return true;
}
public boolean isPossible(int depa,int dist) {
visited[depa-1]=true;
switch(depa) {
case 1:
if( (dist==3&&!visited[1]) || (dist==7&&!visited[3]) || (dist==9&&!visited[4]) )
return false;
break;
case 2:
if( (dist==8&&!visited[4]) )
return false;
break;
case 3:
if( (dist==1&&!visited[1]) || (dist==9&&!visited[5]) || (dist==7&&!visited[4]) )
return false;
break;
case 4:
if( (dist==6&&!visited[4]) )
return false;
break;
case 6:
if( (dist==4&&!visited[4]) )
return false;
break;
case 7:
if( (dist==1&&!visited[3]) || (dist==9&&!visited[7]) || (dist==3&&!visited[4]) )
return false;
break;
case 8:
if( (dist==2&&!visited[4]) )
return false;
break;
case 9:
if( (dist==3&&!visited[5]) || (dist==7&&!visited[7]) || (dist==1&&!visited[4]) )
return false;
break;
default:
if(visited[dist-1])
return false;
}
return true;
}
}
from math import sqrt
def pattern(op_inp) :
map_ = {1 : (0, 0), 2 : (0, 1), 3 : (0, 2),
4 : (1, 0), 5 : (1, 1), 6 : (1, 2),
7 : (2, 0), 8 : (2, 1), 9 : (2, 2)}
dis_false = [2, 2*sqrt(2)]
visited = set([]) # 방문한 점 기록
for pos in range(0, len(op_inp)-1) :
if op_inp[pos+1] in visited : ## 이미 방문한 점 : return False
return False
else :
dis = sqrt((map_[op_inp[pos]][0]-map_[op_inp[pos+1]][0])**2+(map_[op_inp[pos]][1]-map_[op_inp[pos+1]][1])**2) # 현재점과 다음점의 거리를 계산
if dis in dis_false and op_inp[pos] in visited : pass # 거리상 False의 대상이라도 그 중간의 점이 visited(방문한 점)에 있다면 False를 반환하지 않음
elif dis in dis_false : return False # 계산한 거리가 False의 대상(1과 9처럼 중간에 다른 숫자가 있다면)이라면 False
visited.update([op_inp[pos], op_inp[pos+1]]) # 방문한 점 업데이트
return True # 입력된 점들을 모두 처리해도 False가 반환되지 않는다면 True 반환
pattern(list(map(int, input("INPUT : ").split())))
점과 점사이의 거리를 계산하면서 판별하도록 만들었습니다.
결과
INPUT : 1 2 5 6 4
INPUT : 1 2 3 6
INPUT : 3 8 4 1 7
INPUT : 2 8 4 6
True
True
True
False
# 키패드를 좌표평면 상에 표시해서 좌표 간 거리가 2 또는 8**0.5면 불가능한 패턴이라는 점을 응용한 코드
# 3*3 크기의 키패드를 좌표평면 상에 만드는 함수
def make_keypad():
keypad = {}
row = 0
for i in range(1,3**2+1):
if i%3 == 0:# 키패드 숫자 i가 3의 배수일 때
keypad[i] = (3, row)
row += 1# 3의 배수 바로 다음 수부터는 y좌표가 +1이 됨
else:
keypad[i] = (i%3,row)# 키패드의 x좌표는 키패드 숫자 i를 3으로 나눈 몫임
return keypad# 키패드의 숫자를 키로 가지고 좌표를 값으로 가지는 딕셔너리를 반환함
def check_pattern():
print("패턴 숫자를 순서대로 입력하세요.")
nums = input()
err_list =[]# 불가능한 좌표 사이의 거리를 모아놓는 리스트
for num in nums:# 입력받은 숫자를 하나씩 할당
n1 = int(num)
if nums[-1] == num:# num이 받은 값이 nums리스트의 마지막 원소이면
n2 = int(num)
else:
n2 = int(nums[nums.index(num)+1])# 그렇지 않으면 n2는 num의 다음 수
#print(n1,n2)
co1 = make_keypad()[n1]# 좌표 딕셔너리에서 키 n1이 가지는 좌표
co2 = make_keypad()[n2]# 좌표 딕셔너리에서 키 n2가 가지는 좌표
#print(co1)
x_co1 = list(co1)[0]# 첫 숫자의 x좌표
x_co2 = list(co2)[0]# 두번째 숫자의 x좌표
y_co1 = list(co1)[1]# 첫 숫자의 y좌표
y_co2 = list(co2)[1]# 두번째 숫자의 y좌표
dis = ((x_co2 - x_co1)**2+(y_co2 - y_co1)**2)**0.5# 두 좌표 사이의 거리
#print(x_co2,x_co1)
#print(y_co2,y_co1)
#print(dis)
if dis == 2 or dis == 8**0.5:#두 좌표 사이의 거리가 2 이거나 8**0.5이면
err_list.append(dis)#불가능한 거리 리스트에 원소 추가
else:
pass
if err_list == []:# 불가능한 거리가 하나도 없으면 가능한 패턴임
print("가능한 패턴입니다.")
else:
print("불가능한 패턴입니다.")
check_pattern()
def check_pattern_code():
n = input().replace(' ','').split(",")
if len(set(n)) != len(n):
return False
map = [[1 for _ in range(3)] for _ in range(3)]
su = int(n[0])
y, x = su//3, su % 3
if x == 0:
y, x = y-1, 2
else:
x -= 1
map[y][x] += 10
for i in range(1, len(n)):
su = int(n[i])
r, c = su//3, su%3
if c == 0:
r, c = r-1, 2
else:
c -= 1
if map[r][c] > 10:
return False
if (abs(r-y) % 2 == 0 and abs(c-x) % 2 == 0) and map[(r+y)//2][(c+x)//2] < 10:
return False
map[r][c] += 10
y, x = r, c
return True
print(' output: ', check_pattern_code())