크레인 인형뽑기, 완주하지 못한 선수

2020-04-14 알고리즘 문제풀이 스터디

• 학습 시간: 총 18:30 ~ 20:30까지 약 2시간
• 풀이한 문제 수: 2
• 문제 난이도: 프로그래머스 기준 Level1
• 문제풀이 사이트: 프로그래머스
  (출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges)

 

---

1. 2019 카카오 개발자 겨울 인턴십 - 크레인 인형뽑기 게임

문제 정의

0. 인형이 들어 있는 2차원 배열 board
1. 인형이 들어 있는 곳은 1~100까지의 정수
2. 인형이 들어 있지 않는 곳은 0
3. 크레인이 가리키는 인형의 위치 값이 들어 있는 배열 moves
4. 위치 값은 board의 열 번호 (moves[i] - 1)
5. 크레인이 인형을 꺼내면 그 자리는 0
6. 꺼낸 인형은 바구니에 담긴다
7. 바구니는 1차원 배열 box
8. 인형은 아래에서부터 차곡차곡 쌓인다.
9. 만약 동일한 인형 두 개가 연속해서 쌓이면 두 인형은 사라짐.
10. 사라진 인형의 개수를 저장하여 출력

문제 풀이

코드

def solution(board, moves):
    
    box = []
    result = 0

    for move in moves:
        for yul in board: 
            find = yul[move-1]  
            if find != 0:
                if len(box) != 0 and box[-1] == find:
                    box.pop()    
                    result += 2  
                else:
                    box.append(find)
                    
                yul[move-1] = 0
                break
                
    answer = result
    return answer

코드 with 주석

def solution(board, moves):
    
    box = []
    result = 0

    for move in moves:  # 크레인의 위치 값들을 순회한다.
        
        for yul in board:  # 인형이 담긴 판을 순회한다. (yul = board의 열 값)
            
            find = yul[move-1]  # 변수 find에 크레인의 위치를 저장
            
            if find != 0:  # 만약 크레인이 가리키는 위치에 인형이 있으면
            
                # 만약 현재 찾은 인형과, box 배열에 가장 최근에 넣은 인형이 같으면 
                if len(box) != 0 and box[-1] == find:
                    box.pop()    # box 배열에 가장 최근에 넣은 인형을 삭제
                    result += 2  # result 변수에 삭제한 인형의 개수를 저장
                else:
                # 그렇지 않으면 box에 인형을 삽입
                    box.append(find)
                              
                # 크레인이 인형을 꺼낸 자리는 빈 곳으로 만든다.
                yul[move-1] = 0
                
                # board 순회 종료
                break
                
    answer = result
    return answer

생각

스택의 개념을 떠올리면서 문제를 풀었다.

 

---

2. 완주하지 못한 선수

문제 정의

0. 마라톤 참가자 명단 배열 participant
1. 마라톤 완주자 명단 배열 completion
2. 마라톤에 완주하지 못한 사람은 항상 1명
3. 참가자 중에는 동명이인이 있을 수 있음.
4. 동명이인은 모두 완주했을 수도 있고, 한 명만 완주했을 수도 있고, 모두 완주하지 못했을 수도 있다.

문제 풀이

코드

def solution(participant, completion):
    
    hash_par = {}
    no_run = ''
    
    for c in completion:
        hash_par[c] = 0
    
    for c in completion:
        hash_par[c] += 1
        
    for p in participant:
        if p in hash_par and hash_par[p] > 0:
            hash_par[p] = hash_par[p] - 1
        elif p in hash_par and hash_par[p] == 0:
            no_run = p
        elif p not in hash_par:
            no_run = p       
    
    return no_run

코드 with 주석

def solution(participant, completion):
    
    # 완주자 명단 값을 키값으로 담는 dictionary 변수
    hash_par = {}
    
    # 완주하지 못한 사람을 담는 string 변수
    no_run = ''
  
  	# dictionary hash_par를 완주자 명단을 키 값으로 하여 각각 0으로 초기화.
    for c in completion:
        hash_par[c] = 0
    
    # 완주자 명단을 다시 순회하여 hash_par에 해당 키값마다 +1 (동명이인 체크)
    for c in completion:
        hash_par[c] += 1
        
    # 참가자 명단 순회    
    for p in participant:
    	
        # 참가자 p가 완주자 명단에 존재하고, 그 값이 0보다 크면
        if p in hash_par and hash_par[p] > 0:
        	
            # 해당 키값의 값을 -1
            hash_par[p] = hash_par[p] - 1
        
        # 참가자 p가 완주자 명단에 존재하고, 그 값이 0이면
        elif p in hash_par and hash_par[p] == 0:
        	
            # 완주하지 못한 동명이인
            no_run = p
        
        # 참가자 p가 완주자 명단에 존재하지 않으면
        elif p not in hash_par:
        
        	# 완주하지 못한 사람
            no_run = p       
    
    return no_run

생각

해쉬 맵의 개념을 생각하고 문제를 풀었다.