2018 디지털 과거 Code+ 온라인 예선 문제풀이

• A
   첫 번째 문제는 메모들이 주어지고 각 메모에는 날짜가 YYYY/MM/DD, YYYY-MM-DD, YYYY년MM월DD일 형태로 반드시 1번 등장한다. 메모에 등장하는 날짜가 빠른 순서로 메모를 정렬한 후에 출력하여야 한다. 주의해야 할 것은 년도가 2자리일 수도 있고, 월이나 일이 05일이나 5일의 형태로 올 수가 있다. 
   각 메모별로 주어진 날짜를 잘 파싱하여야 하는데, 나는 구분자로 "/", "-", "년|월|일"을 검색하는 케이스를 나누고 구분자 앞, 뒤로 년도, 월, 일을 가져와 저장하는 방식으로 문제를 풀었다.
  
  

  import java.io.*;
  import java.util.*;
  
  public class Main {
  	public static void main(String[] args) throws Exception {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
  		List<Date> dates = new ArrayList<>();
  		while (true) {
  			String line = br.readLine();
  			if ("END".equals(line))
  				break;
  
  			StringTokenizer st = new StringTokenizer(line);
  			while (st.hasMoreTokens()) {
  				String word = st.nextToken();
  
  				if (word.contains("/")) {
  					int s = word.indexOf("/");
  					int e = word.indexOf("/", s + 1);
  					int f = e;
  					for (int i = e + 1; i < word.length(); i++) {
  						if (!('0' <= word.charAt(i) && word.charAt(i) <= '9')) {
  							f = i;
  							break;
  						}
  					}
  					if (f == e)
  						f = word.length();
  
  					if (s != -1 && e != -1) {
  						try {
  							int year = Integer.parseInt(word.substring(s - 2, s));
  							int month = Integer.parseInt(word.substring(s + 1, e));
  							int day = Integer.parseInt(word.substring(e + 1, f));
  							dates.add(new Date(year, month, day, line));
  							break;
  						} catch (Exception exception) {
  						}
  					}
  				}
  				if (word.contains("-")) {
  					int s = word.indexOf("-");
  					int e = word.indexOf("-", s + 1);
  					int f = e;
  					for (int i = e + 1; i < word.length(); i++) {
  						if (!('0' <= word.charAt(i) && word.charAt(i) <= '9')) {
  							f = i;
  							break;
  						}
  					}
  					if (f == e)
  						f = word.length();
  
  					if (s != -1 && e != -1) {
  						try {
  							int year = Integer.parseInt(word.substring(s - 2, s));
  							int month = Integer.parseInt(word.substring(s + 1, e));
  							int day = Integer.parseInt(word.substring(e + 1, f));
  
  							dates.add(new Date(year, month, day, line));
  							break;
  						} catch (Exception exception) {
  						}
  					}
  				}
  
  				if (word.contains("년") && word.contains("월") && word.contains("일")) {
  					int s = word.indexOf("년");
  					int e = word.indexOf("월", s + 1);
  					int f = word.indexOf("일", e + 1);
  
  					if (s != -1 && e != -1 && f != -1) {
  						try {
  							int year = Integer.parseInt(word.substring(s - 2, s));
  							int month = Integer.parseInt(word.substring(s + 1, e));
  							int day = Integer.parseInt(word.substring(e + 1, f));
  							dates.add(new Date(year, month, day, line));
  							break;
  						} catch (Exception exception) {
  						}
  					}
  				}
  			}
  		}
  
  		Collections.sort(dates, new Comparator<Date>() {
  			@Override
  			public int compare(Date o1, Date o2) {
  				if (o1.year == o2.year) {
  					if (o1.month == o2.month)
  						return Integer.compare(o1.day, o2.day);
  					return Integer.compare(o1.month, o2.month);
  				}
  				return Integer.compare(o1.year, o2.year);
  			}
  		});
  
  		for (Date date : dates) {
  			bw.write(date.content);
  			bw.write("\n");
  		}
  		bw.close();
  	}
  
  	private static class Date {
  		public int year, month, day;
  		public String content;
  
  		public Date(int year, int month, int day, String content) {
  			this.year = year;
  			this.month = month;
  			this.day = day;
  			this.content = content;
  		}
  	}
  }
  

  
  

