본문 바로가기

# 프로그래밍 개발/04. 알고리즘 문제풀이

백준 알고리즘 2947번 나무조각 문제 풀이 코드 공개

반응형

문제

동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 또, 모든 숫자는 다섯 조각 중 하나에만 쓰여 있다.

동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만들려고 한다.

  1. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
  2. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
  3. 세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
  4. 네 번째 조각의 수가 다섯 번째 수보다 크다면, 둘의 위치를 서로 바꾼다.
  5. 만약 순서가 1, 2, 3, 4, 5 순서가 아니라면 1 단계로 다시 간다.

처음 조각의 순서가 주어졌을 때, 위치를 바꿀 때 마다 조각의 순서를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 조각에 쓰여 있는 수가 순서대로 주어진다. 숫자는 1보다 크거나 같고, 5보다 작거나 같으며, 중복되지 않는다. 처음 순서는 1, 2, 3, 4, 5가 아니다.

출력

두 조각의 순서가 바뀔때 마다 조각의 순서를 출력한다.

출처

Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #4 1번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013

알고리즘 분류

시간초가 결과가 있다는 것은 그만큼 문제나 코드가 지저분하다는 뜻이겠지.. 

최근 현업을 뛰다보니, 알고리즘 코드가 효율성도 물론 중요하겠지만 

어떻게든 동작하는 것이 무엇보다도 중요한 것 같다. 

 

그러니 저 시간초과도 그런 면에서는 맞는 답이 아닐까 싶다. 

일단 아래는 시간초과가 발생하지 않은 코드이다. 

#include <stdio.h>
#define swap(a,b) {int t= a; a = b; b = t;}
int main(void) 
{
	int arr[5];
	int i;
	int t = 0;

	for(i=0; i<5; i++)
		scanf("%d", &arr[i]);

	while(1)
	{
		for(i=0; i<4; i++)
		{
			if(arr[i]>arr[i+1])
			{
				swap(arr[i],arr[i+1]);
				printf("%d %d %d %d %d\n", arr[0], arr[1], arr[2], arr[3], arr[4]);
			}
		}
		for(int i = 0 ; i < 5; i++){
			if(arr[i] == i+1) t++;
			else break;
		}
		if(t == 5)
			break;
		else
			t = 0;
	}

	return 0;
}

 

그리고 아래는 시간초과가 발생된 정답코드이다. 

#include <stdio.h>

int main(void) // 버블정렬
{
	int arr[5];
	int i;
	int temp=0;

	for(i=0; i<5; i++)
		scanf("%d", &arr[i]);
	do
	{
		for(i=0; i<4; i++)
		{
			if(arr[i]>arr[i+1])
			{
				temp=arr[i+1];
				arr[i+1]=arr[i];
				arr[i]=temp;
				printf("%d %d %d %d %d \n", arr[0], arr[1], arr[2], arr[3], arr[4]);
			}
		}
		temp= (arr[1]>arr[0])||(arr[2]>arr[1])||(arr[3]>arr[2])||(arr[4]>arr[3]);
	} while(temp);

	return 0;
}

아래가 더 깔끔한것 같은데.. 아쉽다. 

반응형