codejcd 기술 블로그

문제

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

분석/설계

최대 넓이를 가지는 가로 * 세로를 구하고 

최소 넓이를 가지는 가로*세로를 구하여 최대 넓이 - 최소 넓이 빼주고

거기에 참외수를 곱하여 방식으로 처음에 생각하고 접근하였습니다.

1. 입력받은 문자열을 각각의 문자로 쪼개 확인합니다.

2. 최대 넓이를 가지는 가로, 세로의 길이 각 입력 값을 받아 방향에 따라 각각의 최대 값을 구해주면 됩니다.

3. 최소 넓이는 꺽이는 부분을 고려하여, 아래와 같이 정의하고 i 위치에따른 이전 변과 다음 변의 방향이 같으면

    i는 최소 넓이를 구하는 가로 또는 세로 중에 하나이므로 이를 저장합니다.

4. 마지막으로 구해진 최대, 최소 가로와 세로 값 그리고 참외 수를 곱해서 결과 값을 구합니다.

구현 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int K = Integer.parseInt(br.readLine());
		int maxHeight = 0;
		int maxWidth = 0;
		int minHeight = 0;
		int minWidth = 0;
		
		int[] dirArr = new int[6];
		int[] distArr = new int[6];
		
		for(int i=0; i<6; i++) { // 1. 입력받은 문자열을 각각의 문자로 쪼개 확인합니다.
			String[] input = br.readLine().split(" ");
			dirArr[i] = Integer.parseInt(input[0]);
			distArr[i] = Integer.parseInt(input[1]);
			
            // 2. 최대 넓이를 가지는 가로, 세로의 길이 각 입력 값을 받아 방향에 따라 각각의 최대 값을 구해주면 됩니다.
			if (dirArr[i] == 1 || dirArr[i] == 2) { 
				maxWidth = Math.max(maxWidth, distArr[i]);
			} else {
				maxHeight = Math.max(maxHeight, distArr[i]);
			}
		}
			
        // 3. 최소 넓이는 꺽이는 부분을 고려하여, 아래와 같이 정의하고 i 위치에따른 이전 변과 다음 변의 방향이 같으면
        // i는 최소 넓이를 구하는 가로 또는 세로 중에 하나이므로 이를 저장합니다.
		for(int i=0; i<6; i++) { // 최소 넓이를 가진 넓이를 구한다.
			// i를 최소 넓이의 가로 또는 세로라고 가정한다.
			int before = (i+5) % 6; 
			int after  = (i+1) % 6;
			
			if (dirArr[before] == dirArr[after]) { // i 기준으로 이전과 다음에 나올 변의 방향이 같으면
				if (dirArr[i] == 1 || dirArr[i] == 2) { // 방향에 따라 가장 작은 크기 가로, 세로 
					minWidth = distArr[i];
				} else {
					minHeight = distArr[i];
				}
			}
		}
		
        // 4. 마지막으로 구해진 최대, 최소 가로와 세로 값 그리고 참외 수를 곱해서 결과 값을 구합니다.
		int result = (maxHeight * maxWidth - minHeight * minWidth) * K; // (최대 넓이 - 최소 넓이) * 참외 개수 
		System.out.println(result);
	}
}

정리

최소 넓이의 가로 세로를 어떤식으로 기준을 잡고 구할지가 쉽게 떠오르지 않습니다.

문제에 주어진 조건을 잘 확인하고 고민해봐야합니다.

참고

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

문제

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

분석/설계

회전을 할 각 라인의 개수와 구한 각 라인을 반복하여 회전시켜야합니다.

1. 입력받은 문자열을 각각의 문자로 쪼개 확인합니다.

2. 회전을 할 각 라인의 개수를 구합니다.

    2X2  = 2개, 4X4 = 2개, 5x4 = 2개, 6x4 = 2개....

    Math.min(N, M) / 2  