• B
   두 번째 문제는 초깃값이 하나 주어지고, 각 자릿수마다 올 수 있는 최댓값이 주어진다. 각 자릿수의 수는 최댓값을 넘길 수 없고 더했을 때 자리올림이 발생한다. 이 때 초깃값에서 주어진 입력만큼 더했을 때 결과값을 출력하는 문제이다.
   예를 들어 주어진 수의 자릿수가 4자리이고, 각 자릿수마다 최댓값이 9 9 9 8이고 초깃값이 7793일 때 여기에 3000을 더하면 결과값이 얼마인지 묻는 문제이다. 이 예의 정답은 1126이다.
   가장 마지막 자릿수부터 1씩 더해가면서 최댓값을 넘을 때 자리올림을 해주는 방식으로 풀면, 주어진 입력이 최대 INT_MAX이기 때문에 시간초과에 걸릴 것이다. 초깃값에 더해야 할 입력이 정해져 있으므로, 각 자리마다 발생하는 자리올림또한 정해져 있다. 따라서 가장 마지막 자리부터 더해야 할 입력을 모두 더하고 최댓값으로 나누면 나머지가 해당 자리의 값이 되고, 몫이 자리올림이 된다.
  
  

  import java.io.*;
  import java.util.*;
  
  public class Main {
  	public static void main(String[] args) throws Exception {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer st = new StringTokenizer(br.readLine());
  		int N = Integer.parseInt(st.nextToken());
  		if (N < 1 || 8 < N)
  			exit();
  
  		st = new StringTokenizer(br.readLine());
  		int[] max = new int[N];
  		for (int i = 0; i < N; i++) {
  			max[i] = Integer.parseInt(st.nextToken());
  			if (max[i] < 0 || 9 < max[i])
  				exit();
  		}
  
  		st = new StringTokenizer(br.readLine());
  		int[] number = new int[N];
  		for (int i = 0; i < N; i++) {
  			number[i] = Integer.parseInt(st.nextToken());
  			if (number[i] < 0 || 9 < number[i])
  				exit();
  		}
  
  		for (int i = 0; i < N; i++)
  			if (max[i] < number[i])
  				exit();
  
  		int count = Integer.parseInt(br.readLine());
  		for (int i = N - 1; i >= 0; i--) {
  			int n = count + number[i];
  			number[i] = n % (max[i] + 1);
  			count = n / (max[i] + 1);
  		}
  
  		for (int i = 0; i < N; i++)
  			System.out.print(number[i]);
  	}
  
  	private static void exit() {
  		System.out.println(-1);
  		System.exit(0);
  	}
  }
  

  
  

