Yong's Tech Story

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

문제 풀이 (JAVA) 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

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());
		long max = 0;
		long sum = 0;
		int N = Integer.parseInt(st.nextToken()); // 테스트케이스 수
		long[] arr;
		List<Long> list = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			sum = 0;
			int idx = 0;
			max = 0;
			int n = Integer.parseInt(br.readLine());
			arr = new long[n];
			st = new StringTokenizer(br.readLine(), " ");
			while (st.hasMoreTokens()) {
				arr[idx++] = Integer.parseInt(st.nextToken());
			}
			for (int j = n - 1; j >= 0; j--) {
				long curMoney = arr[j];
				if (curMoney > max) {
					max = curMoney;
				} else {
					sum += (max - curMoney);
				}
			}
			list.add(sum);
		}
		for (Long n : list) {
			System.out.println(n);
		}
	}

}

문제 풀이

1. 해당 문제는 그리디 알고리즘 문제로 항상 최댓값에서 팔아야 하기 때문에 배열의 끝부터 탐색을 해야 한다.

2. 백준 문제 제출시 4%에서 오류가 발생한다면 변수를 Integer가 아닌 Long 타입으로 변환해주어야 한다. 숫자의 범위가 32bit를 넘기 때문이라고 한다.

3. for문을 배열의 끝부터 탐색하여 현재 값이 max 값일 경우, 값을 교체해주고 max가 아닐 경우 max값과 현재값의 차를 이익으로 누적하면 된다.

결론

: 그리디 알고리즘에는 다양한 문제 접근 방식이 필요한듯 하다. 필자는 문제 접근 방식이 생각나지 않아 다른 사람의 코드를 참고하였다.

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

문제 풀이 (JAVA) 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int[][] arr; // 이차원 배열
	static int totalCnt; // 영역의 총 개수
	static boolean[][] visited; // 방문 여부 배열
	static int size = 0; // 영역의 넓이
	static int[] dx = { 1, 0, -1, 0 }; // 4방향 
	static int[] dy = { 0, 1, 0, -1 }; 
	static int M; // 행 개수
	static int N; // 열 개수

	public static void main(String[] args) throws IOException {
		// 영역 구하기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken());// 행 개수
		N = Integer.parseInt(st.nextToken());// 열 개수
		int K = Integer.parseInt(st.nextToken());// 입력 줄

		arr = new int[M][N];
		visited = new boolean[M][N];

		List<Integer> list = new ArrayList<>(); // 영역 넓이 저장 리스트

		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());

			int lx = Integer.parseInt(st.nextToken()); // 왼쪽 꼭짓점 X
			int ly = Integer.parseInt(st.nextToken()); // 왼쪽 꼭짓점 Y
			int rx = Integer.parseInt(st.nextToken()); // 오른쪽 꼭짓점 X
			int ry = Integer.parseInt(st.nextToken()); // 오른쪽 꼭짓점 Y
			
            for (int x = ly; x < ry; x++) { // 배열의 x는 꼭짓점 Y
				for (int y = lx; y < rx; y++) { // 배열의 y는 꼭짓점 X
					arr[x][y] = 1; // 색칠 된 도형의 경우 1로 선언
				}
			}
		}

		for (int x = 0; x < M; x++) {
			for (int y = 0; y < N; y++) {
  				// dfs에서 연결 되지 않은 0으로 x,y를 탐색한다.
				if (visited[x][y] == false && arr[x][y] == 0) {
					size = 1; // 현재 위치 사이즈 ==1 로 초기화
					visited[x][y] = true;
					totalCnt++; // if조건에 걸렸을때 하나의 영역의 시작이다.
					dfs(x, y);

					list.add(size); // dfs 종료 시 계산된 사이즈 추가
				}
			}
		}

		Collections.sort(list); // 오름차순 정렬

		System.out.println(totalCnt);
		for (Integer n : list) {
			System.out.print(n + " ");
		}
	}

	private static void dfs(int x, int y) {
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i]; // 다음 탐색할 X
			int ny = y + dy[i]; // 다음 탐색할 Y
			if (nx >= 0 && nx < M && ny >= 0 && ny < N && visited[nx][ny] == false && arr[nx][ny] == 0) {
				visited[nx][ny] = true;
				size++;
				dfs(nx, ny);
			}
		}
	}

}

문제 풀이

1. 해당 문제는 영역을 구하는 문제로 색칠된 도형의 넓이가 아닌 색칠하지 않은 도형의 넓이를 구하는 문제이다.

2. 문제에서 제시 되는 꼭짓점의 도형맵을 아래로 뒤집게 되면, 입력받은 꼭짓점과 이차원 배열의 (x,y)가 일치하게 된다.

3. 단, 오른쪽 꼭짓점의 경우, 입력 꼭짓점 rx-1, ry-1까지 반복문을 계산하여 도형의 넓이를 구해야 일치한다.

4. 나머지는 기존의 dfs 공식을 사용한다.(경계값 체크 필수)

결론

