알고리즘 유형2. 구현 feat. 유레카

구현

머릿속에 있는 알고리즘(사고)을 소스코드로 바꾸는 과정

전형적인 문제풀이과정이 아닌, 문제를 읽고 이해해서 문제가 뭘 원하는지 파악해야한다.

 

• 문제가 요구하는 내용을 이해해서 이걸 코드로 작성(다양한 방법이 있음)
• 시뮬레이션 : data 초기상태를 잘 받고, 규칙에 따를 수 있게 코드 작성 (시간의 흐름에 따라 데이터 수정등, 주로 반복문 사용)
• 문제를 꼼꼼히 읽어야함

 

이것이 코딩테스트다 CH04. 예제1

: n개의 방향을 입력받고, 방향에 따라 동서남북으로 이동 (단, 일정 범위를 넘어가는 방향은 무시), 최종적으로 도착한 좌표 출력

package 구현_ch04;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// BufferedReader, static
// String[] plans -> char[]
// x <-> y (y를 기준으로)
public class 상하좌우2 {
	static int n;
	static char[] plans;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		// while, for st.countTokens()
		int count = st.countTokens();
		plans = new char[count];

		for (int i = 0; i < count; i++) {
			plans[i] = st.nextToken().charAt(0);
		}

		// 풀이
		int y = 1, x = 1;
		// L, R, U, D에 따른 이동 방향
		// 이동 계획을 하나씩 확인
		for (int i = 0; i < count; i++) {

			int ny = y;
			int nx = x;

			switch (plans[i]) {
			case 'L': nx = nx - 1; break;
			case 'R': nx = nx + 1; break;
			case 'U': ny = ny - 1; break;
			case 'D': ny = ny + 1; break;
			}

			// 공간을 벗어나는 경우 무시
			if (ny < 1 || nx < 1 || ny > n || nx > n)
				continue;
			// 이동 수행
			y = ny;
			x = nx;
		}
		System.out.println(y + " " + x);
	}
}

/*
 5 
 R R R U D D
 
 3 4

 */

 

이것이 코딩테스트다 CH04. 예제2

: 00:00:00 ~ N:59:59까지의 모든 시각중 3이 하나라도 포함되어있는 모든 경우의 총합을 출력

package 구현_ch04;
import java.util.Scanner;
// 문자열로 처리하지 않고, 숫자로 처리하는 부분 OK
// 시, 분, 초를 나눠서 따로 처리하는 부분 OK
public class 시각2 {
	static int N, cnt;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        long start = System.nanoTime();
        for (int h = 0; h <= N; h++) {
            if (h % 10 == 3) {
            	cnt += 3600;
            	continue;
            }
            for (int m = 0; m < 60; m++) {
            	if (m / 10 == 3 || m % 10 == 3) {
            		cnt += 60;
            		continue;
            	}
            	for (int s = 0; s < 60; s++){
                	if (s / 10 == 3 || s % 10 == 3) cnt++;
                }
            }
        }
        
        long end = System.nanoTime();
        System.out.println(cnt);
        System.out.println(end - start);
    }

}
// 5 11475

추가
 || vs |, && vs &
 || : 한번 true가 나오면 나머지 뒤에거는 비교안함 && : 한번 false가 나오면 나머지 뒤에거는 비교안함
 | : 한번 true가 나와도 끝까지 모든걸 비교함 & : 한번 false가 나와도 끝까지 모든걸 비교함

이것이 코딩테스트다 CH04. 문제1 왕실의 나이트

: 8x8 체스판에서 나이트 주어진 위치 기준 움직일 수 있는 경우의 수 출력 (나이트는 L모양으로 움직임)

package 구현_ch04;

import java.util.Scanner;

public class 왕실의나이트2 {
	static int y, x, result;
	// 나이트가 이동할 수 있는 8가지 방향 정의
    static int[] dy = {-1, -2, -2, -1, 1, 2, 2, 1};
    static int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 현재 나이트의 위치 입력받기
        String inputData = sc.nextLine();
        y = inputData.charAt(1) - '0';
        x = inputData.charAt(0) - 'a' + 1;

        // 만약 무조건 8개로 이동할 수 있으면 미리 출력
        // if문을 미리 써서 손해라고 생각할 수 있지만,
        // if문 : 비교 4번, for문까지 확인 : 8 x 4 = 32 로 오히려 if문을 사용하는게 나을 수 있다.
        if (y > 2 && y < 7 && x > 2 && x < 7) {
        	System.out.println(8);
        	return;
        }
        