• C
   세 번째 문제는 H*W 크기의 체스판에서 나이트(Knight)가 체스판의 어떤 위치로든 이동할 수 있으려면 최대 몇 번이 필요한지 묻는 문제이다. 체스판의 모든 자리를 이동할 수 있다면 T를 출력하고 아니면 F를 출력한다. 그리고 최대 이동횟수를 출력하여야 한다.
   이러한 유형은 전형적인 문제로 BFS로 풀 수 있다. 큐에 나이트가 이동할 수 있는 모든 자리를 넣고, 방문여부를 체크해주면서 큐에 원소가 없을 때 까지 반복한다. 큐에 원소를 넣을 때는 몇 번만에 이동했는지를 알아야 하므로 이동횟수 1을 증가시켜준다. BFS가 끝나면 체스판의 각 자리의 방문여부를 체크해서 방문한 적이 없는 자리가 존재하면 해당 H*W의 크기에서 나이트가 이동할 수 없는 자리가 있다는 것이고 F를 출력한다. 그리고 체스판에서 나이트가 최대로 이동할 수 있는 횟수는 BFS를 돌면서 증가시켜 주었던 이동횟수의 최댓값을 출력하면 된다.
   문제에서 나이트가 이미 이동한 위치로 다시 갈 수 있다고 하였는데, 이 조건 때문에 BFS를 돌 때 방문여부 체크를 안하면 안된다. 왜냐하면 나이트가 이동할 수 있는 위치는 정해져 있기 때문에 이미 이동한 위치에 다시 나이트가 이동한다고 하면 같은 자리를 계속 이동하게 될 것이다.
  
  

  import java.io.*;
  import java.util.*;
  
  public class Main {
  
  	private static final int[] dy = { -2, -2, -1, -1, 1, 1, 2, 2 };
  	private static final int[] dx = { -1, 1, -2, 2, -2, 2, -1, 1 };
  
  	public static void main(String[] args) throws Exception {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer st = new StringTokenizer(br.readLine());
  		int Y = 0;
  		int X = 0;
  		try {
  			Y = Integer.parseInt(st.nextToken());
  			X = Integer.parseInt(st.nextToken());
  		} catch (Exception e) {
  			exit();
  		}
  		if (Y < 2 || 50 < Y || X < 2 || 50 < X)
  			exit();
  
  		Queue<Node> q = new LinkedList<>();
  		boolean[][] visited = new boolean[Y][X];
  		q.add(new Node(0, 0, 0));
  		visited[0][0] = true;
  
  		int max = 0;
  		while (!q.isEmpty()) {
  			Node n = q.poll();
  			max = Math.max(max, n.count);
  
  			for (int i = 0; i < 8; i++) {
  				int y = n.y + dy[i];
  				int x = n.x + dx[i];
  				if (y < 0 || y >= Y || x < 0 || x >= X || visited[y][x])
  					continue;
  
  				q.add(new Node(y, x, n.count + 1));
  				visited[y][x] = true;
  			}
  		}
  
  		boolean check = true;
  		for (int y = 0; y < Y; y++)
  			for (int x = 0; x < X; x++)
  				if (!visited[y][x])
  					check = false;
  
  		System.out.print((check) ? "T" : "F");
  		System.out.print(max);
  	}
  
  	private static void exit() {
  		System.out.println(-1);
  		System.exit(0);
  	}
  
  	private static class Node {
  		public int y, x, count;
  
  		public Node(int y, int x, int count) {
  			this.y = y;
  			this.x = x;
  			this.count = count;
  		}
  	}
  }
  

  
  

• D
   마지막 문제는 0~20까지의 숫자가 무작위로 주어진다. 그리고 정수 하나가 주어지는데, 무작위로 주어진 숫자들 중 3개를 뽑아 더했을 때 이 수와 같은 경우 해당하는 숫자 3개를 출력하는 문제이다.
   주어진 숫자들은 총 21개이므로 3중 반복문을 통해 O(N^3)으로 구하여도 빠르게 구할 수 있다. 단 문제에서 일치하는 값을 출력할 때 오름차순으로 출력해야 하는 조건이 있으므로, 처음 입력을 받을 때 한번 정렬을 한 후에 앞에서부터 3개를 뽑는 3중 반복문을 구현하면 된다.
  
  

  import java.io.*;
  import java.util.*;
  
  public class Main {
  	public static void main(String[] args) throws Exception {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
  		StringTokenizer st = new StringTokenizer(br.readLine());
  		List<Integer> numbers = new ArrayList<>();
  		while (st.hasMoreTokens())
  			numbers.add(Integer.parseInt(st.nextToken()));
  		Collections.sort(numbers);
  
  		int target = Integer.parseInt(br.readLine());
  		List<Node> candidate = new ArrayList<>();
  		for (int i = 0; i < numbers.size(); i++) {
  			for (int j = i + 1; j < numbers.size(); j++) {
  				for (int k = j + 1; k < numbers.size(); k++) {
  					int A = numbers.get(i);
  					int B = numbers.get(j);
  					int C = numbers.get(k);
  					if (A + B + C == target)
  						candidate.add(new Node(A, B, C));
  				}
  			}
  		}
  
  		if (candidate.size() == 0)
  			exit();
  		for (Node node : candidate) {
  			bw.write(String.valueOf(node.A));
  			bw.write(" ");
  			bw.write(String.valueOf(node.B));
  			bw.write(" ");
  			bw.write(String.valueOf(node.C));
  			bw.write("\n");
  		}
  		bw.close();
  	}
  
  	private static void exit() {
  		System.out.print("NO");
  		System.exit(0);
  	}
  
  	private static class Node {
  		public int A, B, C;
  
  		public Node(int a, int b, int c) {
  			this.A = a;
  			this.B = b;
  			this.C = c;
  		}
  	}
  }