220901에 보았던 코딩테스트 문제 4개 관련 코드 및 풀이

1. 좌석 구매

문제 안내

상세 설명

• 아래 그림과 같이 공연을 관람하기 위한 100,000 x 100,000 크기의 격자 모양의 좌석이 있습니다.
• 이 공연장의 표를 구매하기 위해 K명의 관람객이 매표소에 한 줄로 서 있습니다. 이때, 관람객은 자신이 원하는 좌석에만 공연을 관람하려고 합니다.
• 각 관람객은 매표소에서 자신이 원하는 좌석의 좌표를 말하고, 아직 아무도 구매하지 않은 좌석이면 해당 좌석의 표를 삽니다. 그러나 만약 이미 구매된 좌석이면 공연 관람을 포기하고 집으로 돌아갑니다.
• 줄을 서 있는 사람들이 구매하려는 좌석의 좌표가 순서대로 담겨있는 배열 seat가 매개변수로 주어질 때, 표를 구매하는데 성공한 사람의 수를 return하도록 solution 함수를 완성해주세요.
  

제한사항

• 줄을 서 있는 관람객의 수는 1 이상 100,000 이하입니다.
• seat에는 관람객이 구매하려는 좌석의 좌표가 가장 앞에 있는 사람부터 순서대로 들어있습니다.
• seat의 각 원소는 관람객이 구매하려는 좌석의 좌표이며, [가로 좌표, 세로 좌표] 순입니다.
• 가로 좌표, 세로 좌표의 범위는 1 이상 100,000 이하의 정수입니다.

입출력 예

seat	result
[[1,1],[2,2],[3,3]]	3
[[1,1],[2,1],[1,2],[3,4],[2,1],[2,1]]	4

입출력 예 설명

• 입출력 예 #1
  • 가장 앞사람부터 순서대로 (1,1), (2,2), (3,3) 위치의 좌석을 구매하여 총 3명의 관람객이 구매에 성공했습니다.
• 입출력 예 #2
  • 가장 앞사람부터 순서대로 (1,1), (2,1), (1,2), (3,4) 위치의 좌석을 구매하였습니다.
  • 5,6번째 관람객이 구매하려는 좌석은 2번째 관람객이 이미 구매하였으므로 5,6번째 관람객은 집으로 돌아갑니다.
  • 따라서 총 4명의 관람객이 구매에 성공했습니다.

풀이 및 코드

풀이

로직 설명

1. 주어진 구매 예정 좌석 좌표 리스트를 정렬해야겠다!
   → why? 정렬하게 되면, 동일 좌표들끼리 인접해있을 것이기 때문에 제일 앞에 있는 좌표만 구매한 것으로 처리하기 위해서!!

seat = [[1,2], [2,2], [1,2], [2,3], [1,2]] 
seat.sort
# seat = [[1,2], [1,2], [1,2], [2,2], [2,3]] 
# → [1,2]에 해당하는 좌석은 맨 앞의 것만 구매한 것으로 간주하여 카운트하면 됨. 
# 그 다음의 두 개는 따로 연산하지 않고 넘어감!

2. 여러개 들어 있는 동일 좌표는 어떻게 구분할 것인가?
   → target이라는 변수를 지정하여 seat 리스트에서 순서대로 추출하게 될 각 좌표들이 target과 동일한지 판단하여 구분

3. 좌석을 구매할 때 카운트는 어떻게 할 것인가?
   → 동적 계획법 사용.

   • dp라고 하는 0으로 구성된 리스트를 생성 후, 좌석을 구매하게 되면 해당 좌표의 index에 해당하는 dp 내의 요소를 1로 변경해줌.
   • 마지막 좌석까지 확인 후, dp의 요소를 모두 더하면 그 값이 바로 좌석의 총 구매 갯수

코드 구현 및 라인별 풀이

Code

def solution(seat):	

	seat.sort()
    
	length = len(seat)
	dp = [0] * length
	target = None
    
	for i in range(length):	
		if seat[i] != target:
			dp[i] = 1
			target = seat[i]
		else:
			continue
            
	return sum(dp)

관련 풀이

※ 잘 안보이는 경우, 그림 우클릭 → '새 탭에서 이미지 열기' 클릭하여 확인하면 됨!

회고

• 맨 처음 구현한 코드는 아래와 같았다.
• 그런데, 해당 코드는 총 20개의 테스트 케이스 중 하단 4개의 케이스에 대해 시간초과가 발생하였다.
  • 아마도 if seat[i] not in success 부분에서 success 리스트를 모두 탐색하기 때문에 시간 초과가 발생하는 것으로 생각되었다.
    → target이라는 변수를 별도로 두어서 현재 순서의 좌표와 target을 비교하는 형태로 코드를 개선
  • 또한, success.append(seat[i]) 부분에서도 append를 하게 되면 메모리인가 시간인가를 더 잡아먹는다고 어디서 주워들었던거 같은데.. 이 부분은 정확하지 않아서 스터디 하면서 다른 분들께 물어볼 생각이다.
    → 동적계획법을 사용하여 메모이제이션을 통해 실행 속도를 향상시키는 방향으로 코드를 개선

def solution(seat):	

	seat.sort()
    
    length = len(seat)
	success = []
    
	for i in range(length):	
		if seat[i] not in success:
			success.append(seat[i])
            
	return len(success)

• 다른 분들 풀이에 대해서는 나중에 시간될 때 학습해볼 예정!