구현

<이것이 취업을 위한 코딩 테스트다>를 공부하며 정리한 내용입니다.

문제 특징

• 구현 : 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정
• 문제 해결 분야에선.. ‘풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제’
• 알고리즘은 간단한데 코드가 길어지는 문제… → 적절한 라이브러리를 사용해보자
• 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
• 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형
• 메모리 제한을 생각해보아야 함 → 파이썬의 경우 리스트의 크기 1,000만 이상만 아니면 괜찮다
• 시간 제한과 데이터의 개수 먼저 확인 → 어느 정도의 시간 복잡도의 알고리즘으로 작성할 것인지?

---

예제 - 상하좌우(시뮬레이션 유형)

여행가 A는 NxN 크기의 정사각형 공간 위에 서 있다. 이 공간은 1x1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 여행가 A는 상,하,좌,우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.

계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다. 각 문자의 의미는 다음과 같다.

• L : 왼쪽으로 한 칸 이동
• R : 오른쪽으로 한 칸 이동
• U : 위로 한 칸 이동
• D : 아래로 한 칸 이동

이때 여행가 A가 NxN 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1,1)의 위치에서 L 혹은 U를 만나면 무시된다.
계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1≤ N ≤ 100)
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 ≤ 이동 횟수 ≤ 100)

출력 조건

• 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X,Y)를 공백으로 구분하여 출력한다.

입력 예시

5

R R R U D D

출력 예시

3 4

---

해설

• 연산 횟수는 이동 횟수에 비례 → 이동 횟수가 N번이면 시간 복잡도는 O(N)
• 일련의 명령에 따라서 개체를 차례대로 이동시킴 → ‘시뮬레이션’ 유형

1. 내 풀이
   • 계획을 하나씩 꺼내서 선 실행 후 조건체크🍀
   • 조건체크시 4가지 경우를 하나씩 체크해줘야 함. → 조건문이 다했다…(조건문 부피가 크다는 뜻)

	n=int(input()) #공간의 크기 입력
	plan=input().split() #map 안하면 저절로 list가 됨.
    
   	x=1 #시작 좌표 
    y=1
    
    for i in plan:#계획 하나씩 꺼내기
        if i=='L': #일단 그대로 실행하고 봄.
            y-=1
        elif i=='R':
            y+=1
        elif i=='U':
            x-=1
        elif i=='D':
            x+=1
    
        if x==0: #실행했더니 n을 벗어나면 다시 원상복구 시키기
            x=1
        elif y==0:
            y=1
        elif x>n:
            x-=1
        elif y>n:
            y-=1
    
    print(x,y) #출력

2. 교재 풀이
   • 리스트를 활용하여 조건문 사용 줄임
   • 🍀임의의 변수에 결과를 저장해놓고, n 범위 벗어나면 그 값으로 갱신하지 않도록 설정

	n=int(input())
	x,y=1,1
	plans=input().split()

	#L, R, U, D에 따른 x,y에 대한 변위
	dx=[0,0,-1,1]
	dy=[-1,1,0,0]
	move_types=['L','R', 'U', 'D']

	#이동 계획을 하나씩 확인
	for plan in plans:
    	#for문을 이용해서 조건 검사해주기
    	for i in range(len(move_types)):
        	if plan==move_types[i]:
            	nx=x+dx[i] #임의의 변수에 결과 저장해놓기
            	ny=x+dy[i]
            
    	if nx<1 or ny<1 or nx>n or ny>n: #n을 벗어나면 x,y 갱신없이 지나가도록.
        c	ontinue #바로 아래 코드 무시
    	x,y=nx,ny #아니라면 저장한 결과 불러오기

	print(x,y)