백준 알고리즘 14171 City and States

 https://www.acmicpc.net/problem/14171

14171번: Cities and States

문제 정리 
1. 첫 번째 줄엔 N을 받아서 도시의 갯수를 받아 온다.

2. 두 번째 줄부터 N번째 줄까지 도시와 주를 입력 받아 온다. 
3. 도시의 첫 두글자와 주를 비교해서 서로 같으면 Special Pair로 정의한다. 

4. 주가 같으면 인정하지 않는다. 

시도

첫 번째 시도 : 단순 city와 state 만 비교했음. 실제로 순서쌍으로 비교했어야 했는데 그로 인해 틀린 결과 받음 

import sys
input = sys.stdin.readline
n = int(input()) 
count = 0 # 쌍 갯수 세기 
for _ in range(n): # 도시 , 주 입력 받기 
    c,s= map(str,input().split())
    c = c[:2]  # 도시는 앞에 두 글자만 보게 함 s = state(주) 의미
    if c == s : # 도시와 주 모두 같으면 안됨
        continue # skip 
    if c == s[:2] and c != s :
        count +=1 
        
print(count)

두 번째 시도 : 이중 반복문으로 인해 시간 초과를 받음 

import sys
input = sys.stdin.readline
n = int(input())
count = 0
cities = []

for _ in range(n):
    c, s = input().split()
    cities.append((c[:2], s))

for i in range(n):
    for j in range(i+1, n):
        if cities[i][0] == cities[j][1] and cities[i][1] == cities[j][0]:
            count += 1

print(count)

 

해결 방법

처음부터 다시 생각해보았고 special pair 이라는 것을 토대로 순서쌍을 만들어야 하기 때문에 리스트에만 넣으려던 생각을 버리고 딕셔너리에 대해 생각해보았다. 딕셔너리에 넣고자 하는 생각을 했으나 어떻게 넣어야 할 지를 모르겠어서 고민을 했고 검색 결과 튜플 형식으로 넣어서 푸는 문제들이 많아서 이를 적용했다.

import sys
input = sys.stdin.readline
n = int(input()) 
count = 0 # 쌍 갯수 세기 
r = {}
for _ in range(n): # 도시 , 주 입력 받기 
    c,s= map(str,input().upper().split())
    c = c[:2]  # 도시는 앞에 두 글자만 보게 함 s = state(주) 의미
    
    if c == s : # 도시와 주 모두 같으면 안됨
        continue # skip 
    if (s, c) not in r:
        r[(s,c)] = 0 # 순서쌍 (s,c) 가 r에 없으면 딕셔너리에 넣어주고 값을 0으로 초기화
    r[(s,c)]+=1 # 이후 순서쌍의 갯수를 증가시켜줌
    if (c,s) in r: # r에 있는 (s,c) 와 순서를 바꾼 (c,s) 를 비교해서 공통된 special pair를 찾음 
         count += r[(c,s)] # 들어 있으면 count에 더해줌 
print(count)

 

알고리즘 풀이에 사용된 개념

1. 해시(Hash) : 자료구조 중 하나로, 효율적인 데이터 저장과 검색을 위해 사용됨. 키(Key)와 값(Value)으로 이루어진 항목들을 저장하는데, 각각의 키는 해시 함수를 통해 고유의 해시 코드(Hash Code)로 매핑됨. 
2. 해시 테이블(Hash Table) : 해시 기법을 사용하여 데이터를 저장하는 자료구조. 배열을 기반으로 하며 각 배열 원소는 버킷(Bucket)이라고 불리는 공간을 가진다. 위 문제에서는 접두사를 키로 사용하여 빠르게 해당 도시의 주 코드를 검색할 수 있었으며 반대의 경우도 가능하기 때문에 Hash Table을 사용했고 r이라는 딕셔너리를 이용했다.
3. 딕셔너리(Dictionary) :  Key와 Value를 한 쌍으로 저장하는 자료형이다. 중괄호 사이 Key:value 형태로 정의하고 쉼표로 구분함. 새로운 요소를 추가할 때는 변수명[key] = value 이용함 ex) dic['name'] = 'jongsu' 
위 코드에서는 r이라는 딕셔너리에 튜플 형태로 저장해둠 , 딕셔너리에서 key 값은 중복될 수 없고 value도 단 하나의 값만 가진다. 
4. 튜플 : 여러 개의 데이터를 묶은 하나의 집합으로서 존재하는 자료 형태 , 리스트와 유사하지만 값 변경 할 수 없는 것이 특징 소괄호() 를 사용해서 선언한다. 

 

피드백

오랜만에 푸는 알고리즘 문제라 알고리즘에 대한 명확한 분류가 떠오르지 않았다. 좀 더 익숙해지기 위해서 꾸준하게 해야 할 것 같았다. 또한 파이썬 문법이 헷갈렸다. numpy나 math 관련해서 자주 사용할 것 같아서 미리 더 공부해야겠다. 

또한 부트캠프 멘토님 말씀대로 지금은 부트캠프 적응에 좀 더 집중하고 추후 백준 알고리즘 기초 강의 등을 통해 체계적으로 공부해야겠단 생각이 들었다. 
시간계산도는 Big-O 형식으로 보았을 때 위 코드는 N의 값에 따라 하나의 반복문의 실행 횟수가 달라지기 때문에 O(N)을 보일 것이다.