[코딩테스트] 프로그래머스 1845, 단체사진 찍기

문제

https://programmers.co.kr/learn/courses/30/lessons/1835

코딩테스트 연습 - 단체사진 찍기

 

접근

• 8명의 프렌즈들을 한 줄로 세우는 경우의 수는 8! = 40320 가지입니다. 이는 8명에 대한 순열을 나타냅니다.
• 8명의 순열을 탐색하기 위해서 DFS 순회를 사용하였습니다.
• 만약 1번의 순회(한 줄로 세우기)가 완료되었다면 입력 받은 조건들(data)을 검사하고 조건에 맞지 않으면 카운트 하지 않습니다.

프렌즈들의 저장 구조는 해시 맵(position)을 사용하였습니다. Key는 프렌즈의 이름을 나타내며 Value는 프렌즈가 줄에서 몇번째에 위치하는지 나타내는 수입니다.

Map<String, Integer> position;
static final String[] FRIENDS = {"", "A", "C", "F", "J", "M", "N", "R", "T"};

for(String friend : FRIENDS)
{
    this.position.put(friend, 0);
}

 

프렌즈가 원하는 조건을 검사하는 로직은 다음과 같습니다.

	private boolean isSatisfiedInterval(int p1, int p2, String r, int interval)
	{
		if(r.equals("="))
		{
			// |p1 위치 - b 위치| = interval + 1
			return Math.abs(p1-p2) == interval + 1;
		}
		else if(r.equals(">"))
		{
			// |p1 위치 - b 위치| > interval + 1
			return Math.abs(p1-p2) > interval + 1;
		}
		else
		{
			// |p1 위치 - b 위치| < interval + 1
			return Math.abs(p1-p2) < interval + 1;
		}
	}

• p1, p2 : 프렌즈가 줄에서 몇번째에 위치하는지 나타내는 수
• r : '=', '>', '<' 중 하나를 나타내는 변수
• interval : 프렌즈들끼리 떨어져야 하는 간격을 나타내는 수

 

소스코드

import java.util.HashMap;
import java.util.Map;

public class Solution{
	boolean[] chosen;
	int[] nums;
	Map<String, Integer> position; 
	int person;
	int answer;
	String[] data;
	static final String[] FRIENDS = {"", "A", "C", "F", "J", "M", "N", "R", "T"};

	public Solution() {
		
	}
	
	public Solution(boolean[] chosen, int[] nums, int person, String[] data) {
		this.chosen = chosen;
		this.nums = nums;
		this.person = person;
		this.answer = 0;
		this.position = new HashMap<String, Integer>();
		this.data = data;
		
		
		for(String friend : FRIENDS)
		{
			this.position.put(friend, 0);
		}
	}
	
	public void DFS(int level)
	{
		if(level == person)
		{
			for(String condition : data)
			{
				int p1 = position.get(String.valueOf(condition.charAt(0)));
				int p2 = position.get(String.valueOf(condition.charAt(2)));
				String r = String.valueOf(condition.charAt(3));
				int interval = Integer.parseInt(String.valueOf(condition.charAt(4)));
				
				if(!isSatisfiedInterval(p1, p2, r, interval))
				{
					return;
				}
			}
			answer++;
		}
		else
		{
			for(int i = 1; i <= person; i++)
			{
				if(!chosen[i])
				{
					position.put(FRIENDS[level+1], nums[i]);
					chosen[i] = true;
					DFS(level + 1);
					chosen[i] = false;
				}
			}
		}
	}
	
	private boolean isSatisfiedInterval(int p1, int p2, String r, int interval)
	{
		if(r.equals("="))
		{
			// |p1 위치 - b 위치| = interval + 1
			return Math.abs(p1-p2) == interval + 1;
		}
		else if(r.equals(">"))
		{
			// |p1 위치 - b 위치| > interval + 1
			return Math.abs(p1-p2) > interval + 1;
		}
		else
		{
			// |p1 위치 - b 위치| < interval + 1
			return Math.abs(p1-p2) < interval + 1;
		}
	}
	
    public int solution(int n, String[] data) {
		int person = 8;
		boolean[] chosen = new boolean[person+1];
		int[] nums = {0, 1, 2, 3, 4, 5, 6, 7, 8};
        Solution solution = new Solution(chosen, nums, person, data);
        
        solution.DFS(0);
    	
        return solution.answer;
    }
}

 

References

https://data-make.tistory.com/350