[코드트리 챌린지] 객체 정렬, 시뮬레이션(배열-리스트, dx-dy technique)

실력진단

---

학습내용

객체 정렬

• 키를 기준으로 정렬
  • lambda x: x*2 (익명함수)

students.sort(key=lambda x: x.kor) # 국어 점수 기준 오름차순 정렬
students.sort(key=lambda x: -x.kor) # 국어 점수 기준 내림차순 정렬

https://www.codetree.ai/missions/5/problems/sort-by-height?&utm_source=clipboard&utm_medium=text

 

class User:
    def __init__(self, name, height, weight):
        self.name=name
        self.height=height
        self.weight=weight

n=int(input())
users=[]
for _ in range(n):
    name,height,weight=tuple(input().split())
    users.append(User(name,int(height),int(weight)))

users.sort(key=lambda x: x.height)

for i in range(n):
    print(users[i].name, users[i].height, users[i].weight)

#이런식으로도 가능!!
for user in users:
    print(user.name,user.height,user.weight)

• tuple이용한 객체정렬

students = [
    ("lee", 80, 90), # 첫 번째 학생
    ("kim", 80, 80), # 두 번째 학생
    ("park", 30, 60), # 세 번째 학생
]

students.sort(key=lambda x: x[0]) # 이름 기준 사전순 정렬

for name, eng, math in students: # 정렬 이후의 결과 출력
    print(name, eng, math)

>> kim 80 80
   lee 80 90
   park 30 60

• 여러 우선순위를 갖는 객체 정렬

print((2,3)>(1,9)) # True --> 튜플끼리 대소관계 비교 가능!! 앞자리 부터!

#두개의 우선순위가 있는 경우
students.sort(key=lambda x: (x.kor, x.eng)) #kor우선순위 비교->같을경우 영어점수

• 국영수 순이지
  https://www.codetree.ai/missions/5/problems/korean-english-math-order?&utm_source=clipboard&utm_medium=text

 

 

 

 

 

• 정렬 기준이 복잡한 객체 정렬

students.sort(key=lambda x: x.kor+x.eng+x.math) #총점 비

• 객체 정렬시 index 멤버 변수의 필요성

시뮬레이션1

• 블럭쌓는 명령2 https://www.codetree.ai/missions/5/problems/block-stacking-commands2?&utm_source=clipboard&utm_medium=text

#입력
n,k=map(int,input().split())
lst=[0 for _ in range(n)] # 0~n-1
#lst=[0]*(n+1) 0번째거는 남겨두고 1~n 사용한다면!
for _ in range(k):
    a,b=map(int, input().split())
    for i in range(a-1, b):
        lst[i]+=1

print(max(lst)) 

• 최대로 겹치는 구간 https://www.codetree.ai/missions/5/problems/maximum-overlapped-segments?&utm_source=clipboard&utm_medium=text

# 내 풀이
# 입력
n=int(input())
lst=[0]*201
for _ in range(n):
    x1,x2=map(int, input().split()) #음수일수도 있음!!
    for i in range(x1+100,x2+100):
        lst[i]+=1

print(max(lst))

# 모범 답안
OFFSET = 100
MAX_R = 200

# 변수 선언 및 입력
n = int(input())
segments = [
    tuple(map(int, input().split()))
    for _ in range(n)
]
checked = [0] * (MAX_R + 1)

for x1, x2 in segments:
    # OFFSET을 더해줍니다.
    x1, x2 = x1 + OFFSET, x2 + OFFSET
    
    # 구간을 칠해줍니다.
    # 구간 단위로 진행하는 문제이므로
    # x2에 등호가 들어가지 않음에 유의합니다.
    for i in range(x1, x2):
        checked[i] += 1

# 최댓값을 구합니다.
max_num = max(checked)
print(max_num)

• 사각형의 총넓이2 https://www.codetree.ai/missions/5/problems/total-width-of-a-rectangle2?&utm_source=clipboard&utm_medium=text

# 내 답안
OFFSET=100
n=int(input())

lst=[[0 for _ in range(201)] for _ in range(201)]
recs=[
    tuple(map(int,input().split()))
    for _ in range(n)
]

for x1,y1,x2,y2 in recs:
    x1,y1,x2,y2=x1+OFFSET,y1+OFFSET,x2+OFFSET,y2+OFFSET

    for j in range(x1,x2):
        for k in range(y1,y2):
            if lst[j][k]==0:
                lst[j][k]=1
result=0
for i in range(201):
    result+=sum(lst[i])   
print(result)

# 모범답안
OFFSET=100

n=int(input())

count=[[0]*201 for _ in range(201)]
for _ in range(n):
    x1,y1,x2,y2=tuple(map(int,input().split()))

    x1+=OFFSET
    y1+=OFFSET
    x2+=OFFSET
    y2+=OFFSET

    for x in range(x1,x2):
        for y in range(y1,y2):
            count[x][y]=1

area=0
for x in range(201):
    for y in range(201):
        if count[x][y]==1:
            area+=1

print(area)

• 겹치지 않는 사각형의 넓이 https://www.codetree.ai/missions/5/problems/area-of-non-overlapping-rectangle?&utm_source=clipboard&utm_medium=text

# 내 답안
OFFSET=1000
count=[[0]*2001 for _ in range(2001)]
for i in range(3):
    x1,y1,x2,y2=map(int,input().split())
    x1+=OFFSET
    y1+=OFFSET
    x2+=OFFSET
    y2+=OFFSET

    for x in range(x1,x2):
        for y in range(y1,y2):
            if i==2:
                count[x][y]+=2
            else:
                count[x][y]+=1

