[BOJ_2029] 음계 : 반례

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

2920번: 음계

solved.ac의 CLASS를 높이려고 하나씩 풀던 중 브론즈2 문제에서 틀렸다. 반례 찾는 법을 배우려는 중이라, 무조건 맞을 거라 생각했던 이 문제가 틀린 점을 적어놓으려고 한다.

 

처음 썼던 코드 :

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
		
		String answer = "ascending";
		for (int i = 0; i < 8; i++) {
			int n = Integer.parseInt(st.nextToken());
			if(n!=i+1 && n!=8-i) {
				answer = "mixed";
				break;
			}else if(n==8-i) answer = "descending";
		}
		System.out.println(answer);
	}

}

 

무조건 맞을 거라 생각했는데 틀렸다.

 

처음 풀면서 했던 생각 : 1 2 3 4 .. 이렇게 순서대로 가는 경우 n은 i+1이다. 8 7 6 5 .. 이렇게 반대로 가는 경우  n은 8-i이다. 즉, n이 i+1도 아니고, 8-i도 아니면 mixed이고, 중간에 break로 나가지 않으면서 8-i인 경우에는 descending이다.

 

문제점 : n이 i+1이거나 8-i임을 만족하면서 mixed인 경우가 있었다.

 

ascending   : 1 2 3 4 5 6 7 8
descending : 8 7 6 5 4 3 2 1
반례          : 1 7 3 5 4 6 2 8

 

따라서 위와 같은 코드는 반례에서 mixed가 아닌, descending을 답으로 내놓는다. 이를 보완하기 위해 첫번째 요소를 보고 판단한 후 for문에 들어가도록 바꾸었다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
		
		String answer = "ascending";
		boolean flag = true;
		int n = Integer.parseInt(st.nextToken());
		if(n!=1 && n!=8) {
			answer = "mixed";
		}else {
			if(n==8) {
				flag = false;
				answer = "descending";
			}
			for (int i = 1; i < 8; i++) {
				n = Integer.parseInt(st.nextToken());
				if(flag && n!=i+1) {
					answer = "mixed";
					break;
				}
				if(!flag && n!=8-i) {
					answer = "mixed";
					break;
				}
			}
		}
		
		System.out.println(answer);
	}

}

 

통과!

하지만 다음 코드가 더 짧고 쉬웠다. String 비교가 시간이 많이 걸리지만, 짧은 문장을 최대 두 번만 비교하면 되기 때문에 빨리 끝나는 것 같다. 위 코드와 시간이 동일하게 나왔다.

 

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));

		String str = br.readLine();
		String answer = "mixed";
		if(str.equals("1 2 3 4 5 6 7 8")) answer = "ascending";
		else if(str.equals("8 7 6 5 4 3 2 1")) answer = "descending";
		
		System.out.println(answer);
	}

}

 

느낀 점 : 정말 쉬운 문제였기 때문에 틀렸을 때 당황했다. 문제가 쉬워보인다고 단순하게 생각하고 끝내지 말고, '이렇게 풀면 틀릴 점이 있을까?'를 한 번 더 생각해봐야겠다.