[이코다] 그리다 & 구현 실전문제

시간제한1 초 데이터 :100만개 => O ( n log n)

p.96 숫자카드게임

 

내풀이

풀이시간	시간복잡도
20m	O(N log N)

def solution ():
    n,m = map(int,input().split())

    for i in range(n):
        matrix.append(min(list(map(int, input().split()))))
    print(max(matrix))
    result= 0



solution()

 

배운점

답의 후보들을 배열에 넣지 말고 그냥 두가지 값을 바로 max로 비교하는 것이 더 좋다

result = 0

for i in arr:
	result = max(i,result)

 

p.100 숫자카드

풀이시간	시간복잡도
20m	O(N log N)

내 코드

def solution():
    n,k = map(int,input().split())
    cnt=0
    while n!=1:
        if n%k ==0:
            n = n/k
            cnt+=1
        else:
            n-=1
            cnt+=1
    print(cnt)
solution()

배운점

예외에 대한 생각을 항상 해야한다.

 

구현 - p.110 상하좌우

풀이시간	시간복잡도
12m	O(N^2)

내 풀이

def solution ():
    n = int(input())
    go = input().split()
    loc = [1,1]

    for i in go:
        if i == 'R':
            if loc[1]+1<=n:
                loc[1]+=1
        elif i == 'L':
            if loc[1]-1>1:
                loc[1]-=1
        elif i == 'U':
            if loc[0]-1>1:
                loc[0]-=1
        else:
            if loc[0]+1<n:
                loc[0]+=1
    print(" ".join(map(str,loc)))

        
solution()

배운점

 

입력시 숫자로 변경할 게 아니면 map을 하지 않아도 된다

 

 

 

배운점 모음 

문자열이 순서대로 주어지고 그 순서를 이용해야 할 때 

ord를 이용하고 첫번째 값을 빼버리면  순서가 나온다 

input = 'b'
step = ['a','b','c']

ord(input)- ord(step[0]) // 1 인덱스가 나옴

 

구현 - p.118 게임 개발

풀이시간	시간복잡도
2h	O(N^3)?

def solution():
    n,m = map(int,input().split())
    x,y,v = map(int,input().split())
    #지나온 기록
    d = [[0]*m for _ in range(n)]
    direction = [[-1,0],[0,1],[1,0],[0,-1]]

    d[x][y]=1
    arr=[]
    #지도배열받기
    for i in range(n):
        temp = list(map(int,input().split()))
        arr.append(temp)
    cnt=0
    ans=1
    #왼쪽으로 도는 동작
    def turnLeft(v):
        v-=1
        if v == -1:
            v =3
        return v
    
    while True:
        v=turnLeft(v)
        addX,addY = direction[v]
        newX,newY = x+addX, y+addY

        if arr[newX][newY] ==0 and d[newX][newY]==0:
            d[newX][newY]=1
            x,y = newX,newY
            cnt=0
            ans+=1
            continue
        else:
            cnt+=1
        if cnt==4:
            backX,backY =direction[v]
            newX,newY = x-backX, y-backY 
            if arr[newX][newY] == 0:
                x,y = newX,newY
            else:
                break
            cnt=0
    print(ans)


solution()

복잡한 문제라 오래 걸렸다. 

차분히 생각하면 풀 수있는 문제였지만 집중을 하지 못해서 오래걸렸다.

배열 초기화 하는법과 , 위치를 움직이는 것은 d로 케이스를 정해야 함을 깨달았다.

 

지난데 다시 지나기 금지 = 똑같은 배열 만들어서 흔적 표시

위치 값 움직인느 것 = dx,dy ,direction 등을 만들어서 case별로 생각해내기