: 해당 문제는 dfs를 변형한 문제로, 꼭짓점의 위치를 이차원 배열의 위치와 매핑시켜 색칠 된 도형의 넓이를 구하는 것이 핵심이다. 입력 변수를 받아 arr를 잘 입력하였다면, 기존의 dfs 공식을 써서 풀 수 있다.

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

문제 풀이 (JAVA)

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

public class Main {

	public static void main(String[] args) {
		// 단어 뒤집기2
		Scanner input = new Scanner(System.in);

		String str = input.nextLine();
		String result = solution(str);
		System.out.print(result);
	}

	public static String solution(String s) {
		StringBuilder answer = new StringBuilder();
		Stack<Character> stack = new Stack<>();
		boolean flag = false; // tag가 아닐때 false
		for (int i = 0; i < s.length(); i++) {
			char ch = s.charAt(i);
			if (ch == '<') {
				flag = true; // tag일때 true
				// 태그전에 들어온 글자가 있을경우 스택 출력
				while (stack.isEmpty() != true) {
					answer.append(stack.pop());
				}
				answer.append(ch); // '<' 추가
				continue;
			} else if (ch == '>') {
				flag = false; // '>' 일때 tag가 종료됨을 알림
				answer.append(ch);
				continue;
			}
			// tag가 종료됬으나 tag 밖 글자가 공백을 가진다면 공백을 기준으로 역순출력해야하므로
			else if (flag == false && ch == ' ') {
				flag = false;
				// 스택에 들어온 값 역순 출력
				while (stack.isEmpty() != true) {
					answer.append(stack.pop());
				}
				answer.append(ch); // ' ' 추가
				continue;
			}
			if (flag == true) { // tag 안이라면
				answer.append(ch); // 정상출력
			} else if (flag == false) { // tag 밖이라면
				stack.push(ch); // 역순출력을 위한 스택 추가
				// 마지막 행 처리(index가 마지막이면 종료하므로.)
				if (i == s.length() - 1) {
					while (stack.isEmpty() != true) {
						answer.append(stack.pop());
					}
				}
			}

		}
		return answer.toString();
	}
}

다른 사람 풀이 코드(JAVA)

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

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(), " <>", true);
		StringBuilder answer = new StringBuilder();

		boolean flag = false;
		while (st.countTokens() > 0) {
			String token = st.nextToken();
			if (token.equals("<"))
				flag = true;
			else if (token.equals(">"))
				flag = false;

			if (flag)
				answer.append(token);
			else {
				StringBuilder tmp = new StringBuilder(token);
				answer.append(tmp.reverse());
			}
		}
		System.out.println(answer);
	}
}

주요 핵심 포인트

1. 해당 문제는 <tag> 일때 boolean 논리변수를 설정해주는 것이 가장 중요하다. 따라서 tag일때에는 정상 출력을 해야하므로 true, tag가 아닐때에는 스택에 쌓은 순서로 출력해야 하므로 false 논리변수를 설정한다.

2. '<' 가 들어왔을때 논리 변수를 tag임을 알리는 true로 변경하며, 스택에 값이 들어있다면 '<' 괄호 이전에 false로 설정되어 스택이 쌓였다는 의미로 스택이 있는 경우에는 먼저 값을 출력한 후 추가한다.

3. '>'가 들어왔을때 논리 변수를 tag가 아님을 알리는 false로 변경하며, 이후 문자를 스택에 저장한다.

4. '    '  공백의 경우, tag안의 글자 사이에 공백이 있거나, tag 밖 글자에 공백이 있을수 있으므로, tag 밖 글자가 공백일 경우에만 역순으로 출력한다.

5. 마지막 인덱스에서는 push()만 하고 종료될수 있으므로 , 마지막 인덱스일경우 스택의 모든 문자를 출력한다!! 처리 하지 않으면 마지막 문자가 나오지 않는다.

개선해야할 사항

1. 해당 문제는 풀지 못하여 다른 사람의 코드를 참조한 후, 다시 풀어보았다. 해당 문제를 풀지 못한 이유는 생각을 너무 짧게 하고 코딩에 돌입해서 그런듯 하다. 한번 꼬이기 시작하면 머리가 하애지기 때문에 사전에 로직을 어떻게 처리할지 머리속으로 충분히 정리한 후 구현하는 연습을 해야 할듯 하다. 다음부터는 정리를 다 끝내고 코딩을 해야겠다.

2. 다른 사람이 푼 코드는 StringTokenizer 생성자 함수에 구분자를 정규식처럼 사용하여 나누었다. 해당 코드는 스페이스바, < , >   3가지를 기준으로 구분하여 저장하겠다는 생성자 함수이다. 해당 식을 통해 '<' , '문자열', '>' 를 token으로 받아 쉽게 처리 할수 있음을 볼 수 있다. 또한 StringBuilder를 통해 .reverse() 함수를 사용하여 역순 정렬을 처리하였다. 해당 코드가 가장 클린한 코드로 보이며, 해당 코드 또한 참조할줄 알아야겠다.