[BOJ] 1138번 한 줄로 서기

문제

www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

풀이

1) 처음에 짠 비효율적인 코드 (메모리 : 20128KB, 시간 : 616ms)

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static int[] left_bigger,tmp,heights;
	static boolean visited[],chk;
	static void dfs(int st, int depth, int std) {
		if(depth==std) {
//			for(int i=1;i<=N;i++)
//				System.out.print(tmp[i]+" ");
//			System.out.println();
			if(left_bigger[tmp[1]]==0) {
				int tc=1;
				for(int i=2;i<=N;i++) {
					int height = tmp[i];
					int cnt=0;
					for(int j=i-1;j>0;j--) {
						if(tmp[j]>height)
							cnt++;
					}
					if(cnt==left_bigger[height])
						tc++;
				}
				if(tc==N) {
					chk = true;
					for(int i=1;i<=N;i++)
						System.out.print(tmp[i]+" ");
				}
			}
			return;
		}
		for(int i=1;i<=N;i++) {
			if(!visited[i]) {
				visited[i] = true;
				tmp[depth] = heights[i];
				dfs(i+1,depth+1,std);
				visited[i] = false;
			}
		}
	}
	public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	StringBuilder sb = new StringBuilder();
    	N = Integer.parseInt(br.readLine());
    	left_bigger = new int[N+1];
    	tmp = new int[N+1];
    	heights = new int[N+1];
    	visited = new boolean[N+1];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=1;i<=N;i++) {
    		left_bigger[i] = Integer.parseInt(st.nextToken());
    		heights[i] = i;
    	}
    		
    	
    	//계산
    	dfs(1,1,N+1);
	}
} 

 

2) 효율적인 코드(메모리 : 16352KB, 시간 : 152ms)

import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	StringBuilder sb = new StringBuilder();
    	int N = Integer.parseInt(br.readLine());
    	ArrayList<Integer> list = new ArrayList<Integer>();
    	ArrayList<Integer> left = new ArrayList<Integer>();
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++)
    		left.add(Integer.parseInt(st.nextToken()));
    	
    	//계산
    	for(int i=N;i>0;i--) {
    		list.add(left.get(i-1),i);
    	}
    	for(int num : list)
    		System.out.print(num+" ");
	}
}