LIG넥스원 코딩테스트 빈출 유형 풀이 [Python]

• LIG넥스원의 코딩테스트는 프로그래머스에서 진행되며, 사용 가능 언어로는 C, C++, Java, Python이 있다.
• 시험시간은 120분이며, 총 3문제가 출제된다.
• 빈출유형에 해당하는 문제 목록은 여기서 참고하였다.

1. 대피소 (링크)

🔎 문제유형 : 구현, 브루트포스 알고리즘, 시뮬레이션

import sys
input = sys.stdin.readline
from itertools import combinations as comb

n, k = map(int, input().split())
arr = list(tuple(map(int, input().split())) for _ in range(n))

def get_dist(xi, yi, xj, yj):
    return abs(xi - xj) + abs(yi - yj)

min_dist = float("inf")

cmb = comb(arr, k)
for c in cmb:
    dist = list()
    for hx, hy in arr:
        if (hx, hy) not in c:
            tmp = list()
            for sx, sy in c:
                tmp.append(get_dist(hx, hy, sx, sy))
            dist.append(min(tmp))
    if dist:
        min_dist = min(min_dist, max(dist))

print(min_dist if min_dist < float("inf") else 0)

처음 제출에서는 답이 float("inf")일 때 처리를 해주지 않아서 5점밖에 받지 못했다.

---

2. 문자열 폭발 (링크)

🔎 문제유형 : 자료구조, 문자열, 스택

import sys
input = sys.stdin.readline

s = input().strip()
b = input().strip()

stack = list()
bomb = list()

for c in s:
    if c not in b:
        if bomb:
            stack.extend(bomb)
            bomb.clear()
        stack.append(c)
    else:
        bomb.append(c)
        if ''.join(bomb[-len(b):]) == b:
            for _ in range(len(b)):
                bomb.pop()
                
while bomb:
    if ''.join(bomb[-len(b):]) == b:
        for _ in range(len(b)):
            bomb.pop()
    else:
        break  
if bomb:
    stack.extend(bomb)

print(''.join(stack) or "FRULA")

처음 제출에서는 for문이 실행된 이후에도 남아 있는 문자열이 있는 경우를 생각하지 못해서 틀렸습니다를 받았다.

---

3. 구명보트 (링크)

🔎 문제유형 : 그리디

from collections import deque

def solution(people, limit):
    answer = 0
    people.sort()
    pp = deque(people)

    while pp:
        p = pp.pop()
        if pp and p + pp[0] <= limit:
            pp.popleft()
            answer += 1
        else:
            answer += 1

    return answer

처음 제출에서는 people 배열을 역순으로 정렬하고 작은 수부터 pop하는 식으로 구현했는데, 아래 반례의 경우를 생각하지 못해서 틀렸습니다를 받았다.

[150, 120, 80, 80, 70, 40], 150
# 기대값 : 4

---

4. Tree Isomorphism (링크)

🔎 문제유형 : 그래프 이론, 그래프 탐색, 정렬, 트리, 트리 동형 사상

import sys
input = sys.stdin.readline

t = int(input())

def build_tree(st):
    stack = list()
    for s in st:
        if s == '#':
            children = list()
            while stack and stack[-1] != '(':
                children.append(stack.pop())
            stack.pop()
            children.sort()
            stack.append('(' + ''.join(children) + ')')
        else:
            stack.append('(')
    return stack[0]

for _ in range(t):
    tree1 = input().split()
    tree2 = input().split()
    t1 = build_tree(tree1)
    t2 = build_tree(tree2)
    
    if t1 == t2:
        print("The two trees are isomorphic.")
    else:
        print("The two trees are not isomorphic.")

GPT에게 트리 동형 사상을 이용한 코드를 작성해달라고 요청했을 때 다음과 같은 코드를 받았다.

class TreeNode:
    def __init__(self, label):
        self.label = label
        self.children = []

def build_tree(tokens):
    """ 전위 순회 토큰 리스트를 기반으로 트리를 생성합니다. """
    stack = []
    root = None
    current = None

    for token in tokens:
        if token == '#':
            if stack:
                current = stack.pop()
        else:
            node = TreeNode(token)
            if current:
                current.children.append(node)
            else:
                root = node
            stack.append(current)
            current = node

    return root

def encode_tree(node):
    """ 트리를 문자열로 변환하여 동형 여부를 비교할 수 있도록 합니다. """
    if not node:
        return ''
    encoded_children = sorted([encode_tree(child) for child in node.children])
    return '(' + ''.join(encoded_children) + ')'

def are_isomorphic(tree1, tree2):
    """ 두 트리가 동형인지 확인합니다. """
    return encode_tree(tree1) == encode_tree(tree2)

def main():
    import sys
    input = sys.stdin.read
    data = input().strip().split('\n')
    num_cases = int(data[0])
    results = []

    for i in range(num_cases):
        tree1_tokens = data[2 * i + 1].split()
        tree2_tokens = data[2 * i + 2].split()

        tree1 = build_tree(tree1_tokens)
        tree2 = build_tree(tree2_tokens)

        if are_isomorphic(tree1, tree2):
            results.append("The two trees are isomorphic.")
        else:
            results.append("The two trees are not isomorphic.")

    for result in results:
        print(result)

if __name__ == "__main__":
    main()