[SWEA] 1208. [S/W 문제해결 기본] 1일차 - Flatten (Java)

문제 링크 / level: D3

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV139KOaABgCFAYh&categoryId=AV139KOaABgCFAYh&categoryType=CODE

SW Expert Academy

 

 

내가 생각한 풀이

누워있다가 갑자기 풀어봤다. 이번에도 S/W 문제해결 시리즈다. 한동안 알고리즘 문제 많이 안 풀다가 푸니까 또 재밌네🤔

 

문제의 핵심은

1. 상자의 높이만 알면 된다.

2. 덤프 횟수만큼 반복해서 매번 최고점과 최저점을 구한다. 그리고 그때의 간격을 구한다. 만약 0이나 1이라면 평탄화 작업이 완료된 것이므로 끝낸다.

가즈아!!! 개발자 만두!!!!!!

문제에 있는 그림은 이차원배열의 형태라서 나도 순간 자연스럽게 이차원배열부터 떠올리기는 했지만, 문제를 곰곰이 생각해보니 굳이 이차원배열이 필요없겠다-라는 생각이 들었다. 왜냐하면 상자의 높이만 알면 되거든!!🤗

즉, 일차원배열에 주어진 input값을 차례로 저장해주기만 하면 된다. 가로의 길이는 항상 100이니까 배열의 크기는 100으로 설정해주면 되겠다.

 

그리고 덤프 횟수가 주어진다. 횟수를 알기 때문에 일단 for문으로 돌려준다.

for문 안에서 해줘야하는 것들이 이 문제의 핵심인 평탄화 작업인데 순서는 아래와 같다.

1. 최고점과 최저점을 각각 구한다.

2. 두 값의 차이를 구한다. (만약 0이거나 1이면 평탄화 완료된 것이므로 종료. 아니라면 3번 진행)

3. 평탄화 작업을 한다.

이걸 계속 반복해주면 된다.

 

코드를 다 작성한 후에 자신있게 제출했더니 테스트케이스 중에 하나가 틀렸다. (두둥,,,😥)

뭐야 뭐야 뭐야.... SWEA 문제는 반례 찾기도 어렵단 말이야...

그런데 다행히 이 댓글을 보고 바로 문제를 해결할 수 있었다. (감사합니다. 따봉 눌렀읍니다😎👍)

 

저 테스트케이스를 돌려보니 내 코드에서는 답이 2가 나왔다.

즉, 평탄화 작업을 먼저 수행한 후에 최고점과 최저점을 구해서 그 두 값의 차이를 구하고 0과 1인지 아닌지 판단하는 것이 핵심이었다.

 

나는 두 값의 차이부터 구한 후에 평탄화 작업을 수행했기 때문에 이런 문제가 발생했던 것! 즉, 문제를 제대로 이해하지 못한 것으로 볼 수도 있다. 흐규흐규😂

만약 테스트케이스 중 6번의 값이 15가 나왔다면 이러한 로직 때문에 틀렸다고 보면 될 것 같다. 코드를 수정한 후에 제출해보니 정답은 14인 듯.

 

// 핵심 코드
// 덤프 수행 시작
for (int i = 0; i <= dump; i++) {
	// 평탄화 작업
	if (i != 0) {
		map[max_idx]--;
		map[min_idx]++;
	}
	max = 0;
	min = 101;
	for (int j = 0; j < 100; j++) {
		// 최고점 찾기
		if (max < map[j]) {
			max = map[j];
			max_idx = j;
		}
		// 최저점 찾기
		if (min > map[j]) {
			min = map[j];
			min_idx = j;
		}
	}
	diff = max - min; // 최고점과 최저점의 높이차이
	if (diff == 0 || diff == 1) { // 만약 평탄화 작업 완료시
		break; // 끝내기.
	}
}

 

겨우 겨우 쥐어짜낸 코드.

 

평탄화 작업을 먼저 하도록 하면서도 최고점과 최저점을 한 번만 구하도록 하려니 은근히 생각이 복잡해졌다.

고민 끝에 for문을 돌 때 맨 처음에는 평탄화 작업을 수행하지 않고 넘어가도록 하고, 그 다음번부터 평탄화 작업을 진행시켰다. 이렇게 하려면 for문의 조건문을 i < dump가 아닌 i <= dump로 해주어야 한다. (왜냐하면 만약 i < dump로 했을 때는 dump 횟수가 1이라면 평탄화 작업을 하지 않고 끝나버리니까)

 

어디 좀 적으면서 하면 좋았을걸 머리로만 생각하려니 힘들었다. 머리가 많이 굳었나봐...^_^

그래도 다행히 해결 완료!

아자! 성공이다!!!

왜인지는 모르겠지만 내 실행시간이 좀 적게 걸린 편이고, 메모리도 적게 쓴 편이라 더욱 뿌듯하다.😁

 

 

💌 전체 코드 보기:

https://github.com/psS2mj/Problem_Solving_SWEA_by_JAVA/blob/master/D3/Solution_1208_Flatten.java

psS2mj/Problem_Solving_SWEA_by_JAVA