result=0
for i in range(2001):
    for j in range(2001):
        if count[i][j]==1:
            result+=1
print(result)

시뮬레이션2

dx, dy technique-방향에 맞춰

x,y=0,0
dx, dy = [1, 0, -1, 0], [0, -1, 0, 1]

nx, ny = x + dx[dir_num], y + dy[dir_num]

• 방향에 맞춰 이동 https://www.codetree.ai/missions/5/problems/move-in-direction?&utm_source=clipboard&utm_medium=text

n=int(input())
x,y=0,0

for _ in range(n):
    direc,dis=input().split()
    dis=int(dis)

    #딕셔너리를 이용하여 좀 더 가독성이 있고 짧은 코드
    dir_mapper={
        "E":0,
        "S":1,
        "W":2,
        "N":3
    }
    dir_num=dir_mapper[direc]

    #흔히 생각할 수 있는 코드
    # if direc=="E":
    #     dir_num=0
    # elif direc=="S":
    #     dir_num=1
    # elif direc=="W":
    #     dir_num=2
    # else:
    #     dir_num=3

    #   0.  1. 2. 3
    dx=[1, 0, -1, 0]
    dy=[0, -1, 0, 1]

    x,y=x+dx[dir_num]*dis, y+dy[dir_num]*dis

print(x,y)

dx, dy technique-방향 회전을 위한

dir_num = 3 
x, y = 1, 5
dx, dy = [1, 0, -1, 0], [0, -1, 0, 1]

# rotate direction 시계
dir_num = (dir_num + 1) % 4

# 반시계
dir_num = (dir_num - 1 + 4)%4

# move
nx, ny = x + dx[dir_num], y + dy[dir_num]

• 문자에 따른 명령 2 https://www.codetree.ai/missions/5/problems/text-based-commands2?&utm_source=clipboard&utm_medium=text

#입력
input_char=input()
orders=list(input_char)

#dxdy
x,y=0,0
dir_num=3
dx=[1,0,-1,0]
dy=[0,-1,0,1]

#rotation
for order in orders:
    if order=="L":
        dir_num=(dir_num-1+4)%4
    elif order=="R":
        dir_num=(dir_num+1)%4
    else:
        x,y=x+dx[dir_num],y+dy[dir_num]

print(x,y)

dx, dy technique-격자에서의 dx, dy

격자에서의 x, y를 수학에서의 x, y가 아닌 행, 열로 생각해야 한다는 것

※ zip함수

arr1 = [1, 2, 3]
arr2 = [4, 5, 6]
for elem1, elem2 in zip(arr1, arr2):
    print(elem1, elem2)

>> 1 4
   2 5
   3 6

※ index error 피하기!

def in_range(x, y):
    return 0 <= x and x < 5 and 0 <= y and y < 5

• 인접한곳에 1이 있나?

a = [[0, 0, 0, 1, 0],
     [0, 1, 1, 1, 0],
     [0, 0, 0, 0, 1],
     [1, 0, 1, 1, 1],
     [1, 0, 1, 1, 0]]

x, y = 2, 4
dxs, dys = [0, 1, 0, -1], [1, 0, -1, 0]

#범위 벗어나지 않는지 먼저 확인하기 위한 함수
def in_range(x, y):
    return 0 <= x and x < 5 and 0 <= y and y < 5

cnt = 0
for dx, dy in zip(dxs, dys):
    nx, ny = x + dx, y + dy
    if in_range(nx, ny) and a[nx][ny] == 1: #in_range함수가 먼저 나와야해
        cnt += 1

print(cnt)

• 1이 3개 이상 있는 위치 https://www.codetree.ai/missions/5/problems/place-more-than-3-ones?&utm_source=clipboard&utm_medium=text

# 입력
n=int(input())
a=[list(map(int, input().split())) for _ in range(n)]

# dx, dy
dxs,dys=[1,0,-1,0],[0,-1,0,1]
sum_cnt=0

#범위 벗어나지 말라는 함수
def in_range(x,y):
    return 0 <= x and x < n and 0 <= y and y < n

#x,y 순회하면서 인접한곳에 1이 3개이상 있는지 확인
for x in range(n):
    for y in range(n):
        cnt=0
        for dx,dy in zip(dxs,dys):
            nx,ny=x+dx,y+dy
            if in_range(nx,ny) and a[nx][ny]==1:
                cnt+=1
        if cnt>=3:
            sum_cnt+=1

print(sum_cnt)

dx dy technique-조건에 따른 이동

반대 전환이 필요할때 - 마주보는 방향의 합이 3이 되게 설정하기

• 작은 구슬의 이동 https://www.codetree.ai/missions/5/problems/small-marble-movement?&utm_source=clipboard&utm_medium=text

n,t=map(int,input().split())
x,y,d=input().split()

dir_mapper={
    'R':0,
    'L':3,
    'U':2,
    'D':1
}
x,y,move_dir=int(x)-1,int(y)-1,dir_mapper[d]

dxs=[0,1,-1,0]
dys=[1,0,0,-1]

def in_range(x,y):
    return x>=0 and x<n and y>=0 and y<n

for _ in range(t):
    nx,ny=x+dxs[move_dir],y+dys[move_dir]
    if in_range(nx,ny):
        x,y=nx,ny
    else: #1초 동안 방향전환만 하면 된다!
        move_dir=3-move_dir