3. 구한 각 라인을 반복하여 회전시킵니다.

   이때 회전하는 방향을 유의해야하고 각 시작점(0,0) ... (1,1)는 임시 변수에 저장했다가 이동한 위치로 (1,0) ... (2,1)

   반복이 끝날때 값을 넣어줍니다. 

구현 코드

import java.util.Scanner;

public class Main {
	static int M, N, R; // 가로, 새로, 회전 수
	static int [][] arr;
	static int[] dx = {0, 1, 0, -1}; 
	static int[] dy = {1, 0, -1, 0};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 1. 입력받은 문자열을 각각의 문자로 쪼개 확인합니다.
		N = sc.nextInt();
		M = sc.nextInt();
		R = sc.nextInt();
		arr = new int[N][M];
		
		for (int i=0; i<N; i++) {
			for (int j=0; j<M; j++) {
				arr[i][j] = sc.nextInt(); 
			}
		}
		
        // 2. 회전을 할 각 라인의 개수를 구합니다.
		int line = Math.min(N, M) / 2;
		
        // 3. 구한 각 라인을 반복하여 회전시킵니다.
		for (int i=0; i<R; i++) { 
			for (int j=0; j<line; j++) { 
				int x = j;
				int y = j;
				int val = arr[x][y];
				int idx = 0;
				
				while(idx<4) {
					int mx = x + dx[idx];
					int my = y + dy[idx];
					
					if (mx >= j && mx < N-j && my >= j && my < M-j) {
						arr[x][y] = arr[mx][my];
						x = mx;
						y = my;
					} else {
						idx++;
					}	
				}
				arr[j+1][j] = val;
			}
		}
		
		for (int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				System.out.print(arr[i][j] + " ");
			}
			System.out.println();
		}
		
		sc.close();
	}
}

정리

각 라인 별로 어떻게 값 이동을 구현할지를 각 라인의 수를 어떻게 구할지 

처음 접하면 떠오르지 않습니다. 

기존 맵의 탐색하는 유형은 많이 만나봐서 그런 방식으로 접근을 했고,

각 라인의 범위를 침범하지 않은 채로 이동을 해야했기때문에 많은 고심을 한 문제입니다.

백준 사이트에 보면 이런 유형의 문제가 많으니 많이 접해보고 다른분들의 풀이도 보면 도움이 되지 않을까 싶습니다.

참고

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

문제

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

분석/설계

답이 여러개인 경우 땅의 높이가 가장 높은 것을 골라야한다는 것을 염두해두어야함.

1. 입력받은 문자열을 각각의 문자로 쪼개 확인합니다.

2. 맵 상에 블록 높이의 최소 값과 최대값을 구합니다.

3. 최소~최대 높이의 수 만큼 반복문을 만듭니다.

   3.1 맵의 크기만큼 반복문을 만들고 맵의 높이 - (최소 값~최대 높이 )를 차이를 구합니다.

   3.2 차이가 0보다 클 경우 시간과 인벤토리에 차이값을 더해줍니다.

   3.3 차이가 0보다 작을 경우 시간과 인벤토리에 차이값을 더하고 빼줍니다.

   3.4 구한 값들을 반복문이 끝날때까지 결과값에 갱신합니다.

4. 결과값을 출력합니다.

