1번 문제 - 정주행 - 실전 유형 코딩 테스트 모의고사

배우기

03 사전 체험용 코딩테스트 해설

1번 문제 - 정주행

수열로 주어지는 데이터에서 꼭 따져야 하는 내용은 다음과 같습니다.

중복여부
정렬여부
원소의 범위
특이한 규칙성 혹은 순환성

문제에서 주어지는 수열이 가지는 이런 특징들로 인해 가능한 풀이들이 존재하니 꼭 확인하셔야 합니다. 문제의 설명과 입력 형식을 잘 보고 위와 같은 데이터의 특징을 꼭 캐치하시기 바랍니다.

이 문제는 실제로 정렬하여 풀 수도 있지만, 데이터에 중복이 없다는 성질을 이용해 효과적으로 풀 수 있습니다. 동영상 해설을 참고하여 아래의 두 풀이에 대한 소스코드를 이해하고 자신의 것으로 만들어봅시다.

//정렬을 사용한 O(N log N) 풀이
import java.util.*;
import java.io.*;

public class Main{
	public static final Scanner scanner = new Scanner(System.in);
	
	public static void main(String[] args)
	{
		//데이터 입력
		int n = scanner.nextInt();
		int[] data = new int[n];
		for(int i = 0 ; i < n ; i ++){
			data[i] = scanner.nextInt();
		}
		
		//데이터를 정렬한다 
		Arrays.sort(data);
		
		//정답이라고 가정한다
		boolean flag = true;
		for(int i = 0 ; i + 1 < n ; i ++){
			
			if(data[i] + 1 != data[i+1])
			{
				//왼쪽(i)숫자가 오른쪽 숫자(i+1)보다 1 작아야 한다.
				//주어진 조건을 한 번이라도 만족하지 않으면 연속적인 수열이 아니다
				flag = false;
				
				//이미 불가능하므로 더 이상 볼 필요 없다.
				break;
			}
		}
		

		if(flag){
			System.out.println("YES");
		}else{
			System.out.println("NO");
		}
	}
}

java

//정렬을 사용하지 않은 O(N) 풀이
//입력 데이터에 중복이 없기에 가능하다.
import java.util.*;
import java.io.*;

public class Main{
	public static final Scanner scanner = new Scanner(System.in);
	
	public static int getMaximum(int[] data){
		//배열의 최대값을 반환하는 함수 
		int max = data[0];
		for(int i = 0 ; i < data.length; i++){
			if(max < data[i]){
				max = data[i];
			}
		}
		return max;
	}
	
	public static int getMinimum(int[] data){
		//배열의 최소값을 반환하는 함수
		int min = data[0];
		for(int i = 0 ; i < data.length; i++){
			if(min > data[i]){
				min = data[i];
			}
		}
		return min;
	}
	
	public static void main(String[] args)
	{
		//데이터 입력
		int n = scanner.nextInt();
		int[] data = new int[n];
		for(int i = 0 ; i < n ; i ++){
			data[i] = scanner.nextInt();
		}
		
		//에피소드 중 가장 빠른 번호와 늦은 번호를 계산한다 
		int max = getMaximum(data);
		int min = getMinimum(data);
		
		//그 범위에 존재하는 편의 수를 계산한다 
		int btw = max - min + 1;
		
		//그 범위에 존재하는 편의 수와 내가 본 편의 수가 같다면 
		//그 사이의 모든 편의 수가 존재한다 => 자연수 이므로 연속적이다.
		if(btw == n){
			System.out.println("YES");
		}else{
			System.out.println("NO");	
		}
	}
}

java

실습 내용

시간이 흘러 지구는 2100년이 되었고, 웹툰 <소리의 마음>은 10만회 이상을 연재하며 매번 세계 기록을 갱신하고 있다. 대부분의 사람들에게 <소리의 마음>은 삶의 일부가 되었으며, 어린 학생들이 <소리의 마음>을 회차 순서에 맞게 쭉 정주행을 하는 모습을 쉽게 찾아 볼 수 있다.

하지만 조금 특이한 성격을 가진 승철이는 여태까지 <소리의 마음>을 순서에 구애받지 않고 읽어왔다. 그러던 어느날 승철이는 여태까지 자신이 본 에피소드의 번호들을 정렬하면 연속적인 수열로 표현될 수 있는지 궁금해졌다. 승철이는 <소리의 마음>을 다음과 같은 규칙을 지키며 읽었음이 보장된다.

승철이는 총 N화의 에피소드를 보았다.
승철이는 기억력이 좋기 때문에 똑같은 에피소드를 두번 보지는 않았다.

승철이가 여태까지 읽은 에피소드들의 번호가 차례로 주어질 때, 승철이가 본 에피소드들의 번호를 정렬하면 연속된 수열로 표현될 수 있는지 판별하는 프로그램을 작성하시오.

연속적인 수열이란 항상 i번째 숫자의 값이 (i+1)번째 숫자보다 1이 작은 정수로 이루어진 수열을 의미한다.

입력 형식

첫 줄에는 여태까지 승철이가 본 에피소드의 수 N이 주어진다. N은 1과 10만 사이의 자연수이다.

두 번째 줄에는 승철이가 본 에피소드의 번호들이 공백으로 구분되어 주어진다. 에피소드의 번호는 모두 서로 다르며 1과 100만 사이의 자연수이다.

출력 형식

승철이가 본 에피소드의 번호들이 연속적인 수열로 표현될 수 있다면 YES를 출력하고, 그렇지 않다면 NO를 출력한다.

문제 출처

구름EDU - 알고리즘 문제해결기법 입문

입/출력 예시

공백

줄 바꿈

탭

예시 1

입력

5
12534

출력

YES

예시 2

입력

5
12634

출력

⋇ 입출력 형식을 잘 지켜주세요

질문하기

추가 자료

추가 자료가 없습니다

여기서 새로운 학습 자료를 확인하세요!
선생님이 추가한 자료들을 바로 확인할 수 있어요.