안전지대

프로그래머스 / Level 0 / 안전지대

• 2차원 배열 문제라는 건, dx (상하로 이동하는 칸 수), dy(좌우로 이동하는 칸 수) 리스트를 만들어서 인접 칸을 체크해야 한다는 뜻
• 인접 칸을 확인할 때, 2차원 배열의 범위를 벗어나는지 안 벗어나는지 체크는 필수
  • 0 <= nx < N and 0 <= ny < N
• 시간 복잡도: 모든 칸을 이중 for문으로 순회하는 과정에서 $O(N^2)$

def solution(board):
    def check_danger(x, y):
        # 지뢰가 매설된 칸 및 인접 8칸을 위험 지역 처리
        dx = [-1, -1, -1, 0, 0, 1, 1, 1]
        dy = [-1, 0, 1, -1, 1, -1, 0, 1]
        
        # 지뢰가 매설된 칸
        safe[x][y] = False

        # 인접 8칸
        for k in range(8):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < N and 0 <= ny < N:
                safe[nx][ny] = False
    
    N = len(board)              # 배열의 한 변 길이
    safe = [[True] * N for _ in range(N)]   # 안전: True, 위험: False
    
    # 모든 칸 순회
    for i in range(N):
        for j in range(N):
            # 지뢰를 발견하면, 해당 칸 및 인접 8칸을 위험 처리
            if board[i][j] == 1:
                check_danger(i, j)
    
    # safe인 칸 확인
    answer = sum(sum(i for i in row) for row in safe)
    
    return answer 

성격 유형 검사하기

프로그래머스 / Level 1 / 성격 유형 검사하기

• 여러 가지 풀이법이 있겠지만, 딕셔너리를 이용해 각 유형별 점수를 저장하는 게 제일 편한 것 같음
• 시간 복잡도: $N$개의 문제를 채점하는 과정에서 for문을 사용하므로 $O(N)$

 def solution(survey, choices):
    # 각 유형별 점수
    points = {key: 0 for key in "RTCFJMAN"}
    
    # 점수 채점
    for i in range(len(survey)):
        left_i = survey[i][0]       # 비동의 시 점수가 오르는 유형
        right_i = survey[i][1]      # 동의 시 점수가 오르는 유형
        ch = choices[i]             # 사용자의 응답

        if ch <= 3:                 # 비동의 선택지
            points[left_i] += (4 - ch)
        elif ch >= 5:               # 동의 선택 시
            points[right_i] += (ch - 4)
        
        
    # 유형 확인
    answer = []
    answer.append("R" if points["R"] >= points["T"] else "T")
    answer.append("C" if points["C"] >= points["F"] else "F")
    answer.append("J" if points["J"] >= points["M"] else "M")
    answer.append("A" if points["A"] >= points["N"] else "N")
    return "".join(answer)

영어 끝말잇기

프로그래머스 / Level 2 / 영어 끝말잇기

• 이미 사용한 단어를 확인할 방법이 필요한데, $O(1)$ 안에 확인 가능한 집합형이 딱이지
• 누구의 차례인지는 나머지 연산으로, 그 사람의 몇 번째 차례인지는 몫 연산으로 확인
  • 이런 건 직접 보통 종이에 쓰면서 패턴 찾는 게 제일 속 편함.

• 시간 복잡도: 최대 $N$개의 단어를 for문으로 확인하므로 $O(N)$

def solution(n, words):
    used_words = set([words[0]])     # 이미 사용된 단어 (첫 단어를 포함)
    
    for i in range(1, len(words)):
        number = i % n + 1          # 누구의 차례?
        order = i // n + 1          # 몇 번째 차례?
        
        # 이미 사용한 단어가 아니면 탈락
        if words[i] in used_words:
            return [number, order]
        
        # 끝말잇기 조건 만족하지 않으면 탈락
        if words[i][0] != words[i - 1][-1]:
            return [number, order]
        
        # 이미 사용한 단어를 집합에 추가
        used_words.add(words[i])
        
    # 탈락자가 없음
    return [0, 0]