[JAVA] 2564번 - 경비원

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

구현으로 풀면 된다.

근데 조건이 블록의 가장자리에만 상점이 들어갈 수 있다.

이말은 즉 저 경계를 일자로 쭉 펼쳐서 일차원에서 풀 수 있다는 것이다.

 

일자로 쭉 피면 0에서부터 시작해서 최대길이는 2*가로+2*세로 까지가 된다.

 

 

 

 

시간복잡도

O(N)이다

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. 각 방향에 따라 상점의 위치를 저장한다.

switch문으로 동/서/남/북일 때, 상점의 위치를 저장한다.

for(int i=0; i<=n; i++) {
        	st = new StringTokenizer(br.readLine());
        	
        	int dir = Integer.parseInt(st.nextToken());
        	int loc = Integer.parseInt(st.nextToken());
        	int tmp = 0;
        	
        	switch(dir) {
        	case 1: // 북쪽일때
        		tmp = loc;
        		break;     		
        	case 2: // 남쪽일때
        		tmp = w+h+w-loc;
        		break;
        	case 3: // 서쪽일때
        		tmp = w+h+w+h-loc;
        		break;      		
        	case 4: // 동쪽일때
        		tmp = w+loc;
        		break;       				
        	}
        	if(i<n) { //상점의 위치 입력받기
        		arr[i]=tmp;
        	}
        	else { //동근이 위치 입력받기
        		p = tmp;
        	}
        }

 

2. 시계방향일때와 반시계방향일때 각각 거리를 비교하여 최단거리를 출력

for (int i = 0; i<arr.length; i++) {
            int path1 = Math.abs(p - arr[i]);
            int path2 = 2 * w + 2 * h - path1;
            cnt += Math.min(path1, path2);
        }

 

 

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
   public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));       
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(br.readLine());
        int cnt=0, p = 0;
        
        int[] arr = new int[n];
        
        for(int i=0; i<=n; i++) {
        	st = new StringTokenizer(br.readLine());
        	
        	int dir = Integer.parseInt(st.nextToken());
        	int loc = Integer.parseInt(st.nextToken());
        	int tmp = 0;
        	
        	switch(dir) {
        	case 1: // 북쪽일때
        		tmp = loc;
        		break;     		
        	case 2: // 남쪽일때
        		tmp = w+h+w-loc;
        		break;
        	case 3: // 서쪽일때
        		tmp = w+h+w+h-loc;
        		break;      		
        	case 4: // 동쪽일때
        		tmp = w+loc;
        		break;       				
        	}
        	if(i<n) { //상점의 위치 입력받기
        		arr[i]=tmp;
        	}
        	else { //동근이 위치 입력받기
        		p = tmp;
        	}
        }
        
        for (int i = 0; i<arr.length; i++) {
            int path1 = Math.abs(p - arr[i]);
            int path2 = 2 * w + 2 * h - path1;
            cnt += Math.min(path1, path2);
        }
        
        System.out.println(cnt);
  
    }  
}