코딩테스트--거리두기 확인하기(프로그래머스 / 파이썬)

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

코딩테스트 연습 - 거리두기 확인하기

 

---

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

 

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

---

제한사항

• places의 행 길이(대기실 개수) = 5
  • places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
  • places 원소의 길이(대기실 가로 길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
• return 값 형식
  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

 

---

 

네.... 어려워보이네요 ㅎㅎ

 

그래도 대기실 개수, 인원은 정해져 있네요!(5*5)

 

거리두기가 잘 되어 있는지를 확인하는 문제...

 

한번해보죠!

 

저는 사각형으로 잘라서 탐색하는 방법을 사용하기로 했습니다.

1. 일단 P 를 찾는다

2. P의 좌표를 x,y라 했을때 (x+1,y) , (x,y+1) , (x+1,y+1)를 구한다

3. 서로를 비교하며 위 문제의 거리두기 형식이 맞는지를 확인!

 

만약 이렇게 P가 있다면

P	O	X
O	X	P
X	X	X

이렇게만 탐색을 하는것!

--> 왜 주변 8칸 다 안봐도 되나요?? -->

P	O	X
O	P	X
X	X	X

이렇게 되어있다면 가운데 P를 기준으로 탐색하기전에 맨위 P에서 먼저 그주변을 탐색하기때문에

P를 기준으로 오른쪽만 봐주시면 될것같아요! 

일단해보겠습니다!!

 

 

def find(i,j,k):
        check=0
        right=""
        bottom=""
        last=""
        
        if k!=4:
            right=i[j][k+1]
            check+=1
            
        if j!=4:
            bottom=i[j+1][k]
            check+=1
        
        if right=="P" or bottom=="P":#거리두기 안지킴
            return True
        else:
            if check==2:
                last=i[j+1][k+1]
                
                if last=="P":
                    if right=="O" or bottom=="O":#거리두기 안지킴
                        return True
            
        return False

네...... 실패 ㅋㅋㅋ

 

근데 방법은 나쁘지 않은것 같았는데...

 

제 생각으로는

o	O	O
O	O	P
O	P	X

이렇게 되면 비교가 안되네요.. 넵... 다시해보죠

 

이번엔

o	O	O
O	P	O
O	O	X

P 기준으로 십자로 탐색 해보겠습니다.

 

def find(i,j,k,mode):
        check=0
        memolist=["up","right","down","left"]
        
        last=""
        if k!=4:
            memolist[1]=i[j][k+1]
        if k!=0:
            memolist[3]=i[j][k-1]
        if j!=0:
            memolist[0]=i[j-1][k]
        if j!=4:
            memolist[2]=i[j+1][k]
        
        if mode=="P":
            for i in memolist:
                if i=="P":
                    return True
        else:
            if memolist[0]==memolist[1]=="P":
                return True
            elif memolist[1]==memolist[2]=="P":
                return True
            elif memolist[2]==memolist[3]=="P":
                return True
            elif memolist[0]==memolist[2]=="P":
                return True
            elif memolist[1]==memolist[3]=="P":
                return True
            
            
        return False

O 표시 되어있는 책상에서도 탐색해야될꺼 같아서 했습니다!

 

	0
3	P	1
	2

일때는 0,1,2,3 이 P인지 확인해주고

 

	0
3	O	1
	2

일때는 (0과 1),(1과 2),(2과 3),(3과 0),     (0과 2),(1과 3)

이 동시에 P인지 확인 해주면 될것 같네요!

 

 

결과는?

11번만 실패.....

뭘까요........

 

if 문에 하나 추가 안해줬네요....

 if memolist[0]==memolist[1]=="P":
                return True
            elif memolist[1]==memolist[2]=="P":
                return True
            elif memolist[2]==memolist[3]=="P":
                return True
            elif memolist[3]==memolist[0]=="P":
                return True

            elif memolist[0]==memolist[2]=="P":
                return True
            elif memolist[1]==memolist[3]=="P":
                return True

 

	0
3	P	1
	2

이렇게 있을때 3 과 0을 안써줬네요 ㅋㅋㅋ 너무헤맸네...

 

 

*all 

def solution(places):
    answer = []
    breakcheck=False

    def find(i,j,k,mode):
        check=0
        memolist=["up","right","down","left"]

        last=""
        if k!=4:
            memolist[1]=i[j][k+1]
        if k!=0:
            memolist[3]=i[j][k-1]
        if j!=0:
            memolist[0]=i[j-1][k]
        if j!=4:
            memolist[2]=i[j+1][k]

        if mode=="P":
            for i in memolist:
                if i=="P":
                    return True
        else:
            if memolist[0]==memolist[1]=="P":
                return True
            elif memolist[1]==memolist[2]=="P":
                return True
            elif memolist[2]==memolist[3]=="P":
                return True
            elif memolist[3]==memolist[0]=="P":
                return True

            elif memolist[0]==memolist[2]=="P":
                return True
            elif memolist[1]==memolist[3]=="P":
                return True

        return False

    for i in places:
        breakcheck=False
        for j in range(5):
            for k in range(5):
                if i[j][k]=="P":
                    breakcheck=find(i,j,k,"P")
                elif i[j][k]=="O":
                    breakcheck=find(i,j,k,"O")

                if(breakcheck):
                    break
            if(breakcheck):
                break
        if(breakcheck):
            answer.append(0)
        else:
            answer.append(1)
    return answer

여튼 성공했는데 코드가 너무기네요...

 

 

다른 분들은 탐색으로 해결하더라구요..?

P를 만나면 상하좌우로 2칸씩 이동해서 그자리에 P가 있는지 확인하는

 

def solution(places):
    result = []
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    def f(i, j, cnt):
        nonlocal good
        if cnt >2 : return
        if -1<i<5 and -1<j<5:
            if graph[i][j] == 'X':
                return

            if cnt != 0 and graph[i][j] == 'P':
                good = 0
                return

            graph[i][j] = 'X'

            for w in range(4):
                ni = i+dx[w]
                nj = j+dy[w]
                f(ni, nj, cnt+1)

    for case in places:
        graph = [list(r) for r in case]
        good = 1
        for i in range(5):
            for j in range(5):
                if graph[i][j]=='P':
                    f(i,j,0)

        result.append(good)
    return result

 

 

저의 if문 범벅보다는 짧네요...

근데.... if문 범벅이 더 빠르네...ㅎㅎ

 

 

둘 중에 생각나는거 써야겠네요...

 

 

틀린 점이 있다면 댓 달아주세요!