구현 코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
    	// 입력을 Scanner 로 받을 경우 시간 초과
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] nmb = br.readLine().split(" ");
        int N = Integer.parseInt(nmb[0]);
        int M = Integer.parseInt(nmb[1]);
        int B = Integer.parseInt(nmb[2]);
		int[][ ]map = new int[N][M];
		
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		
		for(int i=0; i<N; i++) { // 변수를 초기화 하면서 최대값, 최소값을 구한다.
            String[] mapRow = br.readLine().split(" ");
			for(int j=0; j<M; j++) {
				int input = Integer.parseInt(mapRow[j]);
				map[i][j] = input;
				max = Math.max(max, input);
				min = Math.min(min, input);
			}
		}
		
		int minTime = Integer.MAX_VALUE; 
		int height = 0; 
		
		for (int i=min; i<=max; i++) { // 최소~최대까지 루프
			int time = 0;
			int inventory = B;
			int diff = 0;
			
			for (int j=0; j<N; j++) {
				for (int k=0; k<M; k++) {
					if (map[j][k] > i) { // 값이 클 경우
						diff = map[j][k]-i; // 차이 값을 구함
						time += diff * 2; // 시간에 (+)
						inventory += diff; // 인벤토리에 (+)
					} else if(map[j][k] < i) { // 값이 작을 경우
						diff = i- map[j][k]; // 차이 값을 구함
						time += diff; // 시간에 (+)
						inventory -= diff; // 인벤토리에 (-)
					}
				}
			}
			
			if(inventory >= 0 && minTime >= time) { // 최소 시간과 높이를 갱신
				minTime = time;
				height = i;
			}
		}
		
		System.out.println(minTime + " " + height);
	}
}

정리

입력받을 시 Scanner를 사용할 경우 백준 채점 사이트에서 시간초과를 만나게됩니다.

Scanner 대신 BufferedReader를 통해 입력을 받아야합니다.

Scanner는 1KB 버퍼 BufferedReader 는 8KB 버퍼로 차이가 있기때문에 입력 값이 많을수록 성능 차이가 있습니다.

참고

https://dlee0129.tistory.com/238

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

문제

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

분석/설계

Stack 자료구조를 활용하여, 문제의 조건들을 구현 가능합니다.

1. 입력받은 문자열을 각각의 문자로 쪼개 확인합니다.

2. 문자의 각 괄호가 '(' , '[' 이면 2, 3을 곱해줍니다.

3. 문자의 괄호가 ')'의 경우

    3.1 스택이 비어있거나 '('이 없는 경우 결과 값을 0으로 수정.

    3.2 이전 문자 값이 '('  일 경우 결과 값에 더해주고, Stack에서 제거.

4. 문자의 괄호가 ']' 경우

    4.1 스택이 비어있거나 '['이 없는 경우 결과 값을 0으로 수정.

    4.2 이전 문자 값이 '['  일 경우 결과 값에 더해주고, Stack에서 제거.

구현 코드

import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		Stack<Character> stack = new Stack<>();
		
		int res = 0;
		int val = 1;
		
		for (int i=0; i<str.length(); i++) {
			char c = str.charAt(i);
			if (c == '(' ) {
				stack.push(c);
				val *= 2;
			} else if(c == '[') {
				stack.push(c);
				val *= 3;
			} else if(c == ')') {
				if(stack.isEmpty() || stack.peek() != '(') {
					res = 0;
					break;
				} else if(str.charAt(i-1) == '(') {
					res += val;
				}
				stack.pop();
				val /= 2;
			} else if(c == ']') {
				if(stack.isEmpty() || stack.peek() != '[') {
					res = 0;
					break;
				} else if(str.charAt(i-1) == '[') {
					res += val;
				}
				stack.pop();
				val /= 3;
			}
		}
		
		if(!stack.isEmpty()) {
			res = 0;
		} 
		System.out.println(res);
		sc.close();	
	}
}

정리

조건들을 잘 읽고 어떻게 구현할지 쪼개서 생각해봐야 합니다.

Java에서 Stack과 문자열 다루는 메서드들에 대해서는 익숙해질 필요가 있습니다.

• push(item): item 하나를 스택의 가장 윗부분에 삽입.
• peek(): 스택의 가장 위에 있는 항목을 반환.
• pop(): 스택에서 가장 위에 있는 항목을 삭제하고 해당 item을 반환.
• isEmpty(): 스택이 비어있는지 유무에 따라 true/false를 반환.

참고

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

알고리즘 문제를 구현한 코드와 정답을 비교해보도록 하겠습니다.

문제

알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어집니다.

이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에,

그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다.

