이것이 코딩테스트다 with 파이썬 | 구현 ①

---

구현이란?

문제를 보고 풀이를 생각하는건 쉽지만 막상 코드로 옮길 때의 어려운 문제를 뜻함
별도의 유형으로 다루지않지만 코딩 테스트에 빈번하게 출제되는 유형이라고 한다.

(!?!? 전공 과제하면서 빈번하게 느꼈던 감정이잖아?)

---

구현 알고리즘의 대표적인 예시

1) 상하좌우

문제 설명이 길기 때문에, 유튜브 강의로 나와있는 문제설명을 캡쳐해서 수록했다.
나동빈의 유튜브 강의 바로 가기

👇 답지를 보기 전 작성한 코드

N=int(input()) # 공간의 크기 N
path=input().split() # 이동할 경로
row=1 #행
col=1 #열
for i in range (0,len(path)):
  if path[i]=="L": #열을 한칸 이동
    if col==1:
      continue # 공간밖은 무시
    col-=1
  elif path[i]=="R": #열을 한칸 이동
    if col==N:
      continue
    col+=1
  elif path[i]=="U": #행을 한칸 이동
    if row==1:
      continue
    row-=1
  else: #path[i]=="D" #행을 한칸 이동
    if row==N:
      continue
    row+=1
print(row,col)

공간 밖의 경로는 무시한다는 조건을 제대로 보지못해서 실행결과와 예시답안이 달라서 당황했음
문제 조건을 꼼꼼하게 잘 살펴볼 것

📌답안 예시를 본 후 피드백
그리디 알고리즘의 거스름돈 예제 처럼 R,U,D,L과 그에 따른 거리이동을 리스트로 묶었으면 코드가 좀 더 간결했을 것같다.


👇 피드백 후 코드

N=int(input()) # 공간의 크기 N
path=input().split() # 이동할 경로
row=1 #행
col=1 #열
move_types_row=[0,0,-1,1]
move_types_col=[-1,1,0,0]
path_types=["L","R","U","D"]

for plan in path:
  for i in range(len(path_types)):
    if plan==path_types[i]:
      nr=row+move_types_row[i]
      nc=col+move_types_col[i]
  if nr>N or nr<1 or nc>N or nc<1:
    continue
  row=nr
  col=nc
print(row,col)

---

2) 시각

입력된 N을 바탕으로 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하여라

👇 답지를 보기 전 작성한 코드

N=int(input())
ct=0
for i in range(N+1):
  for j in range(60):
    for k in range(60):
      if i==3 or j==3 or k==3:
        ct+=1
print(ct)

📌답안 예시를 본 후 피드백
너무 단순하게 생각한게 독이였다.. 내가 쓴 코드로 돌리게되면, 3을 포함하는 경우지, 3이랑 같을 경우가 아니기때문에
13분, 23초 이런경우는 횟수에 포함이 되질 않는다.
13을 int형으로 볼게 아니라 str형으로 '13'이라는 문자열 중 '3'을 포함하는지에 대한 여부를 체크하면 된다.

👇 피드백 후 코드

N=int(input())
ct=0
for i in range(N+1):
  for j in range(60):
    for k in range(60):
      if '3' in str(i)+str(j)+str(k):
        #만약 23시 59분 28초라면 => 235928 로 된다
        ct+=1
print(ct)