        // 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
        for (int d = 0; d < 8; d++) {
            // 이동하고자 하는 위치 확인
            int ny = y + dy[d];
            int nx = x + dx[d];
            
            // 해당 위치로 이동된다면 다음꺼 확인
            if (ny < 1 || nx < 1 || ny > 8 || nx > 8) continue;
            
            result += 1;
        }

        System.out.println(result);
    }
}

// a1 2

이것이 코딩테스트다 CH04. 문제2 게임개발

: n x m의 맵에서 (y, x) 위치의 캐릭터가 dir쪽을 바라보고 서있다.(0 : 북, 1 : 동, 2 : 남, 3 : 서)
맵에서 1은 바다, 0 은 육지일 때, 캐릭터가 움직일 수 없을 때까지 실행하고 최종 캐릭터가 방문한 칸을 출력한다.
1. 현재 위치, 현재 바라보는 방향기준 반시계방향으로 회전

2. 반시계 방향으로 회전 후 앞으로 1칸 이동 가능할 시(육지이거나 방문하지 않은 칸일 경우) 이동, 불가능하면 다시 반시계방향으로 회전하여 4방향 모두 탐색

3. 4방향 모두 탐색후 이동이 불가능하면 바라보는 방향을 유지한 채 뒤로 1칸이동

4. 만약 3단계에서 뒤로 이동해야하는데, 뒤쪽이 바다라면 움직임을 멈추고 방문했던 모든 칸의 개수 출력

package 구현_ch04;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 게임개발3 {
    static int n, m, y, x, dir, cnt;
    static boolean[][] visit;
    static int[][] map;
    
    // 북 -> 동 -> 남 -> 서 (시계방향)
    static int dy[] = { -1, 0, 1, 0 };
    static int dx[] = {  0, 1, 0,-1 };
    
    // 왼쪽 회전
    static void turn_left() {
//      dir--;
//      if( dir == - 1) dir = 3;
        if( --dir == - 1) dir = 3;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        map = new int[n][m];
        visit = new boolean[n][m];
        st = new StringTokenizer(br.readLine());
        
        y = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());
        dir = Integer.parseInt(st.nextToken());
        
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 풀이 - 시물레이션
        visit[y][x] = true;
        cnt = 1;
        int turn_time = 0; // 같은 위치에서 왼쪽으로 turn 몇 번 했는지 체크 이동하면 0 초기화 
        
        while(true) {
            // 왼쪽 turn
            turn_left();
            
            // turn 한 왼쪽으로 방문할 수 있으면 방문
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            if( ! visit[ny][nx] && map[ny][nx] == 0 ) {
                visit[ny][nx] = true;
                
                y = ny;
                x = nx;
                
                cnt++;
                turn_time = 0;
            }else { // 방문할 수 없으면 다음 turn 체크
                turn_time++;
                
                if( turn_time == 4 ) { // 네 방향 모두 방문할 수 없으면
                    
                    ny = y - dy[dir];
                    nx = x - dx[dir];
                    
                    if( map[ny][nx] == 0 ) { // 뒤로 갈 수 있으면 이동
                        y = ny;
                        x = nx;
                    }else { // 뒤로 갈 수 없으면 이동 종료
                        break;
                    }
                    
                    turn_time = 0;
                }
            }
        }
        System.out.println(cnt);
    }
}
/*
4 4
1 1 0
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1
3
*/

 

추가 문제 : 백준 1158

https://www.acmicpc.net/problem/1158

 

: 요세푸스 문제

1~n번까지의 사람이 원으로 앉아있다. 주어진 k번째사람을 제거하고, 남은 사람끼리 다시 원을 이룬다. n명 모두 제거될 때까지 계속하고, 제거된 순서대로 출력한다.

package 구현_ch04;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BaekJoon_1158 {
	static int n, k, turn;
	static int[] num; // n명의 사람 순서

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		num = new int[n+1];	// i == 살아있는 사람, 0 == 제거된 사람
		turn = 1;

		System.out.print("<");

		for (int i = 0; i < n+1; i++) {
			num[i] = i;
		}
		
		for (int i = 0; i < n; i++) { // 0 1 2 3 4 5 6 7
			int count = 0;
			
			// 인덱스 찾기
			while (true) {
				//System.out.println(turn + "while");
				if (num[turn] != 0)
					count++; // 해당 인덱스의 사람이 살아있다면
				if (count == k)
					break;
				turn = (turn + 1) % (n+1);
			}
			
			//System.out.println(turn + "밖");
			if (i == n-1)
				System.out.print((turn));
			else
				System.out.print((turn) + ", ");
			num[turn] = 0; // 해당 번호의 사람 제거
		}

		System.out.print(">");
	}

}

해당 문제는 linkedList로도 풀 수 있는데, 처음으로 접근한 방법이 배열이라 배열만 올렸다.