[백준 10431번 JAVA] 줄세우기 (Stack으로 어렵게 풀고 실패하기)

백준 문제 

 

스택으로 어렵게 풀었다. 실버5 문제인데...ㅎ 

다들 for 로 풀었더라 🥲 이전에 비슷한 문제를 stack 자료구조 이용해서 풀었던 기억이 있어서 stack 이 딱 떠올랐는데...

stack 2개 만들어서 풀었는데 문제를 너무 어렵게 생각했나봄... (결론 이렇게 풀면 틀림)

 

내 코드 (틀렸다고 뜸)

<내 풀이>
Max 용 stack 을 만들어서 Max 스택에 값이 더 크면 stack 에 저장하고 size 체크하고 그렇게 풀어봄. 
stack push, pop, peek 하면서 더 번거롭게 풀었다. 

<정답>
for 문에 20개 숫자 모두 집어넣고, 
첫번째 숫자부터 본인보다 큰 수가 있는지 count 로 체크해서 풀자. 

package baekjoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class _10431 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int tc = Integer.parseInt(br.readLine());
		
		for( int i= 0; i < tc; i++ )
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int count = 0;
			String caseNum = st.nextToken(); // 1, 2, 3, 4
			
			Stack<Integer> stack = new Stack<>();
			Stack<Integer> Maxstack = new Stack<>();

			for ( int j = 0; j < 20; j++ )
			{
				int student = Integer.parseInt(st.nextToken());
				
				if( ! Maxstack.isEmpty() &&  ( Maxstack.peek() > student) )
				{
					count += stack.size() + Maxstack.size();
					stack.push(student);
				} else if ( ! Maxstack.isEmpty() && ( Maxstack.peek() < student) )
				{
					//걸음 이동 x 
					stack.push(Maxstack.pop());
					Maxstack.push(student); 
				} else if ( Maxstack.isEmpty() )
				{
					Maxstack.push(student);
				}
			}

			bw.write(caseNum + " " + count + "\n");
		}
		
		br.close();
		bw.flush();
		bw.close();
		
		
	}
}

 

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

//줄세우기 
/**
 * 1 ~ 20 
 * 같은 키는 없다. 
 * 아무나 한 명. 
 * 자기 앞에 자기보다 키가 큰 학생이 1명 이상이라도 있다면, 그중 가장 앞에 있는 학생 앞에 선다. 
 * 이때, 가장 앞에 있던 a 부터 그 뒤에 모든 학생들은 한 발씩 뒤로 물러난다. 
 * -> 결국 오름차순으로 줄을 설 수 있다. 
 * 
 * 학생들이 뒤로 물러난 걸음 수의 총합 
 * 
 * stack 에 쌓고, 그 값을 비교. stack size 를 누적 
 * 
 */
public class _10431 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int tc = Integer.parseInt(br.readLine());
		

		
		for( int i= 0; i < tc; i++ )
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			String caseNum = st.nextToken(); // 1, 2, 3, 4
			
			int [] arr = new int[20];
			for ( int j =0; j < 20; j ++)
			{
				arr[j] = Integer.parseInt(st.nextToken());
			}
			
			int count = 0; 
			for ( int j =0; j < 20; j++ )
			{
				for ( int k=j+1; k<20; k++ )
				{
					if( arr[j] > arr[k])
					{
						count++;
					}
				}
			}
			
			bw.write(caseNum + " " + count + "\n");
			
		}
		
		br.close();
		bw.flush();
		bw.close();
		
		
	}
}