입력 조건
문자열 S (1 <= S의 길이 <= 10000)

입력 예시1
K1KA5CB7

출력 예시1
ABCKK13

입력 예시2
AJKDLSI412K4JS9D

출력 예시2
ADDIJJJKKLSS20

구현을 위해 나눠서 필요한 것들을 생각해봅니다.

1. 문자열을 입력받기 위한 코드가 필요.

2. 입력받은 문자열은 알파벳 대문자와 숫자로 구성되는 제약이 있는데 알파벳을 오름차순으로 정렬 필요.

   따라서 알파벳과 숫자 분리 필요.

3. 분리한 숫자 문자열은 숫자로 변환하여 합을 구함.

4. 정렬된 알파벳 문자열과 숫자를 합친 문자열을 만들어 출력.

구현 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main  {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String S = scanner.next(); // 시스템 입력을 받아 문자열 저장 
		char tempArr[] = S.toCharArray(); // 문자열을 Char 형의 Array로 변환
		int num = 0; 
		String str = "";
		
		Arrays.sort(tempArr); // 오름 차순 정렬
		
		for(int i=0; i<tempArr.length; i++) {
			// 대문자 A~Z 일 경우에 문자열을 str 변수에 추가.
			if(tempArr[i] -'A' >= 0 && tempArr[i]-'Z' <= 0) {
				str += tempArr[i];
			} else { // 아닐 경우 숫자를 따로 더한다.
				num += tempArr[i] - '0';
			}
		}
		
		if(num != 0) { // 알파벳 단독 구성인 경우를 구분하여 출력
			System.out.println(str + num);
		} else {
			System.out.println(str);
		}
		scanner.close();
	}
}

정답 코드

import java.util.*;

public class Main {

    public static String str;
    public static ArrayList<Character> result = new ArrayList<Character>();
    public static int value = 0;

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

        // 문자를 하나씩 확인하며
        for (int i = 0; i < str.length(); i++) {
            // 알파벳인 경우 결과 리스트에 삽입
            if (Character.isLetter(str.charAt(i))) {
                result.add(str.charAt(i));
            }
            // 숫자는 따로 더하기
            else {
                value += str.charAt(i) - '0';
            }
        }

        // 알파벳을 오름차순으로 정렬
        Collections.sort(result);

        // 알파벳을 차례대로 출력
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i));
        }

        // 숫자가 하나라도 존재하는 경우 가장 뒤에 출력
        if (value != 0) System.out.print(value);
        System.out.println();
    }
}

비교

1. 정렬
제가 작성한 코드의 경우 문자열 입력 후 Char 형 Array 전환 후 바로 정렬했다는 점이고
정답의 경우 알파벳 문자를 분리하여 정렬하였습니다. 
따라서 여기서 정렬할 문자 길이에 따른 시간 차이가 발생합니다.

2. 알파벳 문자인지 확인하기 위한 코드
알파벳 문자인지 구분을 위해 Character isLetter 메소드를 사용했다는 점입니다.

3. for문 사용
제가 작성한 코드의 경우 알파벳 문자와 숫자 문자를 구분 및 변수에 저장하기 위해 1번 사용.
정답의 경우 알파벳 출력을 위해 for문을 한번 더 사용하여 총 2번을 사용합니다.

정리

정답에서 char문자 구분을 위해 사용한 메소드 외에 알파벳 문자만을 위한 메서드와 숫자를 구분하는 메서드가
있어서 정리해봅니다.

1. Character isLetter 메서드
    char 값이 문자인지 판단하여 true / false를 리턴.

2.  Character isDigit 메서드
    char 값이 숫자인지 판단하여 true / false를 리턴.

3.  Character isAlphabetic 메서드
    char 값이 알파벳 문자인지 판단하여 true / false를 리턴

참고

https://www.baeldung.com/java-character-isletter-isalphabetic
https://github.com/ndb796/python-for-coding-test/blob/master/12/2.java